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

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

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

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

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

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

7、常數階的函數【2】當有若干個循環語句時，算法的時間復雜度是由嵌套層數最多的循環語句中最內 層語句的頻度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)的頻度不僅與問題規模n有關，還與輸入實例中A的各元素取值及 K的取值有關：若A中沒有與K相等的元素，則語句(3)的頻度f(n)=n ；若A的最后一 個元素等于K,則語句(3)的頻度f(n)是常數0。時間復雜度評價性能有兩個算法A1和A2求解同一問題 時間復雜度分別是T1(n)=100n2，T2(n)=5n3( 1 ) 當輸入量n

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

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

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

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

12、數按降序排序。3.2.2算法分析：每趟選出一個最值和無序序列的第一個數交換，n個數共選n-1趟。 第i趟假設i為最值下標，然后將最值和i+1至最后一個數比較，找出最值的下標，若最值 下標不為初設值，則將最值元素和下標為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+)/*外循環控制趟數，n個數選n-1趟*/k=i;/*k=i;/*假設當前趟的第一個數為最值，記在k中*/for(j

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

14、降序排序或升序排 序。3.2.5優點：穩定，比較次數與冒泡排序一樣，數據移動次數比冒泡排序少；3.2.6缺點：相對之下還是慢。3.3、插入法3.3.1算法要求：用插入排序法對10個整數進行降序排序。3.3.2算法分析：將序列分為有序序列和無序列，依次從無序序列中取出元素值插入到 有序序列的合適位置。初始是有序序列中只有第一個數，其余n-1個數組成無序序列，則n 個數需進n-1次插入。尋找在有序序列中插入位置可以從有序序列的最后一個數往前找，在 未找到插入點之前可以同時向后移動元素，為插入元素準備空間。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優點：穩定，快；3.3.5缺點：比較次數不一定，比較次數越少，插入點后的數據移動越多，特別是當數 據總量龐大的時候，但用鏈表可以解決

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