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

2.算法分析

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

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

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

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

9：打電話問老婆。Step

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

11：擦紅花油，簡(jiǎn)單處理臉部灼傷。Step

12：放油。Step

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

14：等待油熱，并幻想老婆吃雞蛋時(shí)被表?yè)P(yáng)。Step

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

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

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

{ /*onlyajoke,donothing.*/

}

main()

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

while(1)

haha();

}算法的五個(gè)重要的特性：

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

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

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

輸入：有0個(gè)或多個(gè)輸入；

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

{ inti,sum=0;

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

sum+=i;

} 算法的五個(gè)重要的特性：

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

確定性：算法中每一條指令必須有確切的含義，讀者理解時(shí)不會(huì)產(chǎn)生二義性。在相同的條件下，算法對(duì)于相同的輸入只能得出相同的輸出。下面代碼有何問題？floataverage(int*a,intnum) /*num為數(shù)組a元素個(gè)數(shù)*/{ 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)算法是一個(gè)死循環(huán),違反了算法的有窮性特征。(2)算法包含除零錯(cuò)誤,違反了算法的可行性特征。8算法的描述編寫算法時(shí)，可采用自然語(yǔ)言、流程圖、計(jì)算機(jī)語(yǔ)言描述。歐幾里德算法mnr例：歐幾里德算法——輾轉(zhuǎn)相除法求兩個(gè)自然數(shù)m

和n

的最大公約數(shù)9①輸入m

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

10算法的描述方法——自然語(yǔ)言

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

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

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

15（1）正確性（Correctness）

無語(yǔ)法錯(cuò)誤

無邏輯錯(cuò)誤算法設(shè)計(jì)的要求：（2）可讀性（Readability）

晦澀難懂的程序易隱藏錯(cuò)誤難以調(diào)試維護(hù)16（3）健壯性（Robustness）

輸入數(shù)據(jù)非法時(shí)，不會(huì)產(chǎn)生莫名其妙的錯(cuò)誤。算法設(shè)計(jì)的要求：（4）效率與低存儲(chǔ)的要求17算法設(shè)計(jì)的目標(biāo)正確性可使用性（用戶友好性）可讀性健壯性（很好的容錯(cuò)性）高效率與低存儲(chǔ)量需求18算法設(shè)計(jì)的步驟：?jiǎn)栴}描述模型的選擇

算法設(shè)計(jì)和正確性證明

算法的程序?qū)崿F(xiàn)

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

{if(a>b)

if(a>c)returna;

elsereturnc;

else

if(b>c)returnb;

elsereturnc;

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

{intc,inti;

c=a[0];

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

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

returnc;

}

/*需要兩個(gè)額外的存儲(chǔ)空間，兩次比較，至少一次賦值*/

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

{intc,inti;

c=a[0];

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

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

returnc;

}

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

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

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

在一個(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))24定理：若A(n)=amnm+am-1nm-1++a1n+a0是一個(gè)m次多項(xiàng)式，則A(n)=O(nm)。說明：在計(jì)算算法時(shí)間復(fù)雜度時(shí)，可以忽略所有低次冪和最高次冪的系數(shù)。算法分析算法分析——大O符號(hào)25算法的時(shí)間復(fù)雜度一個(gè)沒有循環(huán)的算法的基本運(yùn)算次數(shù)與問題規(guī)模無關(guān)：

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

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

例：

求兩個(gè)n階方陣的相加C=A+B的算法如下,分析其時(shí)間復(fù)雜度。

#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

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

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

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);}基本語(yǔ)句或基本操作30

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

T(n)==O(n3)則該算法的時(shí)間復(fù)雜度為O(n3)。31最好情況：出現(xiàn)概率較大時(shí)分析最差情況：實(shí)時(shí)系統(tǒng)平均情況：已知輸入數(shù)據(jù)是如何分布的，通常假設(shè)等概率分布結(jié)論：如果問題規(guī)模相同，時(shí)間代價(jià)與輸入數(shù)據(jù)有關(guān)，則需要分析最好情況、最壞情況、平均情況。1.4算法及算法分析最好情況、最壞情況、平均情況32Voidbubble_sort(inta[],intn){//起泡排序：將a中整數(shù)序列按照升序重新排列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分析：輸入集合升序：基本操作次數(shù)為0輸入集合逆序：操作次數(shù)為：n(n-1)/2T(n)==4·=O(n2)34分析下面語(yǔ)句的時(shí)間復(fù)雜度：i=1; while(i<=n) i=i*2;分析：35設(shè)語(yǔ)句i=i*2的語(yǔ)句頻度為f(n)，則有2f（n）<=n，即f（n）<=log2n，所以該程序段的時(shí)間復(fù)雜度T（n）=O(log2n)。分析下面語(yǔ)句的執(zhí)行次數(shù)：i=0;s=0;n=100;do i=i+1; s=s+10*iwhile(NOT((i<n)AND(s<n)));分析：36該程序段中，循環(huán)語(yǔ)句的執(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í)間和空間相互之間有一種制約關(guān)系，何者為重需視具體情況而定。37算法空間復(fù)雜度度量若額外空間相對(duì)于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。3839基本操作的實(shí)現(xiàn)：

本書約定：常量的定義：

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFL