算法引論及簡單算法-730708126

1、補充材料1 算法引論及簡單算法2010年11月1日計算機語言與程序設計基礎 0注 意算法是程序設計的靈魂1與數(shù)據(jù)結(jié)構(gòu)的區(qū)別：考慮問題的角度：數(shù)據(jù)結(jié)構(gòu)關心不同的數(shù)據(jù)結(jié)構(gòu)在解題中的作用和效率；算法關心不同設計技術的適用性和效率?？紤]問題的高度：數(shù)據(jù)結(jié)構(gòu)關心的是解具體問題，算法不僅如此，它提供一種解決問題的通用方法。與其他課程的關系高級程序設計語言（C語言，等） 數(shù)據(jù)結(jié)構(gòu) 算法設計與分析 系統(tǒng)的設計與實現(xiàn) 2主要內(nèi)容目標：了解算法分析的基本含義。掌握查找算法、排序算法、遞推算法等算法理念。提綱補1.1 算法分析補1.2 查找算法補1.3 排序算法補1.4 遞推算法3補1.1 算法分析前面的課程內(nèi)容以

2、C語言語法為主本補充章介紹一些基本算法大家在編寫程序的時候，“八仙過海，各顯神通”，解決同一個問題，可以使用各種方法。算法之間存在著“優(yōu)劣”之分4補1.1 算法分析1、算法分析的目的 通過對算法分析，在把算法變成程序?qū)嶋H運行前，就知道為完成一項任務所設計的算法的好壞，從而運行好算法，改進差算法，避免無益的人力和物力浪費。5補1.1 算法分析2、算法分析的含義算法分析是一種分析技術，它以獨立于具體的硬件平臺、編譯器和編程語言的方式，來描述算法的執(zhí)行行為，即它關心的是算法，而不是程序。算法分析是一種測量算法的性能的方法，它不關心精確的細節(jié)，如在算法的某次運行中總共執(zhí)行了多少條機器指令，而是想要一個

3、大致的估計，即隨著輸入數(shù)據(jù)規(guī)模的增大，算法所需工作量以何種速度遞增。（關心變化趨勢）6補1.1 算法分析3、算法復雜性 時間復雜性和空間復雜性7補1.1 算法分析1.有些計算機需要用戶提供程序運行時間的上限，一旦達到這個上限，程序?qū)⒈粡娭平Y(jié)束。2.正在開發(fā)的程序可能需要提供一個滿意的實時響應。為什么要考慮時間復雜性？81.多用戶系統(tǒng)中運行時，需指明分配給該程序的內(nèi)存大小。2.可提前知道是否有足夠可用的內(nèi)存來運行該程序。3.一個問題可能有若干個內(nèi)存需求各不相同的解決方案，從中擇取。4.利用空間復雜性來估算一個程序所能解決問題的最大規(guī)模?？紤]程序的空間復雜性的理由：補1.1 算法分析94. 如何進

4、行算法分析？事前分析：就算法本身，通過對其執(zhí)行性能的理論分析，得出關于算法特性時間和空間的一個特征函數(shù)（）與計算機軟硬件沒有直接關系。事后測試：將算法編制成程序后放到計算機上運行，收集其執(zhí)行時間和空間占用等統(tǒng)計資料，進行分析判斷直接與物理實現(xiàn)有關。補1.1 算法分析101）事前分析目的：試圖得出關于算法執(zhí)行特性的一種形式描 述，以“理論上”衡量算法 “好壞”。如何給出反映算法執(zhí)行特性的描述？ 最直接方法：統(tǒng)計算法中各種運算的執(zhí)行情況： 運用了哪些運算 每種運算被執(zhí)行的次數(shù) 該種運算執(zhí)行一次所花費的時間 算法的執(zhí)行時間=Fi*ti補1.1 算法分析11估算執(zhí)行時間的方法 選擇一種或多種（如加、乘

5、和比較等），然后確定這種（些）操作分別執(zhí)行了多少次。令n代表程序?qū)嵗卣鳎瑒t執(zhí)行時間計算公式為：TP（n）= c1ADD(n) + c2SUB(n) + c3MUL(n) + c4DIV(n)+c1、c2、c3、c4分別表示一次加、減、乘、 除操作所需的時間。函數(shù)ADD (n) 、SUB (n) 、MUL (n) 、DIV (n)分別表示程序P中，所使用的加、減、乘、除操作的次數(shù)。這種方法是否成功取決于識別關鍵操作的能力，這些關鍵操作對時間復雜性的影響最大。一條語句在整個程序運行時實際執(zhí)行時間= 頻率計數(shù) * 每執(zhí)行一次該語句所需的時間補1.1 算法分析12頻率計數(shù)：算法中語句或運算的執(zhí)行次數(shù)

