鄂教版信息技術(shù)九下第9課《程序調(diào)試優(yōu)化算法》教案

1、算法效率與程序優(yōu)化石家莊二中 李博杰在信息學(xué)競(jìng)賽中，常遇到程序運(yùn)行超時(shí)的情況。然而，同一個(gè)程序設(shè)計(jì)思想，用不同算法，會(huì)有不同的運(yùn)行效率；而即使是同樣的算法，由于在代碼的細(xì)節(jié)方面設(shè)計(jì)有所不同，執(zhí)行起來(lái)效率也會(huì)有所不同。當(dāng)遇到所需時(shí)間較長(zhǎng)的問(wèn)題時(shí)，一個(gè)常數(shù)級(jí)優(yōu)化可能是AC的關(guān)鍵所在。下面，我們就從代碼細(xì)節(jié)與算法設(shè)計(jì)兩方面，比較不同程序執(zhí)行時(shí)間的異同，從而選擇其中較優(yōu)的算法，提高程序運(yùn)行效率。本試驗(yàn)所采用的環(huán)境是： CPU Celeron 3.06GHz，內(nèi)存248M，操作系統(tǒng)Windows XP SP2，程序語(yǔ)言C。編譯環(huán)境Dev-c+。以下稱為1號(hào)機(jī)。配置略好于NOIP標(biāo)準(zhǔn)測(cè)試機(jī)CPU 2.0G

2、Hz。第一章 各種運(yùn)算的速度一、基本運(yùn)算的速度為了增強(qiáng)算法效率的計(jì)算準(zhǔn)確性，我們采用重復(fù)試驗(yàn)20次取平均值的做法。每次試驗(yàn)運(yùn)行100000000次。基本運(yùn)行時(shí)間，是指在準(zhǔn)備計(jì)算的運(yùn)算復(fù)雜度之外，只包括循環(huán)控制變量的加減與比較所消耗的時(shí)間。要從實(shí)際運(yùn)行時(shí)間中減去基本運(yùn)行時(shí)間，才是這種運(yùn)算真正的運(yùn)行時(shí)間，稱為凈運(yùn)行時(shí)間。#include<stdio.h>main() int i,j; double a,b,sum=0; for(j=0;j<20;j+) /此處添加隨機(jī)數(shù)產(chǎn)生 a=clock(); for(i=0;i<100000000;i+);/此處添加運(yùn)算 b=clock

3、(); printf("%lfn",b-a); sum+=b-a; printf("ans = %lf",sum/20.0); getch();運(yùn)行平均時(shí)間是：202.3ms。（1）賦值運(yùn)算凈運(yùn)行時(shí)間0.8ms，與基本運(yùn)行時(shí)間202.3ms相比，可忽略不計(jì)，故以后將賦值運(yùn)算作為基本運(yùn)行時(shí)間的一部分，不予考慮。（2）加法運(yùn)算 產(chǎn)生隨機(jī)數(shù)： x=rand();y=rand();循環(huán)內(nèi)加法：t=x+y;下面的各種簡(jiǎn)單運(yùn)算只是更改運(yùn)算符即可，不再寫(xiě)出代碼。凈運(yùn)行時(shí)間41.45ms，即：在1s的時(shí)限中，共可進(jìn)行 (1000-202.3)/ 41.45*108=1.

4、9*109次加法運(yùn)算，即：只通過(guò)循環(huán)、加法和賦值的運(yùn)算次數(shù)不超過(guò)1.9*109.。而應(yīng)用+=運(yùn)算，與普通加法時(shí)間幾乎相同，所以+=只是一種方便書(shū)寫(xiě)的方法，沒(méi)有實(shí)質(zhì)效果。同樣的，各種自運(yùn)算并不能提高效率。（3）減法運(yùn)算 凈運(yùn)行時(shí)間42.95ms，與加法運(yùn)算基本相同?？梢?jiàn)，在計(jì)算機(jī)內(nèi)部實(shí)現(xiàn)中，把減法變成加法的求補(bǔ)碼過(guò)程是較快的，而按位相加的過(guò)程占據(jù)了較多的時(shí)間，借用化學(xué)中的一句術(shù)語(yǔ)，可以稱為整個(gè)運(yùn)算的“速控步”。當(dāng)然，這個(gè)“速控步”的運(yùn)行速度受計(jì)算機(jī)本身制約，我們無(wú)法優(yōu)化。在下面的算法設(shè)計(jì)中，還會(huì)遇到整個(gè)算法的“速控步”，針對(duì)這類情況，我們要對(duì)占用時(shí)間最多的步驟進(jìn)行細(xì)心優(yōu)化，減少常數(shù)級(jí)運(yùn)算次數(shù)。（

