數(shù)據(jù)結(jié)構(gòu)1-2算法分析

1、2. 算法分析,算法（Algorithm）是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每條指令表示一個(gè)或多個(gè)操作。,1,2,3,Step1：尋找雞蛋。分鐘后仍沒找到，打電話給老婆，終于找到。 Step2：洗雞蛋。 Step3：打雞蛋。輕輕磕，用力磕，用大力磕。 Step4：清理操作臺(tái)上的雞蛋清。 Step 5：清理碗中的雞蛋殼。用筷子夾，用勺子舀，用手抓，成功了（現(xiàn)在知道為什么要洗雞蛋了吧）。 Step6：攪拌。清理臉上、手上和衣服上的雞蛋清。 Step 7：發(fā)現(xiàn)碗中的雞蛋沒剩下多少，又拿出兩枚，重復(fù) Step 8：打火，打不著。還是打不著。怎么打也打不著。 Step 9：打電話問

2、老婆。 Step 10：擰開氣閥，終于打著了。 Step 11：擦紅花油，簡(jiǎn)單處理臉部灼傷。 Step 12：放油。 Step 13：倒掉紅花油，重新放入花生油。哎，一字之差！ Step 14：等待油熱，并幻想老婆吃雞蛋時(shí)被表揚(yáng)。 Step 15：救火，扇子扇，水潑，火越燒越大。 Step 16：在濃煙中爬著去找電話。 Step 17：在電話旁思考火警電話是、還是。,4,haha()/*only a joke,do nothing.*/ main()printf(請(qǐng)稍等.您將知道世界的未日.); while(1) haha(); ,算法的五個(gè)重要的特性：,(1) 有窮性：在有窮步之后結(jié)束，每一

3、步都在有窮時(shí)間內(nèi)完成。,5,算法的五個(gè)重要的特性：,(1) 有窮性：在有窮步之后結(jié)束，每一步都在有窮時(shí)間內(nèi)完成。,(2) 確定性：每一條指令必須有明確的含義，算法只有唯一的一條執(zhí)行路徑。,(3) 可行性：可通過基本運(yùn)算有限次執(zhí)行來實(shí)現(xiàn)。,6,輸入：有0個(gè)或多個(gè)輸入； 輸出：有一個(gè)或多個(gè)輸出； getsum(int num)int i,sum=0; for(i=1;i=num;i+) sum+=i; ,算法的五個(gè)重要的特性：,無輸出的算法沒有任何意義 !,7,確定性：算法中每一條指令必須有確切的含義，讀者理解時(shí)不會(huì)產(chǎn)生二義性。在相同的條件下，算法對(duì)于相同的輸入只能得出相同的輸出。 下面代碼有何問

4、題？ float average(int *a,int num) /* num為數(shù)組a元素個(gè)數(shù) */ int i; double sum=0; for(i=0;i=num;i+) sum+=*(+a); return sum/num; main() int score9=1,2,3,4,5,6,7,8,9; printf(%f,average(score,9); ,8,考慮下列兩段描述： (1) 描述一 void exam1() n2; while (n%20) nn+2; printf(%dn,n); ,華中科大考研題,(2) 描述二 void exam2() y=0; x=5/y; pri

5、ntf(“%d,%dn”,x,y); ,這兩段描述是否滿足算法的特征,若不滿足試問它們違反了哪些特征？,9,解： (1)算法是一個(gè)死循環(huán),違反了算法的有窮性特征。 (2)算法包含除零錯(cuò)誤,違反了算法的可行性特征。,10,算法的描述,編寫算法時(shí)，可采用自然語言、流程圖、計(jì)算機(jī)語言描述。,歐幾里德算法,m,n,r,例：歐幾里德算法輾轉(zhuǎn)相除法求兩個(gè)自然數(shù) m 和 n 的最大公約數(shù),11, 輸入m 和n； 求m除以n的余數(shù)r； 若r等于0，則n為最大公約數(shù)，算法結(jié)束；否則執(zhí)行第步； 將n的值放在m中，將r的值放在n中； 重新執(zhí)行第步。,例：歐幾里德算法,自然語言,算法的描述方法自然語言,12,算法的描

6、述方法自然語言,優(yōu)點(diǎn)：容易理解 缺點(diǎn)：冗長(zhǎng)、二義性、不易轉(zhuǎn)成程序,13,例：歐幾里德算法,算法的描述方法流程圖,優(yōu)點(diǎn)：流程直觀 缺點(diǎn)：缺少嚴(yán)密性、靈活性 使用方法：描述簡(jiǎn)單算法 注意事項(xiàng)：注意抽象層次,14,int CommonFactor(int m, int n) int r=m % n; while (r!=0) m=n; n=r; r=m % n; return n; ,程序設(shè)計(jì)語言,例：歐幾里德算法,算法的描述方法程序設(shè)計(jì)語言（偽代碼）,15,16,偽代碼（Pseudocode）：介于自然語言和程序設(shè)計(jì)語言之間的方法，它采用某一程序設(shè)計(jì)語言的基本語法，操作指令可以結(jié)合自然語言來設(shè)計(jì)。

7、 優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解,算法的描述方法偽代碼,17,（1）正確性（Correctness） 無語法錯(cuò)誤 無邏輯錯(cuò)誤,算法設(shè)計(jì)的要求：,（2）可讀性（Readability） 晦澀難懂的程序易隱藏錯(cuò)誤難以調(diào)試維護(hù),18,（3）健壯性（Robustness） 輸入數(shù)據(jù)非法時(shí)，不會(huì)產(chǎn)生莫名其妙的錯(cuò)誤。,算法設(shè)計(jì)的要求：,（4）效率與低存儲(chǔ)的要求,19,算法設(shè)計(jì)的目標(biāo),正確性 可使用性（用戶友好性） 可讀性 健壯性（很好的容錯(cuò)性） 高效率與低存儲(chǔ)量需求,20,算法設(shè)計(jì)的步驟：,問題描述 模型的選擇 算法設(shè)計(jì)和正確性證明 算法的程序?qū)崿F(xiàn) 算法分析,21,效率與存儲(chǔ)量分析,22,算法分析（

8、Algorithm Analysis）：對(duì)算法所需要的計(jì)算機(jī)資源時(shí)間和空間進(jìn)行估算。 時(shí)間復(fù)雜性（Time Complexity） 空間復(fù)雜性（Space Complexity）,算法分析,23,同一問題可以采用多種算法實(shí)現(xiàn)。如何比較算法執(zhí)行效率？ 算法選用的策略 問題的規(guī)模：求解的輸入量 采用的程序語言 編譯程序的好壞 機(jī)器執(zhí)行速度 因此，使用絕對(duì)時(shí)間單位衡量算法的效率不合適,24,問題規(guī)模：輸入量的多少 基本語句（程序步）：被視為算法基本運(yùn)算的一般是最深層循環(huán)內(nèi)的語句。,for (i=1; i=n; i+) for (j=1; j=n; j+) x+;,問題規(guī)模：n 基本語句：x+,算法分

9、析,25,在一個(gè)算法中,進(jìn)行基本運(yùn)算的次數(shù)越少,其運(yùn)行時(shí)間也就相對(duì)地越少；基本運(yùn)算次數(shù)越多,其運(yùn)行時(shí)間也就相對(duì)地越多。 所以,通常把算法中包含基本運(yùn)算次數(shù)的多少稱為算法的時(shí)間復(fù)雜度,也就是說,一個(gè)算法的時(shí)間復(fù)雜度是指該算法的基本運(yùn)算次數(shù)。 算法中基本運(yùn)算次數(shù)T(n)是問題規(guī)模n的某個(gè)函數(shù)f(n),記作： T(n)=O(f(n),26,定理：若A(n)=amnm+am-1nm-1+a1n+a0是一個(gè)m次多項(xiàng)式，則A(n)=O(nm)。,說明：在計(jì)算算法時(shí)間復(fù)雜度時(shí)，可以忽略所有低次冪和最高次冪的系數(shù)。,算法分析,算法分析大O符號(hào),27,算法的時(shí)間復(fù)雜度,一個(gè)沒有循環(huán)的算法的基本運(yùn)算次數(shù)與問題規(guī)模

10、無關(guān)： O（1）常數(shù)階,一個(gè)只有一重循環(huán)的算法的基本運(yùn)算次數(shù)與問題規(guī)模呈線性增大關(guān)系： O（n）線性階,28,算法的時(shí)間復(fù)雜度,O(1) O(log2(n)O(n)(n2)O(n3)O(2n),29,例： 求兩個(gè)n階方陣的相加C=A+B的算法如下,分析其時(shí)間復(fù)雜度。 #define MAX 20 /*定義最大的方階*/ void matrixadd(int n,int AMAXMAX, int BMAXMAX,int CMAXMAX) int i,j; for (i=0;in;i+) for (j=0;jn;j+) Cij=Aij+Bij; ,30,該算法中的基本運(yùn)算是兩重循環(huán)中最深層的語句C

11、ij=Aij+Bij,分析它的頻度,即： T(n)= =O(n2),31,例： 分析以下算法的時(shí)間復(fù)雜度。 int fun(int n) int i,j,k,s; s=0; for (i=0;i=n;i+) for (j=0;j=i;j+) for (k=0;k=j;k+) s+; return(s); ,基本語句或基本操作,32,解：該算法的基本操作是語句s+,其頻度： T(n)= =O(n3) 則該算法的時(shí)間復(fù)雜度為O(n3)。,33,最好情況：出現(xiàn)概率較大時(shí)分析 最差情況：實(shí)時(shí)系統(tǒng) 平均情況：已知輸入數(shù)據(jù)是如何分布的， 通常假設(shè)等概率分布,結(jié)論：如果問題規(guī)模相同，時(shí)間代價(jià)與輸入數(shù)據(jù)有關(guān)，

12、則需要分析最好情況、最壞情況、平均情況。,1.4 算法及算法分析,最好情況、最壞情況、平均情況,34,Void bubble_sort(int a, int n) /起泡排序：將a中整數(shù)序列按照升序重新排列 For(i=n-1, change=TRUE; i=1 change = TRUE ,35,分析： 輸入集合升序：基本操作次數(shù)為0 輸入集合逆序：操作次數(shù)為：n(n-1)/2 T(n)= =4 =O(n2),36,分析下面語句的時(shí)間復(fù)雜度：,i=1; while(i=n) i = i*2; 分析：,37,設(shè)語句i = i*2的語句頻度為f(n)，則有2 f（n）=n，即f（n）=log2n

13、，所以該程序段的時(shí)間復(fù)雜度T（n）= O(log2n)。,分析下面語句的執(zhí)行次數(shù)：,i=0; s=0; n=100; do i = i+1; s = s+10*i while(NOT(in) AND (sn); 分析：,38,該程序段中，循環(huán)語句的執(zhí)行次數(shù)為4（這時(shí)i = 4，s = 100），do循環(huán)中先執(zhí)行循環(huán)體，后判斷條件，直到條件為真時(shí)退出循環(huán)。,算法空間復(fù)雜度度量,一個(gè)算法一般占用三部分存貯空間 算法本身占用 輸入、輸出數(shù)據(jù)占用： 算法運(yùn)行中臨時(shí)占用空間（可變部分） 算法的空間性能以一個(gè)算法運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間作為度量標(biāo)準(zhǔn)算法空間復(fù)雜度，記作S(n)=O(f(n) 時(shí)間和空間

14、相互之間有一種制約關(guān)系，何者為重需視具體情況而定。,39,算法空間復(fù)雜度度量,若額外空間相對(duì)于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。,40,41,基本操作的實(shí)現(xiàn)：,本書約定： 常量的定義： #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 數(shù)據(jù)元素類型約定為：ElemType typedef int Status; /函數(shù)類型，函數(shù)結(jié)果狀態(tài)代碼,41,練習(xí)： 1、有下列運(yùn)行時(shí)間函數(shù),分別寫出相應(yīng)的大O表示的運(yùn)算時(shí)間。 (1) T1 (n)=1000; (2) T2 (n)=n2 +1000n; (3) T3(n)= 3n3+100n2+n+1; 2、分析下面語句的時(shí)間復(fù)雜度： for(i=1;i=n;i+) (2) i=1;k=0; for(j=1;j=i;j+) w