6、。 例： x=x+y for (i =1;i=n;i+) for (i =1;i=n;i+) x=x+y; for (j =1;j=n;j+) x=x+y; (a) (b) (c) 分析： (a)： x=x+y執(zhí)行了1次 (b)： x=x+y執(zhí)行了n次 (c)： x=x+y執(zhí)行了n2次 注：在事前分析中，只限于確定與所使用機器及其他環(huán)境因素無關的頻率計數(shù)，依此建立一種理論上分析模型。補1.1 算法分析13數(shù)量級語句的數(shù)量級：語句的執(zhí)行頻率。例：1，n ，n2 算法的數(shù)量級：算法包含所有語句的執(zhí)行頻率之和。 算法的數(shù)量級從本質(zhì)上反映了一個算法的執(zhí)行特性。 例：求解同一問題的三個算法分別具有n,

7、n2 , n3數(shù)量級。 若n=10，則可能的執(zhí)行時間將分別是10，100，1000 個單位時間與環(huán)境因素無關。補1.1 算法分析14補1.1 算法分析5、算法復雜性的等級常量階時間復雜度為O(1)算法運行時間不隨著問題的規(guī)模而變化如：簡單的賦值語句， x=y;算術運算， x=y*5+z%3;固定次數(shù)的循環(huán)語句等for (i=0;i10;i+) for (j=0;j20;j+) aij=0;15補1.1 算法分析線性階時間復雜度為O(n)算法運行時間隨著問題的規(guī)模而成線性變化for (i=0;in;i+) sum=sun+i;算法執(zhí)行了多少次運算？i=0; 執(zhí)行了1次in; 執(zhí)行了n+1次i+；

8、 執(zhí)行了n次sum=sun+i;執(zhí)行了n次共執(zhí)行了3n+2次運算時間復雜度就是O（3n+2）實際上，算法的時間復雜度并不精確計算基本操作的執(zhí)行次數(shù)，它主要考慮問題規(guī)模的增長率。 O（n）16補1.1 算法分析平方階時間復雜度為O(n2)算法運行時間隨著問題的規(guī)模而成平方變化for (i=0;in;i+)for (j=0;jn;j+) sum=sun+aij; /執(zhí)行n2次printf(“%dn”,sum); /執(zhí)行n次時間復雜度就是O（n2）17補1.1 算法分析多項式階時間復雜度為O(nd) d為固定常數(shù)算法運行時間隨著問題的規(guī)模而成d次多項式階變化對數(shù)階 O(logn) 指數(shù)階 O(log

9、2n) 階乘階 O(n!) 若T(n) = adnd+a1n+a0是一個d次多項 式，則有T(n)=O(nd)185、算法分類（計算時間）多項式時間算法：可用多項式（函數(shù)）對其計算時間限界的算法。 常見的多項式限界函數(shù)有： (1) (logn) (n) (nlogn) (n2) (n3)指數(shù)時間算法：計算時間用指數(shù)函數(shù)限界的算法 常見的指數(shù)時間限界函數(shù)： (2n) (n！) (nn) 說明：當n取值較大時，指數(shù)時間算法和多項式時間 算法在計算時間上非常懸殊。補1.1 算法分析19 計算時間的數(shù)量級對算法有效性的影響 數(shù)量級的大小對算法的有效性有決定性的影響。 例：假設解決同一個問題的兩個算法，

10、它們都有n個輸入，計算時間的數(shù)量級分別是n2和nlogn。則： n=1024：分別需要和10240次運算。 n=2048：分別需要和22528次運算。分析：在n加倍的情況下，一個(n2)的算法計算時間增長4倍，而一個(nlogn)算法則只用兩倍多一點的時間即可完成。補1.1 算法分析20典型的計算時間函數(shù)曲線結(jié)論：在順序處理機上擴大所處理問題的規(guī)模，最有效的途徑是降低算法計算復雜度的數(shù)量級，而不是（僅僅依靠）提高計算機的速度。補1.1 算法分析21補1.2 查找算法所謂查找（search），即根據(jù)給定的某個值，在一組數(shù)據(jù)（如一個數(shù)組）中，確定有沒有出現(xiàn)相同值得數(shù)據(jù)元素。查找是非常實用的算法。如

