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

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

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

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

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

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

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

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

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

10、）3.1.1算法要求：用起泡法對(duì)10個(gè)整數(shù)按升序排序。3.1.2算法分析：如果有n個(gè)數(shù)，則要進(jìn)行n-1趟比較。在第1趟比較中要進(jìn)行n-1次 相鄰元素的兩兩比較，在第j趟比較中要進(jìn)行n-j次兩兩比較。比較的順序從前往后，經(jīng)過(guò) 一趟比較后，將最值沉底（換到最后一個(gè)元素位置），最大值沉底為升序，最小值沉底為降 序。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個(gè)數(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算法特點(diǎn)：相鄰元素兩兩比較，每趟將最值沉底即可確定一個(gè)數(shù)在結(jié)果的位置， 確定元素位置的順序是從后往前，其余元素可能作相對(duì)位置的調(diào)整?？梢赃M(jìn)行升序或降序排 序。3.1.5優(yōu)點(diǎn)：穩(wěn)定，比較次數(shù)已知；3.1.6缺點(diǎn)：慢，每次只能移動(dòng)相鄰兩個(gè)數(shù)據(jù)，移動(dòng)數(shù)據(jù)的次數(shù)多。3.2、選擇法3.2.1算法要求：用選擇法對(duì)10個(gè)整

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

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

14、降序排序或升序排 序。3.2.5優(yōu)點(diǎn)：穩(wěn)定，比較次數(shù)與冒泡排序一樣，數(shù)據(jù)移動(dòng)次數(shù)比冒泡排序少；3.2.6缺點(diǎn)：相對(duì)之下還是慢。3.3、插入法3.3.1算法要求：用插入排序法對(duì)10個(gè)整數(shù)進(jìn)行降序排序。3.3.2算法分析：將序列分為有序序列和無(wú)序列，依次從無(wú)序序列中取出元素值插入到 有序序列的合適位置。初始是有序序列中只有第一個(gè)數(shù)，其余n-1個(gè)數(shù)組成無(wú)序序列，則n 個(gè)數(shù)需進(jìn)n-1次插入。尋找在有序序列中插入位置可以從有序序列的最后一個(gè)數(shù)往前找，在 未找到插入點(diǎn)之前可以同時(shí)向后移動(dòng)元素，為插入元素準(zhǔn)備空間。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- ) /*在有序序列(下標(biāo)0i-1)中尋找插入位置*/ aj+1=aj;/*若未找到插入位置，則當(dāng)前元素后移一個(gè)位置*/aj+1=t;/*找到插入位置，完成插入*/printf(The sorted numbers:);for(i=0;i10;i+)printf(%d ,ai);printf(n);3.3.4優(yōu)點(diǎn)：穩(wěn)定，快；3.3.5缺點(diǎn)：比較次數(shù)不一定，比較次數(shù)越少，插入點(diǎn)后的數(shù)據(jù)移動(dòng)越多，特別是當(dāng)數(shù) 據(jù)總量龐大的時(shí)候，但用鏈表可以解決

16、這個(gè)問(wèn)題。對(duì)幾種排序算法的復(fù)雜性分析做成如下表格類(lèi)別排序方法時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性平均情況最好情況最壞情況輔助存儲(chǔ)插入排序直接插入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ù)排序的復(fù)雜度中，r代表關(guān)鍵字的基數(shù)，d代表長(zhǎng)度，n代表關(guān)鍵字的個(gè)數(shù)總結(jié)算法分析是對(duì)一個(gè)算法需要多少計(jì)算時(shí)間和存儲(chǔ)空間作定量的分析。算法(Algorithm) 是解