算法分析和計算復雜性分析

1、算法分析與評估概述在查找引擎優(yōu)化范疇里邊有一個疑問常常讓人感受捉摸不透到底是什么樣的排序要素 結(jié)尾決定了網(wǎng)頁的排名。而每個查找引擎公司都將其的查找引擎算法維護的極端嚴密，只有 很少很少的一些的公司能有時機看到這些算法的全貌。并且就算是有時機看到這些算法的真 實容貌，要想領(lǐng)悟到話，還得具有深沉的數(shù)學功底。這使得對查找引擎優(yōu)化整個概念的曉得 變得很艱難。同一問題可用不同算法解決，而一個算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的 效率。一個算法得出一個解，那么這個解是最優(yōu)解還是可行解？如果是可行解，與最優(yōu)解的偏 差有多大？對于算法的效果，存在兩種評價方法一一證明方法和仿真分析方法。證明方法是 指利用數(shù)學方

2、法對于算法進行評估，證明它的解的類型。仿真分析方法是指產(chǎn)生或選取大量 的、具有代表性的問題實例，利用該算法對這些問題實例進行求解，并對算法產(chǎn)生的結(jié)果進 行統(tǒng)計分析。例如對于TSP問題貪心算法的模擬與分析，關(guān)于貪心算法的正確性，直觀上只需檢查 算法的輸出結(jié)果中，每個城市出現(xiàn)且只出現(xiàn)一次，該結(jié)果即是TSP問題的可行解，說明算 法正確的求解了這些問題。關(guān)于它的效果，如果實例的最優(yōu)解一直（問題規(guī)模小或問題已被 成功求解），利用統(tǒng)計方法對若干問題實例的算法結(jié)果與最優(yōu)解進行對比分析，即可對其進 行效果評價。而對于較大規(guī)模的問題實例，其最優(yōu)解往往是未知的，因此算法的效果評價 只能借助于與前人算法的結(jié)果的比較

3、。復雜度評價一個算法時另一個問題是 算法能夠執(zhí)行的了嗎？有限的時間和空間上這個算法能 夠執(zhí)行嗎？這就需要對算法的復雜性進行分析。算法的時間復雜度和空間復雜度合稱為算法 的復雜度。時間復雜度時間頻度一個算法執(zhí)行所耗費的時間，從理論上是不能算出來的，必須上機運 行測試才能知道。但我們不可能也沒有必要對每個算法都上機測試，只需知道哪個算法花費 的時間多，哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執(zhí)行 次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多。一個算法中的語句執(zhí)行次數(shù) 稱為語句頻度或時間頻度。記為T(n)。時間復雜度在剛才提到的時間頻度中，n稱為問題的規(guī)模，當n不

4、斷變化時，時 間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現(xiàn)什么規(guī)律。為此，我們引入時 間復雜度概念。一般情況下，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)， 用T(n)表示，若有某個輔助函數(shù)f(n),使得當n趨近于無窮大時，T( n)/f(n)的極限值為不等 于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n)，稱O(f(n)為算法的漸進 時間復雜度，簡稱時間復雜度。時間頻度不同，但時間復雜度可能相同。如：T(n)=n2+3n+4與T(n)=4n2+2n+1它們的 頻度不同，但時間復雜度相同，都為O(n2)o按數(shù)量級遞增排列，常見的時間復雜度有：常數(shù)

5、階0(1),對數(shù)階O(log2n)，線性階O(n), 線性對數(shù)階O(nlog2n),平方階0(n2)，立方階0(n3),. ,k次方階0(nk),指數(shù)階0(2n)。隨著 問題規(guī)模n的不斷增大，上述時間復雜度不斷增大，算法的執(zhí)行效率越低。 最壞時間復雜度和平均時間復雜度最壞情況下的時間復雜度稱最壞時間復雜 度。一般不特別說明，討論的時間復雜度均是最壞情況下的時間復雜度。這樣做的原因是： 最壞情況下的時間復雜度是算法在任何輸入實例上運行時間的上界這就保證了算法的運行 時間不會比任何更長。在最壞情況下的時間復雜度為T(n)=0(n)，它表示對于任何輸入實例，該算法的運行時間 不可能大于0(n)。平均

6、時間復雜度是指所有可能的輸入實例均以等概率出現(xiàn)的情況下，算 法的期望運行時間。指數(shù)階0(2n)，顯然，時間復雜度為指數(shù)階0(2n)的算法效率極低，當n值稍大時就無 法應用。求時間復雜度【1】如果算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長即使算法中有上千條語句， 其執(zhí)行時間也不過是一個較大的常數(shù)。此類算法的時間復雜度是0(1)。x=91;y=100;while(y0) if(x100) (x=x-10;y-; else x+;解答：T(n)=0(1)，這個程序看起來有點嚇人，總共循環(huán)運行了 1100次，但是我們看到n沒有？沒。這段程序的運行是和n無關(guān)的，就算它再循環(huán)一萬年，我們也不管他，只是一個

7、常數(shù)階的函數(shù)【2】當有若干個循環(huán)語句時，算法的時間復雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi) 層語句的頻度f(n)決定的。x=1;for(i=1;i=n;i+)for(j=1;j=i;j+) for(k=1;k=0&(Ai!=k)i-;return i;此算法中的語句(3)的頻度不僅與問題規(guī)模n有關(guān)，還與輸入實例中A的各元素取值及 K的取值有關(guān)：若A中沒有與K相等的元素，則語句(3)的頻度f(n)=n ；若A的最后一 個元素等于K,則語句(3)的頻度f(n)是常數(shù)0。時間復雜度評價性能有兩個算法A1和A2求解同一問題 時間復雜度分別是T1(n)=100n2，T2(n)=5n3( 1 ) 當輸入量n

8、T2(n)，后者花費的時間較少。(2 )隨著問題規(guī)模n的增大， 兩個算法的時間開銷之比5n3/100n2=n/20亦隨著增大。即當問題規(guī)模較大時，算法A1比 算法A2要有效地多。它們的漸近時間復雜度O(n2)和O(n3)從宏觀上評價了這兩個算法在 時間方面的質(zhì)量。在算法分析時，往往對算法的時間復雜度和漸近時間復雜度不予區(qū)分，而 經(jīng)常是將漸近時間復雜度T(n)=O(f(n)簡稱為時間復雜度，其中的f(n)般是算法中頻度最 大的語句頻度。2.2 .空間復雜度一個程序的空間復雜度是指運行完一個程序所需內(nèi)存的大小。利用程序的空間復雜度， 可以對程序的運行所需要的內(nèi)存多少有個預先估計。一個程序執(zhí)行時除了

9、需要存儲空間和存 儲本身所使用的指令、常數(shù)、變量和輸入數(shù)據(jù)外，還需要一些對數(shù)據(jù)進行操作的工作單元和 存儲一些為現(xiàn)實計算所需信息的輔助空間。程序執(zhí)行時所需存儲空間包括以下兩部分。（1）固定部分。這部分空間的大小與輸入/輸出的數(shù)據(jù)的個數(shù)多少、數(shù)值無關(guān)。主要包 括指令空間（即代碼空間X數(shù)據(jù)空間（常量、簡單變量）等所占的空間。這部分屬于靜態(tài) 空間。（2）可變空間，這部分空間的主要包括動態(tài)分配的空間，以及遞歸棧所需的空間等。 這部分的空間大小與算法有關(guān)。一個算法所需的存儲空間用f（n）表示。S（n）=O（f（n） 其中n為問題的規(guī)模，S（n）表 示空間復雜度。對幾種排序算法進行分析3.1、冒泡法（起泡法

10、）3.1.1算法要求：用起泡法對10個整數(shù)按升序排序。3.1.2算法分析：如果有n個數(shù)，則要進行n-1趟比較。在第1趟比較中要進行n-1次 相鄰元素的兩兩比較，在第j趟比較中要進行n-j次兩兩比較。比較的順序從前往后，經(jīng)過 一趟比較后，將最值沉底（換到最后一個元素位置），最大值沉底為升序，最小值沉底為降 序。3.1.3算法源代碼：# include main()(int a10,i,j,t;printf(Please input 10 numbers:);/*輸入源數(shù)據(jù)*/for(i=0;i10;i+)scanf(%d,&ai);/*排序*/for(j=0;j9;j+)/*外循環(huán)控制排序趟數(shù)，

11、n個數(shù)排n-1趟*/for(i=0;iai+1)/*相鄰元素比較，逆序則交換*/( t=ai;ai=ai+1;ai+1=t;/*輸出排序結(jié)果*/printf(The sorted numbers:);for(i=0;i10;i+)printf(%d ,ai);printf(n);3.1.4算法特點：相鄰元素兩兩比較，每趟將最值沉底即可確定一個數(shù)在結(jié)果的位置， 確定元素位置的順序是從后往前，其余元素可能作相對位置的調(diào)整。可以進行升序或降序排 序。3.1.5優(yōu)點：穩(wěn)定，比較次數(shù)已知；3.1.6缺點：慢，每次只能移動相鄰兩個數(shù)據(jù)，移動數(shù)據(jù)的次數(shù)多。3.2、選擇法3.2.1算法要求：用選擇法對10個整

12、數(shù)按降序排序。3.2.2算法分析：每趟選出一個最值和無序序列的第一個數(shù)交換，n個數(shù)共選n-1趟。 第i趟假設(shè)i為最值下標，然后將最值和i+1至最后一個數(shù)比較，找出最值的下標，若最值 下標不為初設(shè)值，則將最值元素和下標為i的元素交換。3.2.3算法源代碼：# include main()(int a10,i,j,k,t,n=10;printf(Please input 10 numbers:);for(i=0;i10;i+)scanf(%d,&ai);for(i=0;in-1;i+)/*外循環(huán)控制趟數(shù)，n個數(shù)選n-1趟*/k=i;/*k=i;/*假設(shè)當前趟的第一個數(shù)為最值，記在k中*/for(j

13、=i+1;jn;j+)/*從下一個數(shù)到最后一個數(shù)之間找最值*/if(akaj)/*若其后有比最值更大的*/k=j;/*k=j;/*則將其下標記在k中*/if(k!=i)/*若k不為最初的i值，說明在其后找到比其更大的數(shù)*/if(k!=i)( t=ak; ak=ai; ai=t; /*則交換最值和當前序列的第一個數(shù)*/printf(The sorted numbers:);for(i=0;i10;i+)printf(%d ,ai);printf(n);3.2.4算法特點：每趟是選出一個最值確定其在結(jié)果序列中的位置，確定元素的位置是 從前往后，而每趟最多進行一次交換，其余元素的相對位置不變?？蛇M行

14、降序排序或升序排 序。3.2.5優(yōu)點：穩(wěn)定，比較次數(shù)與冒泡排序一樣，數(shù)據(jù)移動次數(shù)比冒泡排序少；3.2.6缺點：相對之下還是慢。3.3、插入法3.3.1算法要求：用插入排序法對10個整數(shù)進行降序排序。3.3.2算法分析：將序列分為有序序列和無序列，依次從無序序列中取出元素值插入到 有序序列的合適位置。初始是有序序列中只有第一個數(shù)，其余n-1個數(shù)組成無序序列，則n 個數(shù)需進n-1次插入。尋找在有序序列中插入位置可以從有序序列的最后一個數(shù)往前找，在 未找到插入點之前可以同時向后移動元素，為插入元素準備空間。3.3.3算法源代碼：# include main()(int a10,i,j,t;print

15、f(Please input 10 numbers:);for(i=0;i10;i+)scanf(%d,&ai);for(i=1;i=0 & taj ; j- ) /*在有序序列(下標0i-1)中尋找插入位置*/ aj+1=aj;/*若未找到插入位置，則當前元素后移一個位置*/aj+1=t;/*找到插入位置，完成插入*/printf(The sorted numbers:);for(i=0;i10;i+)printf(%d ,ai);printf(n);3.3.4優(yōu)點：穩(wěn)定，快；3.3.5缺點：比較次數(shù)不一定，比較次數(shù)越少，插入點后的數(shù)據(jù)移動越多，特別是當數(shù) 據(jù)總量龐大的時候，但用鏈表可以解決

16、這個問題。對幾種排序算法的復雜性分析做成如下表格類別排序方法時間復雜度空間復雜度穩(wěn)定性平均情況最好情況最壞情況輔助存儲插入排序直接插入O(nA2)O(n)Og)O(1)穩(wěn)定shell排序O(nA1.3)O(n)Og)O(1)不穩(wěn)定選擇排序直接選擇O2)O2)Og)O(1)不穩(wěn)定堆排序O(nlog2 n)O(nlog2 n)O(nlog2 n)O(1)不穩(wěn)定交換排序冒泡排序O2)O(n)Og)O(1)穩(wěn)定快速排序O(nlog2 n)O(nlog2 n)Og)O(nlog2 n)不穩(wěn)定歸并排序O(nlog2 n)O(nlog2 n)O(nlog2 n)O(1)穩(wěn)定基數(shù)排序O(d(r+n) O(d(n+rd) O(d(r+n)O(rd+n)穩(wěn)定注：基數(shù)排序的復雜度中，r代表關(guān)鍵字的基數(shù)，d代表長度，n代表關(guān)鍵字的個數(shù)總結(jié)算法分析是對一個算法需要多少計算時間和存儲空間作定量的分析。算法(Algorithm) 是解