11、，查找字典。問題描述，令b表示被查找的數(shù)組，n表示數(shù)組元素的個數(shù)，x表示被查找的目標。問題是“數(shù)據(jù)x是否出現(xiàn)在數(shù)組b當中？”22補1.2 查找算法1、順序查找方法基本思路：從數(shù)組b的第一個元素開始，逐個地與x進行比較，一直到查找成功或者所有的數(shù)組元素都已經(jīng)處理完畢。參考程序：int search(int b, int n, int x) int k; for (k=0;(kn)&(bk!=x);k+) if (kn) return(k); else return(-1);算法的復雜度為O(n)23補1.2 查找算法2、折半查找方法(對于有序數(shù)組)參考程序：int search(int b, i

12、nt n, int x) int L,R,mid; L=0;R=n-1; while(L=R) mid=(L+R)/2; if (x=bmid) return(mid);else if (xai，則交換它們，一直比較到an。同理對a1,a2,.an-1處理，即完成排序。 void bubble(int *a,int n) /*定義兩個參數(shù)：數(shù)組首地址與數(shù)組大小*/ int i,j,temp; for(i=0;in-1;i+) for(j=i+1;jaj) temp=ai; ai=aj; aj=temp; 26補1.3 排序算法選擇法 基本思路：選擇法循環(huán)過程與冒泡法一致，它還定義了記號k=i,

13、然后依次把ak同后面元素比較，若akaj,則使k=j.最后看看k=i是否還成立，不成立則交換ak,ai,這樣就比冒泡法省下許多無用的交換，提高了效率。 void choise(int *a,int n) int i,j,k,temp; for(i=0;in-1;i+) k=i; /*給記號賦值*/ for(j=i+1;jaj) k=j; /*是k總是指向最小元素*/ if(i!=k) /*當k!=i是才交換，否則ai即為最小*/ temp=ai; ai=ak; ak=temp; 27補1.4 遞推算法遞推（Recursive Algorithm），即從某個一直得初始條件出發(fā)，根據(jù)這個已知的事實

14、，并按照一定規(guī)律推斷出下一個事實。然后再從這個新的已知的事實出發(fā)，向下再推斷一個事實。遞推是計算機數(shù)值計算的一個重要方法，可以將復雜的運算簡化為若干個重復的簡單運算，從而發(fā)揮計算機長于重復處理的特點。其實質(zhì)與差分方程類似，著名的例子為Fibonacci數(shù)列。28補1.4 遞推算法例：猴子吃桃有一只小猴子，有一天摘了一堆桃子，當天吃掉了一半，后來覺得不過癮，就又多吃了一只。第二天，小猴子又將剩下的桃子吃掉了一半，并多吃了一個。以后每天都吃了前一天剩下的一半零一個。到了第十天的時候，發(fā)現(xiàn)只剩下一只桃子了。請問小猴子第一天一共摘了多少桃子？29補1.4 遞推算法解題思路T10=T9-T9/2-1 即

15、 T9=(T10+1)*2T8=(T9+1)*2T7=(T8+1)*2 T1=(T2+1)*2定義A為桃子的個數(shù)，第10天為1個，第9天為4個，第8天為10個。#include void main() int A,i; A=1; for (i=9;i=1;i-) A=(A+1)*2 pintf(小猴子第一天共摘了 %d 個桃子.n，A);30補1.4 遞推算法例：猴子分桃1979年李政道去中國科技大學訪問，出了一道題目。5只猴子摘了一堆桃子，等第二天再來分。夜里一只猴子偷偷爬起來，吃掉了一只桃子，然后把剩下的桃子分成5份，取走了自己應得到的一份，然后回家了。過了會兒，第二只猴子也爬了起來，吃掉

16、了一只桃子，然后把剩下的桃子分成5份，取走了自己應得到的一份。第三、四、五只猴子都是這樣，吃掉了一只桃子后，正好把剩下的桃子每次都能分成5份。請問最初至少有多少個桃子？每只猴子夜里起床后看到多少只桃子？31補1.4 遞推算法解題思路定義peachi（1i 5）表示第i只猴子看到的桃子數(shù)。peach2=(peach1-1)*4/5peachi=(peachi-1-1)*4/5 （2i 5） 如果知道了peach1 或者 peach5中的任意一個，都可以遞推出來每只猴子看到的桃子個數(shù)。可惜不知道啊。32補1.4 遞推算法解題思路但是我們知道：peach1%5=1；peach2%5=1，并且peach2=(peach1-1)*4/5peach3、peach4、peach5也如此可以用枚舉法，讓peach1=6，來試驗是否滿足上述條件。然后依次peach1累加5，直到滿足上述所有要求。3314.4 遞推算法#include void main() int i, peach6=0; /peach0不使用，為了計算方便 peach1=6; while(1) for (i=2;i=5;i+) peachi=(peachi-1-1)*4/5; if (peachi%5!=1) break; if (i=5) peach1+=5; els