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

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

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

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

4、題？ float average(int *a,int num) /* num為數(shù)組a元素個數(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)算法是一個死循環(huán),違反了算法的有窮性特征。 (2)算法包含除零錯誤,違反了算法的可行性特征。,10,算法的描述,編寫算法時，可采用自然語言、流程圖、計算機語言描述。,歐幾里德算法,m,n,r,例：歐幾里德算法輾轉(zhuǎn)相除法求兩個自然數(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)點：容易理解 缺點：冗長、二義性、不易轉(zhuǎn)成程序,13,例：歐幾里德算法,算法的描述方法流程圖,優(yōu)點：流程直觀 缺點：缺少嚴密性、靈活性 使用方法：描述簡單算法 注意事項：注意抽象層次,14,int CommonFactor(int m, int n) int r=m % n; while (r!=0) m=n; n=r; r=m % n; return n; ,程序設(shè)計語言,例：歐幾里德算法,算法的描述方法程序設(shè)計語言（偽代碼）,15,16,偽代碼（Pseudocode）：介于自然語言和程序設(shè)計語言之間的方法，它采用某一程序設(shè)計語言的基本語法，操作指令可以結(jié)合自然語言來設(shè)計。

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

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

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

10、無關(guān)： O（1）常數(shù)階,一個只有一重循環(huán)的算法的基本運算次數(shù)與問題規(guī)模呈線性增大關(guān)系： O（n）線性階,28,算法的時間復雜度,O(1) O(log2(n)O(n)(n2)O(n3)O(2n),29,例： 求兩個n階方陣的相加C=A+B的算法如下,分析其時間復雜度。 #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,該算法中的基本運算是兩重循環(huán)中最深層的語句C

11、ij=Aij+Bij,分析它的頻度,即： T(n)= =O(n2),31,例： 分析以下算法的時間復雜度。 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) 則該算法的時間復雜度為O(n3)。,33,最好情況：出現(xiàn)概率較大時分析 最差情況：實時系統(tǒng) 平均情況：已知輸入數(shù)據(jù)是如何分布的， 通常假設(shè)等概率分布,結(jié)論：如果問題規(guī)模相同，時間代價與輸入數(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,分析下面語句的時間復雜度：,i=1; while(i=n) i = i*2; 分析：,37,設(shè)語句i = i*2的語句頻度為f(n)，則有2 f（n）=n，即f（n）=log2n

13、，所以該程序段的時間復雜度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（這時i = 4，s = 100），do循環(huán)中先執(zhí)行循環(huán)體，后判斷條件，直到條件為真時退出循環(huán)。,算法空間復雜度度量,一個算法一般占用三部分存貯空間 算法本身占用 輸入、輸出數(shù)據(jù)占用： 算法運行中臨時占用空間（可變部分） 算法的空間性能以一個算法運行過程中臨時占用的存儲空間作為度量標準算法空間復雜度，記作S(n)=O(f(n) 時間和空間

14、相互之間有一種制約關(guān)系，何者為重需視具體情況而定。,39,算法空間復雜度度量,若額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。,40,41,基本操作的實現(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,練習： 1、有下列運行時間函數(shù),分別寫出相應的大O表示的運算時間。 (1) T1 (n)=1000; (2) T2 (n)=n2 +1000n; (3) T3(n)= 3n3+100n2+n+1; 2、分析下面語句的時間復雜度： for(i=1;i=n;i+) (2) i=1;k=0; for(j=1;j=i;j+) w