5、4）乘法運(yùn)算凈運(yùn)行時(shí)間58.25ms，明顯比加減法要慢，但不像某些人想象的那樣慢，至少速度大于加減法的1/2。所以在實(shí)際編程時(shí)，沒(méi)有必要把兩個(gè)或三個(gè)加法變成乘法，其實(shí)不如元素乘常數(shù)來(lái)得快。不必“談乘色變”，實(shí)際乘法作為CPU的一種基本運(yùn)算，速度還是很快的。以上四種運(yùn)算速度都很快，比循環(huán)所需時(shí)間少很多，在普通的算法中，每個(gè)最內(nèi)層循環(huán)約含有4-5個(gè)加、減、乘運(yùn)算，故整個(gè)算法的運(yùn)行時(shí)間約為循環(huán)本身所需時(shí)間的2倍。（5）除法運(yùn)算凈運(yùn)行時(shí)間1210.2ms，是四種常規(guī)運(yùn)算中最慢的一種，耗時(shí)是加法的28倍，是乘法的21.5倍，確實(shí)如常人所說(shuō)“慢幾十倍”，一秒的時(shí)限內(nèi)只能運(yùn)行8.26*107次，不足一億次，

6、遠(yuǎn)大于循環(huán)時(shí)間。所以，在計(jì)算時(shí)應(yīng)盡量避免除法，尤其是在對(duì)時(shí)間要求較高的內(nèi)層循環(huán)，盡量不安排除法，如果整個(gè)循環(huán)中值不變，可以使用在循環(huán)外預(yù)處理并用一個(gè)變量記錄，循環(huán)內(nèi)再調(diào)用該變量的方法，可以大大提高程序運(yùn)行效率。（6）取模運(yùn)算凈運(yùn)行時(shí)間1178.15ms，與除法運(yùn)算速度幾乎相當(dāng)，都非常慢。所以，取模運(yùn)算也要盡量減少。在大數(shù)運(yùn)算而只要求求得MOD N的值的題目中，應(yīng)盡量利用數(shù)據(jù)類型的最大允許范圍，在保證不超過(guò)MAXINT的前提下，盡量少執(zhí)行MOD運(yùn)算。例如在循環(huán)數(shù)組、循環(huán)隊(duì)列的應(yīng)用中，取模運(yùn)算必不可少，這時(shí)優(yōu)化運(yùn)算便十分重要?？衫糜?jì)數(shù)足夠一定次數(shù)后再統(tǒng)一MOD，循環(huán)完后再M(fèi)OD，使用中間變量記錄

7、MOD結(jié)果等方法減少次數(shù)。在高精度計(jì)算中，許多人喜歡邊運(yùn)算邊整理移位，從而在內(nèi)層循環(huán)中有除、模運(yùn)算各一次，效率極低。應(yīng)該利用int的數(shù)據(jù)范圍，先將計(jì)算結(jié)果保存至當(dāng)前位，在各位的運(yùn)算結(jié)束后再統(tǒng)一整理。以下是用統(tǒng)一整理法編寫(xiě)的高精度乘法函數(shù)，規(guī)模為10000位。int a10000=0,b10000=0,c10000=0;void mul() int i,j,t; for(i=0;i<10000;i+) for(j=0;j<10000-i;j+) ci+j+=ai*bj; for(i=0;i<9999;i+) ci+1+=ci/10; ci%=10; 以上函數(shù)運(yùn)行后，平均用時(shí)27

8、6.55ms。以下是邊運(yùn)算邊整理的程序。void mul() int i,j,t; for(i=0;i<10000;i+) for(j=0;j<10000-i;j+) ci+j+1+=(ci+j+ai*bj)/10; ci+j=(ci+j+ai*bj)%10; 以上函數(shù)運(yùn)行后，平均用時(shí)882.80ms。統(tǒng)一整理與邊整理邊移位相比，快了3.2倍，有明顯優(yōu)勢(shì)。故盡量減少除法、取模運(yùn)算的次數(shù)，是從常數(shù)級(jí)別降低時(shí)間復(fù)雜度的方法。（7）大小比較if(x>y) x=y;凈運(yùn)行時(shí)間39.1ms，與加法運(yùn)算速度相當(dāng)。故比較運(yùn)算也屬于較快的基本運(yùn)算。二、位運(yùn)算的速度（1）左移、右移x<&

9、lt;1; x>>1;凈運(yùn)行時(shí)間無(wú)法測(cè)出，證明位運(yùn)算速度極快。而使用自乘計(jì)算需要64.1ms，自除運(yùn)算需要164.85ms，所以盡可能使用位運(yùn)算代替乘除。（2）邏輯運(yùn)算t=x|y; t=xy; t=x&y;凈運(yùn)行時(shí)間約30ms，比加法運(yùn)算（約40ms）快較多，是因?yàn)槿前炊M(jìn)制位計(jì)算。但加減與位運(yùn)算關(guān)系并不大，所以利用位運(yùn)算主要是利用左右移位的高速度。三、數(shù)組運(yùn)算的速度（1）直接應(yīng)用數(shù)組for(i=0;i<10000;i+) for(k=0;k<10000;k+) t=qk;凈運(yùn)行時(shí)間39.85ms。這里計(jì)算了內(nèi)層循環(huán)的時(shí)間。若改為for(i=0;i<10

10、0000000;i+) t=q0;則凈運(yùn)行時(shí)間為1.50ms，很快，與202.3ms的循環(huán)時(shí)間相比，可以忽略。故應(yīng)用數(shù)組，速度很快，不必?fù)?dān)心數(shù)組尋址耗時(shí)。同時(shí)我們發(fā)現(xiàn)，循環(huán)耗時(shí)在各種運(yùn)算中是很大的，僅次于乘除，故我們要盡量減少循環(huán)次數(shù)，能在一個(gè)循環(huán)中解決的問(wèn)題不放在兩個(gè)循環(huán)中，減少循環(huán)變量次數(shù)。（2）二維數(shù)組for(i=0;i<5000;i+) for(k=0;k<5000;k+) t=zik;實(shí)際運(yùn)行時(shí)間為80.45ms，若規(guī)模擴(kuò)至10000則10s內(nèi)無(wú)法出解，由于頻繁訪問(wèn)虛擬內(nèi)存?？梢栽囅?，若物理內(nèi)存足夠大，則運(yùn)行時(shí)間約為320ms，僅為202.3ms的基準(zhǔn)運(yùn)行時(shí)間的3/2，差

11、距似乎并不是很大；由此推得其凈運(yùn)行時(shí)間約為120ms。但相較加、減等簡(jiǎn)單操作，速度仍為3倍，尤其與幾乎不需時(shí)間的一維數(shù)組相比差距巨大。尤其是在計(jì)算中，二維數(shù)組元素經(jīng)常調(diào)用，時(shí)間效率不可忽視。所以，對(duì)于已知數(shù)目不多的同樣大小的數(shù)組，可用幾個(gè)變量名不同的一維數(shù)組表示，如x、y方向，兩種不同參數(shù)，而不要濫用二維數(shù)組。在滾動(dòng)數(shù)組中，可用兩個(gè)數(shù)組交替計(jì)算的方式，用二維數(shù)組同樣較慢。四、實(shí)數(shù)運(yùn)算的速度測(cè)試方法與“基本運(yùn)算”類似。（次數(shù)：100000000，單位：ms）運(yùn)算符=+-*/%long int43.0531.3-74.7569.55299.65360.5int6441.4514.957.9566.

12、41243.451858.85double46.1510.2512.633.651753.55-由上表可見(jiàn)，涉及乘除、取模時(shí)int64很慢，要慎用；int顯然最快，但對(duì)大數(shù)據(jù)要小心越界。若一組變量中既有超出int的，又有不超過(guò)int的，則要分類處理，不要直接都定義成int64，尤其在乘除模較多的高精度過(guò)程中。以上討論了主要基本運(yùn)算的速度問(wèn)題。概括起來(lái)說(shuō)，除、模最慢，二維數(shù)組較慢，加減乘、邏輯位運(yùn)算、比較大小較快，左右移位、一維數(shù)組、賦值幾乎不需要時(shí)間。而循環(huán)for或while語(yǔ)句十分特殊，它的運(yùn)算速度大于判斷大小、自加控制變量所用時(shí)間之和，無(wú)論采用內(nèi)部if判斷退出，還是在入口處判斷，都回用去約

13、200ms的時(shí)間。所以盡量減少循環(huán)次數(shù)，是優(yōu)化算法的關(guān)鍵。對(duì)于雙層或多層的循環(huán)，應(yīng)把循環(huán)次數(shù)少的放在最外層，最大的循環(huán)位居最內(nèi)部，以減少內(nèi)層循環(huán)的執(zhí)行次數(shù)。第二章 各種算法的速度一、排序算法的速度1.冒泡排序for(i=0;i<20000;i+) ai=rand();s=clock();for(i=0;i<n;i+) for(j=0;j<i;j+) if(ai>aj) t=ai; ai=aj; aj=t; b=clock();運(yùn)行時(shí)間：1407ms2.選擇排序for(i=0;i<20000;i+) ai=rand(); s=clock(); for(i=0;i&l

14、t;n;i+) max=0; for(j=0;j<n;j+) if(aj>amax) max=j; bi=amax; amax=-1000000; t=clock();運(yùn)行時(shí)間：1220ms3.插入排序for(i=0;i<20000;i+) ai=rand(); s=clock(); for(i=0;i<n;i+) t=ai; for(j=i-1;j>=0;j-) if(aj>t) break; for(l=i;l>j+1;l-) al=al-1; aj+1=t; t=clock();運(yùn)行時(shí)間：984ms以上三種都是O(n2)的排序，其中插入排序最快，

15、且可以用指針加以優(yōu)化。從編程復(fù)雜度上，冒泡排序最簡(jiǎn)單。從算法的穩(wěn)定性上，插入排序是穩(wěn)定的，即排序后關(guān)鍵字相同的記錄順序不改變，特別適用于表達(dá)式處理等問(wèn)題。一般的選擇排序是不穩(wěn)定的，但這里給出的程序由于使用了人類最原始的方法，即依次選擇最大的并排除，故是穩(wěn)定的。冒泡排序是不穩(wěn)定的，涉及必須保持?jǐn)?shù)據(jù)原順序的題目時(shí)不能選擇冒泡排序，而必須選擇穩(wěn)定的排序方式。以下試驗(yàn)所采用的環(huán)境是： CPU Intel Core 1.73GHz*2，內(nèi)存512M，操作系統(tǒng)Windows 7 Ultimate Beta，程序語(yǔ)言C。編譯環(huán)境Dev-c+，以下稱為2號(hào)機(jī)。由于CPU速度較慢，且操作系統(tǒng)占用資源較多，程序運(yùn)

16、行速度明顯減慢，第一章的“基本運(yùn)行測(cè)試”需要時(shí)間約為前者的2倍，即為406ms。故第一章的程序運(yùn)行時(shí)間此處應(yīng)乘2。4.快速排序的標(biāo)準(zhǔn)版#define MAX 10000000int aMAX;int p(int l,int r) int x=al,i=l-1,j=r+1,t; while(1) do-j; while(aj<x); do+i; while(ai>x); if(i<j) t=ai;ai=aj;aj=t; else return j; void q(int l,int r) int n; if(l<r) n=p(l,r); q(l,n); q(n+1,r);

17、 運(yùn)行時(shí)間：2948ms。注意：不要以為三種平方級(jí)排序方法的速度與快速排序可比擬，因?yàn)槠椒郊?jí)的數(shù)據(jù)范圍是10000，而快速排序的范圍是10000000。對(duì)于10000的數(shù)據(jù)，快速排序只需3.1ms。另外，快速排序不是穩(wěn)定的排序，需要保持原順序的不能用此法。void p(int l,int r) int x=al,i=l-1,j=r+1,t; if(l<r) while(1) do-j; while(aj<x); do+i; while(ai>x); if(i<j) t=ai;ai=aj;aj=t; else break; p(l,j); p(j+1,r); 若程序改為以

18、上形式，則運(yùn)行時(shí)間為2917ms，稍快了一些，是因?yàn)闇p少了函數(shù)調(diào)用次數(shù)。對(duì)于函數(shù)調(diào)用，我們進(jìn)行這樣的測(cè)試。s=clock();for(i=0;i<100000000;i+) test();t=clock();int test() int n; n+;凈運(yùn)行時(shí)間200msint test() int n;凈運(yùn)行時(shí)間84msint test()凈運(yùn)行時(shí)間10ms由此可見(jiàn)，調(diào)用函數(shù)本身并不浪費(fèi)時(shí)間，僅相當(dāng)于循環(huán)本身時(shí)間400ms的1/40，相當(dāng)于加法80ms的1/8，是很快的運(yùn)算。但由于在函數(shù)內(nèi)部需要進(jìn)行現(xiàn)場(chǎng)保護(hù)，調(diào)用系統(tǒng)堆棧，所以用時(shí)大幅增加，定義變量后只是一個(gè)自增運(yùn)算就用去120ms，相當(dāng)

19、于主程序中加法運(yùn)算時(shí)間的3/2倍。故函數(shù)中的運(yùn)算比主程序中要慢，尤其是反復(fù)調(diào)用函數(shù)，會(huì)增加不必要的時(shí)間開(kāi)銷。所以，一些簡(jiǎn)單的功能盡量在一個(gè)函數(shù)或主程序內(nèi)完成，不要使用過(guò)多的函數(shù)；涉及全局的變量不要在函數(shù)調(diào)用時(shí)由接口給出，再返回值，盡量使用全局變量。這些方法可能使程序的可讀性降低，不利于調(diào)試，但有利于提高時(shí)效，正如匯編語(yǔ)言程序比高級(jí)語(yǔ)言快一樣。5.優(yōu)化的快速排序（1）用插入排序優(yōu)化由于遞歸調(diào)用浪費(fèi)大量時(shí)間，本算法的思想是，當(dāng)首尾間距小于min時(shí)，改用效率較高的插入排序，減少反復(fù)遞歸。這個(gè)想法是好的，但運(yùn)行效果并不如人意。當(dāng)min=4時(shí)，程序運(yùn)行時(shí)間降為2901ms，優(yōu)化幅度不大，且增加了編程復(fù)雜

20、度，故不宜采用。其原因是遞歸調(diào)用、插入排序內(nèi)部循環(huán)所用時(shí)間過(guò)長(zhǎng)。（2）用小數(shù)據(jù)判斷優(yōu)化 if(l+1<r) while(1)/與普通快速排序相同 else if(l+1=r&&al<ar) t=ai;ai=aj;aj=t;僅就區(qū)間長(zhǎng)度為2的情況進(jìn)行判斷優(yōu)化，減少一次遞歸調(diào)用，就能使運(yùn)行時(shí)間縮短為2699ms，降低了200ms以上。而區(qū)間長(zhǎng)度不小于3的直接判斷有困難?？焖倥判蜻\(yùn)行時(shí)間（單位：ms）數(shù)據(jù)規(guī)模10000100000100000010000000原始快速排序1.5025.20258.552716.45優(yōu)化快速排序2.3023.40245.402564.806

21、.歸并排序歸并排序是一種穩(wěn)定的排序方法，且時(shí)間效率與快速排序相同，都是O(nlogn)。但歸并排序比快速排序的常數(shù)因子大，故快速排序還是最快的排序方法。歸并排序則適用于有特殊要求的題目，如不滿足交換律的表達(dá)式處理。int aMAX,bMAX;void combine(int from,int to) int i,t,mid=(from+to)/2,f,r; if(from=to|from+1=to) return; if(from+2=to) if(afrom<afrom+1) t=afrom; afrom=afrom+1; afrom+1=t; return; combine(from

22、,mid); combine(mid,to); f=from; r=mid; i=from; while(f!=mid|r!=to) if(f!=mid&&af>ar) bi+=af+; else bi+=ar+; for(i=from;i<to;i+) ai=bi; 調(diào)用：combine(0,MAX);歸并排序算法還可用于統(tǒng)計(jì)逆序?qū)?shù)。所謂逆序?qū)?，即為在一個(gè)數(shù)組a中，滿足i<j且ai>aj（或ai<aj，依排序方向而定）的點(diǎn)(i,j)的個(gè)數(shù)。void sort(int from,int to) int i,t,mid=(from+to)/2,f,

23、r; if(from=to|from+1=to) return; if(from+2=to) if(afrom<afrom+1) t=afrom; afrom=afrom+1; afrom+1=t; tot+; return; sort(from,mid); sort(mid,to); f=from; r=mid; i=from; while(f!=mid|r!=to) if(f!=mid&&af>ar) bi+=af+; else bi+=ar+; if(f!=mid) tot+=(mid-from); for(i=from;i<to;i+) ai=bi;

24、主函數(shù)： sort(0,n); printf("%d",n*(n-1)/2-tot);7.多關(guān)鍵字排序多關(guān)鍵字排序，經(jīng)常出現(xiàn)于要求按某要素排序姓名，該要素相同的按字典序排列的題目。這樣，此要素是第一關(guān)鍵字，姓名是第二關(guān)鍵字。qist(0,n-1);j=0;for(i=1;i<n;i+) if(istloi!=istloi-1) qnameist(j,i-1); j=i; qnameist(j,n-1);此算法的意思是，先按第一關(guān)鍵字快速排序，在從左至右掃描，找到每段相同的元素，再按第二關(guān)鍵字快速排序。此算法復(fù)雜度仍為O(nlogn)，且比兩次快速排序要快，因?yàn)榈诙闻?/p>

25、序已用O(n)的時(shí)間將其分為若干小塊，排序效率大大提高。8.字符串排序void qname(int l,int r) int i=l-1,j=r+1,t; while(1) do-j; while(strcmp(nameloj,nameloi)>0); do+i; while(strcmp(nameloj,nameloi)<0); if(i<j) t=loi;loi=loj;loj=t; else break; if(l<r) qname(l,j); qname(j+1,r);上述排序方法，實(shí)質(zhì)上是將普通快速排序中的數(shù)大小比較換成字符串大小比較。為了避免字符串交換浪費(fèi)時(shí)

26、間，采用了類似指針的定位數(shù)組，只需交換定位數(shù)組的元素即可。當(dāng)然，用指針直接實(shí)現(xiàn)效率更高。關(guān)于字符串比較函數(shù)strcmp的時(shí)間效率，我們有如下試驗(yàn)：for(i=0;i<100;i+) ai=rand(); bi=rand();s=clock();for(i=0;i<100000000;i+) if(strcmp(a,b)=0) break;t=clock();運(yùn)行時(shí)間：1046ms，其中凈運(yùn)行時(shí)間約640ms。這是對(duì)長(zhǎng)度100的字符串進(jìn)行108次比較的時(shí)間。故strcmp的效率即為約8次整數(shù)比較所需時(shí)間，比自己編寫(xiě)的函數(shù)快。int str(char a,char b) int i=0

27、; while(ai!=0|bi!=0) if(ai>bi) return 1; if(ai<bi) return -1; return 0; 運(yùn)行時(shí)間：1131ms，凈運(yùn)行時(shí)間約725ms，相當(dāng)于9次整數(shù)比較時(shí)間，比標(biāo)準(zhǔn)庫(kù)函數(shù)稍慢。顯然，標(biāo)準(zhǔn)庫(kù)函數(shù)是經(jīng)過(guò)精心優(yōu)化的，我們?cè)谟袔?kù)函數(shù)可用時(shí)盡量用庫(kù)函數(shù)，不僅降低編程復(fù)雜度，降低錯(cuò)誤率，還能提高時(shí)間效率。9.Hash排序#define MOD 999997/As a big prime#define MAX 10000/As the max length of the stringint ELFhash(char *key) unsig

