數據結構1-2算法分析

2.算法分析

算法（Algorithm）是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每條指令表示一個或多個操作。1Step1：尋找雞蛋。１分鐘后仍沒找到，打電話給老婆，終于找到。Step2：洗雞蛋。Step3：打雞蛋。輕輕磕，用力磕，用大力磕。Step4：清理操作臺上的雞蛋清。Step

5：清理碗中的雞蛋殼。用筷子夾，用勺子舀，用手抓，成功了（現在知道為什么要洗雞蛋了吧）。Step6：攪拌。清理臉上、手上和衣服上的雞蛋清。Step

7：發(fā)現碗中的雞蛋沒剩下多少，又拿出兩枚，重復２—７Step

8：打火，打不著。還是打不著。怎么打也打不著。Step

9：打電話問老婆。Step

10：擰開氣閥，終于打著了。Step

11：擦紅花油，簡單處理臉部灼傷。Step

12：放油。Step

13：倒掉紅花油，重新放入花生油。哎，一字之差！Step

14：等待油熱，并幻想老婆吃雞蛋時被表揚。Step

15：救火，扇子扇，水潑，火越燒越大。Step

16：在濃煙中爬著去找電話。Step

17：在電話旁思考火警電話是１１０、１２０還是１１９。2haha()

{ /*onlyajoke,donothing.*/

}

main()

{ printf("請稍等...您將知道世界的未日...");

while(1)

haha();

}算法的五個重要的特性：

(1)有窮性：在有窮步之后結束，每一步都在有窮時間內完成。3算法的五個重要的特性：

(1)有窮性：在有窮步之后結束，每一步都在有窮時間內完成。(2)確定性：每一條指令必須有明確的含義，算法只有唯一的一條執(zhí)行路徑。

(3)可行性：可通過基本運算有限次執(zhí)行來實現。4

輸入：有0個或多個輸入；

輸出：有一個或多個輸出；getsum(intnum)

{ inti,sum=0;

for(i=1;i<=num;i++)

sum+=i;

} 算法的五個重要的特性：

無輸出的算法沒有任何意義!5

確定性：算法中每一條指令必須有確切的含義，讀者理解時不會產生二義性。在相同的條件下，算法對于相同的輸入只能得出相同的輸出。下面代碼有何問題？floataverage(int*a,intnum) /*num為數組a元素個數*/{ inti; doublesum=0;

for(i=0;i<=num;i++)

sum+=*(++a);

returnsum/num;

}main(){ intscore[9]={1,2,3,4,5,6,7,8,9};

printf("%f",average(score,9));}6考慮下列兩段描述：(1)描述一

voidexam1() { n＝2; while(n%2＝＝0) n＝n+2; printf("%d\n",n); }華中科大考研題

(2)描述二

voidexam2() { y=0; x=5/y; printf(“%d,%d\n”,x,y); }

這兩段描述是否滿足算法的特征,若不滿足試問它們違反了哪些特征？7解：(1)算法是一個死循環(huán),違反了算法的有窮性特征。(2)算法包含除零錯誤,違反了算法的可行性特征。8算法的描述編寫算法時，可采用自然語言、流程圖、計算機語言描述。歐幾里德算法mnr例：歐幾里德算法——輾轉相除法求兩個自然數m

和n

的最大公約數9①輸入m

和n；②求m除以n的余數r；③若r等于0，則n為最大公約數，算法結束；否則執(zhí)行第④步；④將n的值放在m中，將r的值放在n中；⑤重新執(zhí)行第②步。例：歐幾里德算法自然語言算法的描述方法——自然語言

10算法的描述方法——自然語言

優(yōu)點：容易理解缺點：冗長、二義性、不易轉成程序11N開始輸入m和n

r=m%nr=0m=n；n=r輸出n結束Y例：歐幾里德算法算法的描述方法——流程圖

優(yōu)點：流程直觀缺點：缺少嚴密性、靈活性使用方法：描述簡單算法注意事項：注意抽象層次12intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}程序設計語言例：歐幾里德算法算法的描述方法——程序設計語言（偽代碼）1314偽代碼（Pseudocode）：介于自然語言和程序設計語言之間的方法，它采用某一程序設計語言的基本語法，操作指令可以結合自然語言來設計。優(yōu)點：表達能力強，抽象性強，容易理解算法的描述方法——偽代碼

15（1）正確性（Correctness）

無語法錯誤

無邏輯錯誤算法設計的要求：（2）可讀性（Readability）

晦澀難懂的程序易隱藏錯誤難以調試維護16（3）健壯性（Robustness）

輸入數據非法時，不會產生莫名其妙的錯誤。算法設計的要求：（4）效率與低存儲的要求17算法設計的目標正確性可使用性（用戶友好性）可讀性健壯性（很好的容錯性）高效率與低存儲量需求18算法設計的步驟：問題描述模型的選擇

算法設計和正確性證明

算法的程序實現

算法分析19算法一算法二在三個整數中求最大者max(inta,intb,intc)

{if(a>b)

if(a>c)returna;

elsereturnc;

else

if(b>c)returnb;

elsereturnc;

}/*無需額外存儲空間，只需兩次比較*/max(inta[3])

{intc,inti;

c=a[0];

for(i=1;i<3;i++)

if(a[i]>c)c=a[i];

returnc;

}

/*需要兩個額外的存儲空間，兩次比較，至少一次賦值*/

/*共需5個整型數空間*/求100個整數中最大者同上的算法難寫，難讀max(inta[100])

{intc,inti;

c=a[0];

for(i=1;i<100;i++)

if(a[i]>c)c=a[i];

returnc;

}

/*共需102個整型數空間*/效率與存儲量分析20算法分析（AlgorithmAnalysis）：對算法所需要的計算機資源——時間和空間進行估算。時間復雜性（TimeComplexity）空間復雜性（SpaceComplexity）算法分析21同一問題可以采用多種算法實現。如何比較算法執(zhí)行效率？

算法選用的策略問題的規(guī)模：求解的輸入量采用的程序語言編譯程序的好壞機器執(zhí)行速度

因此，使用絕對時間單位衡量算法的效率不合適22問題規(guī)模：輸入量的多少基本語句（程序步）：被視為算法基本運算的一般是最深層循環(huán)內的語句。for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;問題規(guī)模：n基本語句：x++算法分析23

在一個算法中,進行基本運算的次數越少,其運行時間也就相對地越少；基本運算次數越多,其運行時間也就相對地越多。所以,通常把算法中包含基本運算次數的多少稱為算法的時間復雜度,也就是說,一個算法的時間復雜度是指該算法的基本運算次數。

算法中基本運算次數T(n)是問題規(guī)模n的某個函數f(n),記作：

T(n)=O(f(n))24定理：若A(n)=amnm+am-1nm-1++a1n+a0是一個m次多項式，則A(n)=O(nm)。說明：在計算算法時間復雜度時，可以忽略所有低次冪和最高次冪的系數。算法分析算法分析——大O符號25算法的時間復雜度一個沒有循環(huán)的算法的基本運算次數與問題規(guī)模無關：

O（1）常數階一個只有一重循環(huán)的算法的基本運算次數與問題規(guī)模呈線性增大關系：

O（n）線性階26算法的時間復雜度O(1)<O(log2(n))<O(n)<(n2)<O(n3)<O(2n)27

例：

求兩個n階方陣的相加C=A+B的算法如下,分析其時間復雜度。

#defineMAX20/*定義最大的方階*/voidmatrixadd(intn,intA[MAX][MAX],intB[MAX][MAX],intC[MAX][MAX]){ inti,j; for(i=0;i<n;i++) for(j=0;j<n;j++) C[i][j]=A[i][j]+B[i][j];}28

該算法中的基本運算是兩重循環(huán)中最深層的語句C[i][j]=A[i][j]+B[i][j],分析它的頻度,即：

T(n)==O(n2)29例：分析以下算法的時間復雜度。

intfun(intn){inti,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);}基本語句或基本操作30

解：該算法的基本操作是語句s++,其頻度：

T(n)==O(n3)則該算法的時間復雜度為O(n3)。31最好情況：出現概率較大時分析最差情況：實時系統(tǒng)平均情況：已知輸入數據是如何分布的，通常假設等概率分布結論：如果問題規(guī)模相同，時間代價與輸入數據有關，則需要分析最好情況、最壞情況、平均情況。1.4算法及算法分析最好情況、最壞情況、平均情況32Voidbubble_sort(inta[],intn){//起泡排序：將a中整數序列按照升序重新排列For(i=n-1,change=TRUE;i>=1&&change;--i){ change=FALSE; for(j=0;j<i;j++) if(a[j]>a[j+1]) {a[j]a[i+1];change=TRUE} }}33分析：輸入集合升序：基本操作次數為0輸入集合逆序：操作次數為：n(n-1)/2T(n)==4·=O(n2)34分析下面語句的時間復雜度：i=1; while(i<=n) i=i*2;分析：35設語句i=i*2的語句頻度為f(n)，則有2f（n）<=n，即f（n）<=log2n，所以該程序段的時間復雜度T（n）=O(log2n)。分析下面語句的執(zhí)行次數：i=0;s=0;n=100;do i=i+1; s=s+10*iwhile(NOT((i<n)AND(s<n)));分析：36該程序段中，循環(huán)語句的執(zhí)行次數為4（這時i=4，s=100），do循環(huán)中先執(zhí)行循環(huán)體，后判斷條件，直到條件為真時退出循環(huán)。算法空間復雜度度量一個算法一般占用三部分存貯空間算法本身占用輸入、輸出數據占用：算法運行中臨時占用空間（可變部分）算法的空間性能以一個算法運行過程中臨時占用的存儲空間作為度量標準——算法空間復雜度，記作S(n)=O(f(n))時間和空間相互之間有一種制約關系，何者為重需視具體情況而定。37算法空間復雜度度量若額外空間相對于輸入數據量來說是常數，則稱此算法為原地工作。3839基本操作的實現：

本書約定：常量的定義：

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFL