淺談程序設(shè)計(jì)中的算法優(yōu)化

田效宇

摘要

算法一直都是計(jì)算機(jī)學(xué)科中處于核心地位的基礎(chǔ)課程。對于計(jì)算機(jī)學(xué)生而言，讀懂算法、設(shè)計(jì)算法是一項(xiàng)基本要求，而懂得如何設(shè)計(jì)優(yōu)化算法則是最高境界。如果一個(gè)算法所需執(zhí)行時(shí)間過長，那么這個(gè)算法也將失去存在的意義。所以進(jìn)行算法優(yōu)化變得至關(guān)重要。本文著重討論算法及算法優(yōu)化，討論算法所用代碼均為c語言實(shí)現(xiàn)，所用IDE為DEV-C++。

【關(guān)鍵詞】算法 算法優(yōu)化

1 算法設(shè)計(jì)的概念

如果我們要外出旅游，那么我們會(huì)做出詳細(xì)的計(jì)劃：規(guī)劃路線、規(guī)劃開銷、規(guī)劃時(shí)間;如果我們要寫一篇文章，那么我們會(huì)寫出對應(yīng)的綱要。這些就是生活中的算法。

而程序設(shè)計(jì)中的算法，非形式地說，算法（algorithm）就是任何良定義的計(jì)算過程，該過程取某個(gè)值或值的集合作為輸入并產(chǎn)生某個(gè)值或值的集合作為輸出。這樣算法就是把輸入轉(zhuǎn)換成輸出的計(jì)算步驟的一個(gè)序列。

我們也可以把算法看成是用于求解良說明的計(jì)算問題的工具。一般來說，問題陳述說明了期望的輸入/輸出關(guān)系。算法則描述一個(gè)特定的計(jì)算過程來實(shí)現(xiàn)該輸入/輸出關(guān)系[1]。那么程序設(shè)計(jì)中的算法是什么樣子的呢？

例1：計(jì)算1*2*3*……*9。如圖1所示。

分析：要求求1至9的乘積，那么可以設(shè)置一個(gè)變量a，初值為1，遍歷1至9，使每一個(gè)數(shù)字都與a相乘并賦值到a中，即先計(jì)算a=a*1，再計(jì)算a=a*2……直到計(jì)算a=a*9。

算法代碼：

for（i=1;i<=9;i++）

a=a*i;

這就是一個(gè)很典型的算法。由上述例子可以看出，在程序設(shè)計(jì)中算法才是解決問題的靈魂，而如何設(shè)計(jì)一個(gè)好的算法，是程序設(shè)計(jì)中的重點(diǎn)與難點(diǎn)。

在實(shí)際應(yīng)用中，為了追求經(jīng)濟(jì)效益最大化，我們一般討論完成算法所需的時(shí)間長短。衡量算法效率的方法主要有兩類：事后統(tǒng)計(jì)法與事前分析估計(jì)法。事后統(tǒng)計(jì)法的缺陷非常明顯這里不詳述。因此我們采用事前分析估計(jì)法，通過計(jì)算算法的漸近復(fù)雜度來衡量算法的效率。

事前分析估計(jì)法中有三個(gè)重要概念：問圖題規(guī)模、語句頻度、基本語句。問題規(guī)模是算法求解問題的輸入量的多少，語句頻度是一條語句的重復(fù)執(zhí)行次數(shù)，基本語句指的是算法中重復(fù)執(zhí)行次數(shù)與算法的執(zhí)行時(shí)間成正比的語句。

一般情況下，算法中基本語句重復(fù)執(zhí)行次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f（n），算法的時(shí)間量度記作：T（n）=O（f（n））.它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和f（n）的增長率相同，稱作算法的漸近時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度[2]。

2 設(shè)計(jì)算法

在實(shí)際生活應(yīng)用中，大多數(shù)情況需要解決的問題不會(huì)提供相應(yīng)的算法，即需要我們自己去設(shè)計(jì)算法。

例2.1 ：計(jì)算1+3+5+……+99。

分析：如果題目要求的是1至100相加求和，那么可以遍歷1至100將每一個(gè)數(shù)累加到一個(gè)變量中。但是觀察題目，每兩個(gè)數(shù)相差2，即求100以內(nèi)奇數(shù)的和，那么在遍歷中增加一個(gè)條件判斷即可。設(shè)置X=0，變量i遍歷1至99，判斷其是否為奇數(shù)，結(jié)果為真則執(zhí)行x=x+i，最后輸出結(jié)果X。

算法代碼：

for（i=1;i<=99;i++）

{

if（i%2！=0）

x=x+i;

}

算法的基本語句為if（i%2！=0）x=x+i，時(shí)間復(fù)雜度為O（n）。

例2.2：求序列：0，1，1，2，3，5，8，13……的第46項(xiàng)（兔子繁衍問題）。

分析：觀察這個(gè)數(shù)列，從第三項(xiàng)開始，每一項(xiàng)的值都是前面兩項(xiàng)之和。那么可利用遞歸的思想，當(dāng)項(xiàng)數(shù)為0時(shí)返回0，當(dāng)項(xiàng)數(shù)為1時(shí)返回1，其余情況遞歸求解前兩項(xiàng)的和。

算法代碼：

int F（int n）

{

if（n==0）

return 0;

if（n=-1）

return 1;

else

return F（n-1）+F（n-2）;

}

兔子繁衍問題是一個(gè)呈指數(shù)級增長的問題，求F（45）需要遞歸求解F（44）與F（43），而求F（44），F(xiàn)（43）又需要分YA遞歸求解F（43）與F（42）、F（42）與F（41）。該遞歸算法的時(shí)間復(fù)雜度為[3]，如圖2.2所示，當(dāng)求解到第46項(xiàng)時(shí)所用時(shí)間非常長，時(shí)間為8.046秒。

例2.3 ：有兩個(gè)字符串S、T，求字符串T在字符串S中第一次出現(xiàn)的位置。（以求asdad在字符串a(chǎn)sdasdads中第一次出現(xiàn)的位置為例）。

分析：這個(gè)查找過程又稱為串匹配（stringmatching，也稱模式匹配），T稱為模式在文本處理系統(tǒng)、操作系統(tǒng)、編譯系統(tǒng)、數(shù)據(jù)系統(tǒng)以及Internet信息檢索系統(tǒng)中，串匹配是使用最頻繁的操作[4]。

那么如何查找呢？我們可以設(shè)置兩個(gè)變量i，j。i為跟蹤字符串S中字符位置變化的變量，i為跟蹤模式串T中字符位置變化的變量。該算法的代碼實(shí)現(xiàn)核心是一個(gè)循環(huán)結(jié)構(gòu)，初始時(shí)，i，j設(shè)置為0，將S[i]與T[j]進(jìn)行比較，若相同，則執(zhí)行i++，j++操作，若不同則執(zhí)行i++，并將i置為0。

算法代碼：

int BF（char S[]，char T[]）

{

int index=0;

int i=0;

int i=0;

while（S[i]！='＼0'&&T;[j]！='＼0'）

{

if（S[i]==T[j]）

{

i++;

j++;

}

else

{

index++;

i=index;

j=0;

}

}

if（T[j]=='＼0'）

return index;

else

return-1;

}

設(shè)S長度為n，T長度為m。設(shè)在源字符串i位置成功匹配，討論每一次失配都為比較到模式串最后一個(gè)位置，那么成功時(shí)比較了（i+1）*m次（數(shù)組下標(biāo)從0開始）。

對成功匹配的字符串來說，可供比較的位置有n-m+1個(gè)，假設(shè)每一個(gè)位置成功匹配的概率相等，則那么平均比較次數(shù)為將Pi代入為：即在最壞情況下算法的平均比較次數(shù)為次，設(shè)n>>m，那么時(shí)間復(fù)雜度為O（n×m）。

3 算法優(yōu)化與其重要意義

長久以來，人們在面對一個(gè)算法設(shè)計(jì)問題時(shí)都會(huì)盡力去尋找“最優(yōu)算法”。如果一個(gè)算法設(shè)計(jì)的時(shí)間復(fù)雜度過高，那么算法執(zhí)行所需的時(shí)間就有可能達(dá)到人們所無法接受的地步。所以算法優(yōu)化備受重視，顯然，如何優(yōu)化算法成為了關(guān)鍵問題。下面就例2.F.例2.3討論相應(yīng)的優(yōu)化算法。

例3.1：求例2.1（1+3+5+……+99）的優(yōu)化算法。

法1：

分析：通過例2.1的分析可知要求的序列為奇數(shù)序列，故可以在算法2.1中將條件判斷去掉，并將i++改為i=i+2。這樣程序執(zhí)行次數(shù)就會(huì)減少一半左右。

算法代碼：

for（i=1;i<=99;i=i+2）

x=x+i;

因?yàn)閱栴}規(guī)模太小，無法從執(zhí)行時(shí)間上體現(xiàn)出優(yōu)化算法的優(yōu)勢。雖然算法2.1與法1的時(shí)間復(fù)雜度都是O（n），但是法1減少了約一半的執(zhí)行次數(shù)，當(dāng)問題規(guī)模變得非常大的時(shí)候，這種算法優(yōu)化效果非?？捎^。

法2：

分析：在例2.1以及法1中，我們利用了遍歷求和的方法，時(shí)間復(fù)雜度都為O（n）。像等差數(shù)列、等比數(shù)列等這樣有規(guī)律的數(shù)學(xué)模型一般都能推導(dǎo)出相應(yīng)的數(shù)學(xué)公式，對于等差數(shù)列來說，故可以利用公式求解。

算法代碼：

int sum;

sum=（1+99）*50/2;

因?yàn)閷τ诖怂惴ǖ膶?shí)現(xiàn)代碼來說，基本語句的語句頻度為1，故時(shí)間復(fù)雜度為O（1）。由圖2.1、圖3.1與圖3.2的結(jié)果對比可以看出，此算法執(zhí)行時(shí)間與時(shí)間復(fù)雜度為O（n）的兩種算法的執(zhí)行時(shí)間幾乎相同。像法1中說的那樣，對于算法2.1、法1來說，問題規(guī)模太小導(dǎo)致基本語句需要執(zhí)行的次數(shù)過少，無法真正將執(zhí)行時(shí)間區(qū)別開來。但是通過理論分析可知，算法2.1、法看 隨著問題規(guī)模的不斷增大導(dǎo)致執(zhí)行時(shí)間不斷增加，但對于法2來說，執(zhí)行次數(shù)恒為1，即使問題規(guī)模很大，執(zhí)行時(shí)間也基本不會(huì)變。

例3.2：求例2.2（兔子繁衍問題）的優(yōu)化算法。

分析：一般情況下，數(shù)列求和可以通過循環(huán)結(jié)構(gòu)遍歷求和。而在程序設(shè)計(jì)的循環(huán)結(jié)構(gòu)中如果最內(nèi)層循環(huán)僅為“普通語句”，那么這段程序的時(shí)間復(fù)雜度為O（n^x），x為循環(huán)體層數(shù)。由圖3.3可以看出，如果能將算法的時(shí)間復(fù)雜度由降低到O（n）那么這將是一個(gè)非常大的提升，即如果能將算法2.2轉(zhuǎn)換成一個(gè)單循環(huán)結(jié)構(gòu)，那么就可以完成算法優(yōu)化。設(shè)f0=-，f1=1，循環(huán)執(zhí)行f2=fO+f1，f0=f1，f1=f2，直到求到所需項(xiàng)。

算法代碼：

for（i-2;i<-45;i++）

{

f2=f0+f1;

f0=f1;

f1=f2;

}

此算法將時(shí)間復(fù)雜度降為O（n）。由圖2.2 與圖3.4 的時(shí)間對比可以看出非常明顯的差距，算法2.2需要8.046秒，而算法3.2僅需約0.03秒。當(dāng)求第46項(xiàng)時(shí)，算法2.2運(yùn)行時(shí)間約為算法3.2的300倍。而如果問題規(guī)模繼續(xù)增長，那么時(shí)間差距將是非常巨大的。由此可看出優(yōu)化算法的重要性。對于一些時(shí)間復(fù)雜度高的算法來說，問題規(guī)模稍稍增長，增加的運(yùn)行時(shí)間可能就會(huì)達(dá)到人們無法忍受的地步。而對于此例來說，對算法問題進(jìn)行分析時(shí)僅僅換了一個(gè)數(shù)學(xué)切入角度，執(zhí)行算法所需的時(shí)間就有近300倍的差距?？梢姰?dāng)我們優(yōu)化算法時(shí)，嘗試從不同角度思考、推導(dǎo)是一個(gè)很好的方法。

例3.3：求例2.3的優(yōu)化算法。

分析：算法2.3的缺陷在于，當(dāng)S與T比較失敗時(shí)，無論過去比較結(jié)果如何都將j清零與S下一個(gè)字符比較，這就造成了資源的浪費(fèi)，這里的資源就是過去比較的結(jié)果。

那么算法優(yōu)化的目標(biāo)就為當(dāng)匹配過程中出現(xiàn)字符比較不等時(shí)，利用我們得到的資源，在i不變的情況下將模式向右移動(dòng)盡可能遠(yuǎn)的一段距離后繼續(xù)進(jìn)行比較。

設(shè)應(yīng)移動(dòng)到模式串的T[k]位置。

可以得到如下關(guān)系：

可推得：

由3.3可知，模式串的每一個(gè)位置i所對應(yīng)的k值與主串無關(guān)。設(shè)k=next[j]，假設(shè)next[]數(shù)組已知，則優(yōu)化算法代碼如下：

int KMP（char S[]，char T[]，int next[]，intlengthT）

{

int i=0;

int j=0;

while（S[i]）

i++;

int lengthS=i;

i=0;

while（i

{

if（j==-1‖S[i]==T[j]）

{

i++;

j++;

}

else

j=next[j];

}

if（！T[j]）

return i-lengthT;

else

return-1;

}

由代碼可看出，當(dāng)next[]數(shù)組已知的情況下，優(yōu)化算法與算法2.3非常相似，不同之處的核心在于當(dāng)出現(xiàn)不匹配情況時(shí)優(yōu)化算法不是將j置為0，而是執(zhí)行j=next[j]操作，即尋找到回溯位置再與主串進(jìn)行比較，這樣的操作使時(shí)間復(fù)雜度由O（n×m）降為O（n+m）。下面討論如何計(jì)算next[]數(shù)組值。

由3.1、3.2、3.3可推出next[]數(shù)組的定義：

設(shè)next[j]=k已知，那么可知在模式串中存在如3.3的關(guān)系，且不存在k'>k，使式子T[0]T[1]……T（k-1]T[k]=T[j-k]T[j-k+1]……T[j-1]T[j]（3.4）

成立，那么next[j+1]存在以下兩種情況：

（1）若T[k]=T[j]，可推得next[j+1]=next[j]+1。

（2）若T[k]≠T[j]，即式子3.4的關(guān)系不成立，此時(shí)應(yīng)尋找另一個(gè)位置k'，滿足關(guān)系3.5

T[0]T[1]……T[k-I]T[k]=T[j-k]T[j-k，+1]……T[j-1]T[j]（3.5）

成立，此時(shí)求k'值轉(zhuǎn)化成了模式串的模式匹配問題。設(shè)T[k]≠T[j]且next[k]=k'，并且3.5關(guān)系成立，那么可得next[j+1]=next[k]+1，若next[k]=k時(shí)關(guān)系3.5不成立，則需繼續(xù)尋找k=next[k]滿足

T[0]T[1]……T[k-1]T[k]=T[j-k]T[j-k+1]……T[j-1]T[j]（3.6）

成立，同理若k=next[k]時(shí)關(guān)系

3.6 不成立，則需繼續(xù)尋找next[k]，依次遞推下去，直至尋找至滿足要求的位置或next[j+1]=0。next[]數(shù)組計(jì)算算法如下：

void next（char T[]，int next[]，int length）

{

int i=0;

int k=-I;

next[0]=-1;

while（i

{

if（k==-1‖T[i]==T[k]）

{

i++;

k++;

next[i]=k;

}

else

k=next[k];

}

}

設(shè)輸入的主串為：asdasdads，模式串為：asdad，可推得：next[]={-1，0，0，0，1}

但這仍是一個(gè)有“缺陷”算法，例如，若主串為ddddadddddabcd模式串為dddddabcd，按照上述算法計(jì)算next[]數(shù)組值為next[]={-1，0，1，2，3，4，0，0，0），若在j=4處匹配失敗，那么還需要進(jìn)行j=3、j-2、j=1、j=0的比較，但是這些比較都是沒有必要的，因?yàn)閖=4處模式串是d，前面的字符與j=4相同，故應(yīng)直接進(jìn)行主串的下一個(gè)字符與j=0相比較，以下是優(yōu)化的next[]數(shù)組算法：

void next（char T[]，int next[]，int length）

{

int i=0;

int k=-1;

next[0]=-1;

while（i

{

if（k==-1‖T[i]==T[k]）

{

i++;

k++;

if（T[i]==T[k]）

next[i]=next[k];

else

next[i]=k;

}

else

k=next[k];

}

}

那么模式串“asdad”對應(yīng)的next[]數(shù)組應(yīng)為：next[]={-1，0，0，-1，1}