28、ned long h=0; while(*key) h=(h<<4)+*key+; unsigned long g=h&0Xf0000000L; if(g) h=g>>24; h&=g; return h%MOD;Hash排序，就是先對(duì)讀入的字符串求Hash值。第一種方案是，再對(duì)Hash值進(jìn)行快速排序，最后應(yīng)用二分搜索查找。此時(shí)無(wú)需MOD大質(zhì)數(shù)。第二種方案是，將Hash值MOD后，放入Hash表中，并用開(kāi)散列等方法處理沖突。顯然，第二種方案更優(yōu)，但編程復(fù)雜度也較高。綜上所述，在選擇適當(dāng)?shù)呐判蛩惴〞r(shí)，要注意時(shí)間復(fù)雜度和編程復(fù)雜度，同時(shí)保證滿足題意。二、最短

29、路算法的比較在圖論中，最短路算法是常見(jiàn)的。對(duì)于常見(jiàn)的幾種算法，到底哪種更優(yōu)，還是各有千秋？我們不妨一試。以下實(shí)驗(yàn)在1號(hào)機(jī)上進(jìn)行，均為試驗(yàn)20次隨機(jī)數(shù)取平均值的結(jié)果。1.單源最短路徑dijkstra算法void dijkstra() int i,j,min=0; for(i=0;i<n;i+) disi=d0i; for(i=1;i<n;i+) min=n; for(j=0;j<n;j+) if(!usej&&dij<dimin) min=j; usemin=1; for(j=0;j<n;j+) if(dismin+dminj<disj) di

30、sj=dismin+dminj; 隨機(jī)數(shù)產(chǎn)生器：for(i=0;i<MAX;i+) for(j=0;j<MAX;j+) if(i!=j) dij=rand();當(dāng)MAX=2000時(shí)（即點(diǎn)數(shù)為2000個(gè)），運(yùn)行時(shí)間：28.2ms。當(dāng)MAX更大時(shí)，內(nèi)存會(huì)使用過(guò)多，故在1s時(shí)限內(nèi)至多運(yùn)行規(guī)模為2000的單源最短路徑35次。2.單源最短路徑Ford算法int ford() int i,j; for(i=1;i<n;i+) di=MAXINT; for(i=1;i<n;i+) for(j=0;j<num;j+) if(dfj+wj<dej) dej=dfj+wj; f

31、or(j=0;j<num;j+) if(dfj+wj<dej) return 0; return 1; 數(shù)據(jù)構(gòu)造：10*n條隨機(jī)邊。當(dāng)n=1000時(shí)，運(yùn)行時(shí)間：49.95ms。當(dāng)n=10000時(shí)，運(yùn)行時(shí)間：6766ms。數(shù)據(jù)構(gòu)造：n*n條邊的完全圖。當(dāng)n=1000時(shí)，運(yùn)行時(shí)間6469ms。比Dijkstra和SPFA都慢很多，因?yàn)槠渌惴ǖ睦碚摃r(shí)間復(fù)雜度就達(dá)到了O(VE)，屬于介于O(n2)與O(n3)的算法。但我們?nèi)匀恍枰@種算法，因?yàn)楫?dāng)圖中存在負(fù)權(quán)時(shí)，必須使用Ford算法。同時(shí)，該算法還能判斷圖中是否存在負(fù)權(quán)回路（無(wú)解）。3.單源最短路徑SPFA算法struct mising i

32、nt num; int poo; struct mising *p; ;int wor500000;int dis60001;int yes60001=0;int beg=0,end=1;main() int n,m; int a,b,c,i; struct mising q60001,*qq60001,*x; double s,t; FILE *fp; fp=fopen("1.txt","r"); fscanf(fp,"%d%d",&n,&m); for(i=0;i<n;i+) qqi=&qi; for

33、(i=0;i<m;i+) fscanf(fp,"%d%d%d",&a,&b,&c); a-; b-; qqa->p=(struct mising *)malloc(sizeof(struct mising); qqb->p=(struct mising *)malloc(sizeof(struct mising); qqa=qqa->p; qqb=qqb->p; qqa->poo=b; qqb->poo=a; qqa->num=qqb->num=c; s=clock(); for(i=0;i<

34、;n;i+) qqi->p=NULL; disi=-1; yes0=1; wor0=0; dis0=0; while(beg!=end) x=qworbeg.p; while(x!=NULL) if(disx->poo=-1|(disx->poo>x->num+disworbeg&&disx->poo!=-1) disx->poo=disworbeg+x->num; worend=x->poo; if(yesx->poo=0) yesx->poo=1; end+; x=x->p; yesworbeg=0;

35、beg+; printf("%d",disn-1); t=clock();隨機(jī)數(shù)生成模塊： fprintf(fp,"%d %dn",n,10*n); for(i=0;i<10*n;i+) j=rand()%n+1; k=rand()%n+1; while(j=k) j=rand()%n+1; k=rand()%n+1; fprintf(fp,"%d %d %dn",j,k,rand(); 運(yùn)行時(shí)間（不含文件操作）：當(dāng)n=100000時(shí)，運(yùn)行時(shí)間1937ms；當(dāng)n=10000時(shí)，運(yùn)行時(shí)間141ms；當(dāng)n=1000時(shí)，運(yùn)行時(shí)間小于1

36、0ms。特別需要注意的是，當(dāng)n=50000時(shí)，用時(shí)828ms，再加上文件操作用時(shí)，可稱為是SPFA算法數(shù)據(jù)規(guī)模的上限。這組數(shù)據(jù)是n個(gè)點(diǎn)，10*n條隨機(jī)邊的情況下作出的。若使用O(n2)的Dijkstra算法，時(shí)間將大幅增加。對(duì)于單源最短路徑，要考慮題意要求，稀疏圖使用SPFA，密集圖使用Dijkstra，以提高運(yùn)行效率。3.點(diǎn)對(duì)點(diǎn)最短路徑Floyed算法void floyed() int i,j,k,min=0; for(k=0;k<n;k+) for(i=0;i<n;i+) for(j=0;j<n;j+) if(dik+dkj<dij) dij=dik+dkj;當(dāng)MA

37、X=500時(shí)，運(yùn)行時(shí)間：979.85ms。這提示我們，點(diǎn)對(duì)點(diǎn)最短路徑的規(guī)模最大為500，否則會(huì)超時(shí)。若使用MAX-1次dijkstra算法void dijkstra() int i,j,k,min=0; for(k=0;k<n-1;k+) int useMAX=0; for(i=0;i<n;i+) disi=dki; for(i=1;i<n;i+) min=n; for(j=0;j<n;j+) if(!usej&&dij<dimin) min=j; usemin=1; for(j=0;j<n;j+) if(dismin+dminj<di

38、sj) disj=dismin+dminj; 當(dāng)MAX=500時(shí)，運(yùn)行時(shí)間：1625ms，與floyed的980ms相比，顯然慢了很多。因此，floyed算法是點(diǎn)對(duì)點(diǎn)最短路徑的“正統(tǒng)”算法。三、字符串匹配算法的比較1.樸素匹配算法for(i=0;i<1000;i+) Si=1; for(j=0;j<100000;j+) Tj=1; s=clock(); tot=0; ls=strlen(S); lt=strlen(T); for(i=0;i<lt-ls;i+) for(j=0;j<ls;j+) if(Ti+j!=Sj) break; if(j=ls) tot+; pri

39、ntf("%d ",tot); t=clock();運(yùn)行時(shí)間：335.35ms。這組測(cè)試數(shù)據(jù)是：原串100000個(gè)1，匹配串1000個(gè)1.若使用更極端的數(shù)據(jù)，如匹配串10000個(gè)1，則需要數(shù)秒出解，顯然過(guò)慢。對(duì)于隨機(jī)數(shù)據(jù)，由于匹配的可能性極小，用時(shí)很快是必然的。我們只考慮極端數(shù)據(jù)。2.KMP算法（優(yōu)化）int KMP() int i,q=0; for(i=1;i<=ls;i+) while(q>0&&Tq+1!=Si) q=nextq; if(Tq+1=Si) q+; if(q=lt) atot+=i-lt+1; void ff() int q,

40、k; for(q=1;q<=lt;q+) k=nextq; while(k>0&&Tk+1=Tq+1) k=nextk; nextq=k; void f() int q,k; next1=0;k=0; for(q=2;q<=lt;q+) while(k>0&&Tk+1!=Tq) k=nextk; if(Tk+1=Tq) k=k+1; nextq=k; 調(diào)用過(guò)程： f(); ff(); KMP();算法說(shuō)明：函數(shù)f計(jì)算初始“回復(fù)位置”，函數(shù)ff計(jì)算優(yōu)化后的“回復(fù)位置”，函數(shù)KMP是依賴上述“回復(fù)位置”進(jìn)行快速匹配的算法。Si為待匹配串，Ti

41、為目標(biāo)串，nexti計(jì)算“回復(fù)位置”。運(yùn)行時(shí)間：當(dāng)目標(biāo)串長(zhǎng)1000，匹配串長(zhǎng)100000時(shí)0.8ms。目標(biāo)串長(zhǎng)100時(shí)2.3ms。目標(biāo)串長(zhǎng)10或10000時(shí)，運(yùn)行時(shí)間1.55ms?？梢?jiàn)，KMP算法極快，確實(shí)是O(n)的時(shí)間復(fù)雜度。故正確的優(yōu)化KMP算法是不會(huì)超時(shí)的。同樣，優(yōu)化KMP與普通KMP的差距也很明顯，尤其是在極端數(shù)據(jù)時(shí)。四、最小生成樹(shù)算法的比較1.Prim算法void prim() int lowcost2002,closet2002,i,j,k,min,tot=0; for(i=1;i<=n;i+) lowcosti=cost1i; closeti=1; for(i=1;i&l

42、t;n;i+) min=MAXINT; for(j=1;j<=n;j+) if(lowcostj<min&&lowcostj!=0) min=lowcostj; k=j; tot+=lowcostk; lowcostk=0; for(j=1;j<=n;j+) if(costkj<lowcostj) lowcostj=costkj; closetj=k; printf("%d ",tot);隨機(jī)數(shù)生成：for(i=1;i<=MAX;i+) for(j=1;j<=MAX;j+) if(i!=j) costij=rand();當(dāng)

43、數(shù)據(jù)范圍MAX=2000時(shí)，平均運(yùn)行時(shí)間：46.95ms。 由于Prim算法是O(n2)的，速度快不是偶然。由此可見(jiàn)，最小生成樹(shù)不是程序運(yùn)行時(shí)間的瓶頸。從算法上看，我們注意到Prim算法十分類似求單源最短路徑的Dijkstra算法。兩種算法都是先找出不在集合中的最近元素，將其加入集合，并對(duì)該元素連接的點(diǎn)進(jìn)行松弛操作，更新各點(diǎn)到集合的距離。在具體實(shí)現(xiàn)中，都是利用一個(gè)數(shù)組記錄每個(gè)點(diǎn)到集合的距離，點(diǎn)在集合中用距離為零表示。2.Kruskal算法（較差）int father(int x) if(setx!=x) setx=father(setx); return setx;void kruskal()

44、 int i,j,start,end,value,cost=0; for(i=0;i<n;i+) seti=i; for(k=1;k<n;k+) value=MAXINT; for(i=0;i<n;i+) for(j=0;j<n;j+) if(i!=j&&father(i)!=father(j) if(dataij<value) start=i; end=j; value=dataij; cost+=value; setfather(start)=father(end); printf("%d ",cost);當(dāng)規(guī)模MAX=50

45、0時(shí)，運(yùn)行時(shí)間：3563ms。顯然，當(dāng)圖為密集矩陣時(shí)，Kruskal算法并不迅速。但當(dāng)圖為稀疏圖時(shí)，算法的優(yōu)勢(shì)便很明顯了。3.Kruskal算法（優(yōu)化）int find(int x) if(fx!=x) fx=find(fx); return fx;void kruskal() int i,j,a,b,tot=0,num=0; for(i=0;i<n;i+) fi=i; for(i=0;i<n;i+) a=find(si); b=find(ei); if(a!=b) num+; tot+=wi; fa=b; if(num=max) break; printf("%d &q

46、uot;,tot);主程序：for(i=1;i<n;i+) fi=rand()%max; ei=rand()%max; wi=rand(); s=clock(); sort(0,n-1); kruskal(); t=clock();此處sort函數(shù)是快速排序函數(shù)，采用了本文上述“優(yōu)化的快速排序算法”。當(dāng)max=100000時(shí)，即共100000個(gè)點(diǎn)，共1000000條邊時(shí)，平均運(yùn)行時(shí)間為409.4ms。當(dāng)max=10000時(shí)，平均運(yùn)行時(shí)間為43.7ms。完全滿足時(shí)限1s的要求。而若使用O(n2)的Prim算法，運(yùn)行時(shí)間將不可思議。故Kruskal算法十分適合稀疏圖的處理。我們?cè)賮?lái)看Krus

47、kal算法對(duì)于密集圖的效率。for(i=0;i<max;i+) for(j=0;j<max;j+) fi=i; ei=j; wi=rand(); 當(dāng)max=2000時(shí)，平均運(yùn)行時(shí)間1394.5ms，比Prim的47ms慢了約30倍。通過(guò)單獨(dú)測(cè)試sort時(shí)間可知，當(dāng)數(shù)目過(guò)多時(shí)，快速排序占去很多的時(shí)間（平均1299.3ms），而Kruskal算法本身仍然很快（不到100ms）。綜上所述，在解題前，務(wù)必看清題中給出的圖是密集圖還是稀疏圖，并選擇合適的算法，否則程序運(yùn)行速度會(huì)很慢。五、拓?fù)渑判蛩惴╥nt tuopu() int i,j,k; for(i=0;i<n;i+) for(j

48、=0;j<n;j+) if(aij) dj+; for(i=0;i<n;i+) for(j=0;j<n;j+) if(dj=0) break; if(j=n) return 0; dj=-1; ansi=j; for(k=0;k<n;k+) if(ajk) ajk=0; dk-; return 1;取隨機(jī)數(shù)據(jù)測(cè)試：當(dāng)n=1000時(shí)，運(yùn)行時(shí)間：15ms；當(dāng)n=2000時(shí)，運(yùn)行時(shí)間：63ms。當(dāng)n過(guò)大時(shí)，數(shù)組將越界。六、搜索算法的比較1.樸素深度優(yōu)先搜索程序框架：（函數(shù)依具體題目而定）void op(int now)void read()void print()void printerror()int ans(int now)int s(int now) int i,flag; if(now=n) if(ans(now) return 1; return 0; for(i=0;i<n;i+) op(i); flag=s(