對比圖2.3與圖3.5發(fā)現(xiàn)，優(yōu)化后的算法所需執(zhí)行時(shí)間與未優(yōu)化算法所需執(zhí)行時(shí)間幾乎相同，原因是因?yàn)閱栴}規(guī)模太小，而對于優(yōu)化算法來說，為了優(yōu)化、降低時(shí)間復(fù)雜度，在完成相應(yīng)優(yōu)化時(shí)需要一些固定的代碼實(shí)現(xiàn)，這些代碼實(shí)現(xiàn)所需要的時(shí)間在問題規(guī)模非常小的時(shí)候體現(xiàn)得非常明顯。但當(dāng)問題規(guī)模非常大的時(shí)候?qū)⒊浞煮w現(xiàn)優(yōu)化算法的優(yōu)勢，代碼實(shí)現(xiàn)所占時(shí)間將變得微不足道。

從本例可以看出，優(yōu)化算法經(jīng)歷的數(shù)學(xué)推導(dǎo)過程并不像前述例子一樣簡單。在實(shí)際應(yīng)用中，我們會(huì)遇到更復(fù)雜的算法，為了優(yōu)化算法所需投入的人力物力會(huì)更大。而在本例中輸入量對應(yīng)的問題規(guī)模與算法優(yōu)化推導(dǎo)所需經(jīng)歷的“物質(zhì)過程”不成比例。如果實(shí)際應(yīng)用中輸入量不大，那么時(shí)間復(fù)雜度高與低的兩種算法呈現(xiàn)出的物質(zhì)效益差異將微乎其微，在這種情況下再投入大量人力物力去優(yōu)化算法將是一種不明智的行為。所以當(dāng)我們面對一個(gè)算法設(shè)計(jì)問題時(shí)，不應(yīng)一味地追求效率最高，應(yīng)實(shí)際問題實(shí)際處理。應(yīng)客觀分析問題規(guī)模的大小，如果對待問題規(guī)模較小的算法也投入大量的精力去求解最優(yōu)算法那么可能反而會(huì)造成物質(zhì)、資源的浪費(fèi)導(dǎo)致經(jīng)濟(jì)損失。

4 結(jié)語

算法設(shè)計(jì)的好壞決定程序執(zhí)行的時(shí)間與效率，而程序完成的時(shí)間、效率則會(huì)直接決定相關(guān)的價(jià)值效益，如果算法設(shè)計(jì)的不好，那么在生活中很有可能造成很大的資源浪費(fèi)、經(jīng)濟(jì)損失。從本文的等差數(shù)列求和、兔子繁衍問題可看出，在優(yōu)化算法時(shí)，換一種數(shù)學(xué)角度去思考相應(yīng)問題會(huì)在算法優(yōu)化推導(dǎo)過程變得更簡單的情況下推導(dǎo)出更高效的算法。如果算法問題本身就很復(fù)雜，那么對應(yīng)的優(yōu)化過程可能也會(huì)很復(fù)雜（例如本文中的串匹配問題），這時(shí)我們就應(yīng)從多方面考慮問題，對比優(yōu)化過程需要投入的資源量與結(jié)果呈現(xiàn)的物質(zhì)價(jià)值效益。當(dāng)問題規(guī)模足夠大且經(jīng)對比后發(fā)現(xiàn)優(yōu)化算法帶來的效益足夠大時(shí)，我們就應(yīng)運(yùn)用各種數(shù)學(xué)思想逐步分析所需優(yōu)化的算法，降低時(shí)間復(fù)雜度從而實(shí)現(xiàn)算法優(yōu)化;當(dāng)問題規(guī)模很小且對比后發(fā)現(xiàn)優(yōu)化算法所帶來的效益為負(fù)值，這時(shí)時(shí)間復(fù)雜度較高的算法反而沒有時(shí)間復(fù)雜度低的算法更好，因此我們面對不同問題不同情況時(shí)應(yīng)根據(jù)特定情況進(jìn)行求解，使設(shè)計(jì)的算法成為“我們需要的最優(yōu)算法”。致謝：感謝李孝忠教授的指導(dǎo)與幫助！

參考文獻(xiàn)

[1]殷建平，徐云，王剛，劉曉光，蘇明，鄒恒明，王宏志.算法導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2013.

[1]嚴(yán)蔚敏，李冬梅，吳偉民.數(shù)據(jù)結(jié)構(gòu)（c語言版|第2版）[M].北京：人民郵電出版社，2015：11-12.

[1]鄧芳.關(guān)于遞歸算法時(shí)間復(fù)雜度分析的探討[J].浙江萬里學(xué)院學(xué)報(bào)，2005（04）：26.

[1]王紅梅，胡明.算法設(shè)計(jì)與分析（第2版）[M].北京：清華大學(xué)出版社，2013（37）.