田效宇

摘要

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

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

1 算法設計的概念

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

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

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

例1：計算1*2*3*……*9。如圖1所示。

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

算法代碼：

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

a=a*i;

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

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

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

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

2 設計算法

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

例2.1 ：計算1+3+5+……+99。

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

算法代碼：

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

{

if（i%2！=0）

x=x+i;

}

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

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

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

算法代碼：

int F（int n）

{

if（n==0）

return 0;

if（n=-1）

return 1;

else

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

}

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

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

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

那么如何查找呢？我們可以設置兩個變量i，j。i為跟蹤字符串S中字符位置變化的變量，i為跟蹤模式串T中字符位置變化的變量。該算法的代碼實現(xiàn)核心是一個循環(huán)結構，初始時，i，j設置為0，將S[i]與T[j]進行比較，若相同，則執(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;

}

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

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

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

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

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

法1：

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

算法代碼：

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

x=x+i;

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

法2：

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

算法代碼：

int sum;

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

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

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

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

算法代碼：

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

{

f2=f0+f1;

f0=f1;

f1=f2;

}

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

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

分析：算法2.3的缺陷在于，當S與T比較失敗時，無論過去比較結果如何都將j清零與S下一個字符比較，這就造成了資源的浪費，這里的資源就是過去比較的結果。

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

設應移動到模式串的T[k]位置。

可以得到如下關系：

可推得：

由3.3可知，模式串的每一個位置i所對應的k值與主串無關。設k=next[j]，假設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;

}

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

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

設next[j]=k已知，那么可知在模式串中存在如3.3的關系，且不存在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的關系不成立，此時應尋找另一個位置k'，滿足關系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）

成立，此時求k'值轉化成了模式串的模式匹配問題。設T[k]≠T[j]且next[k]=k'，并且3.5關系成立，那么可得next[j+1]=next[k]+1，若next[k]=k時關系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]時關系

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

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];

}

}

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

但這仍是一個有“缺陷”算法，例如，若主串為ddddadddddabcd模式串為dddddabcd，按照上述算法計算next[]數(shù)組值為next[]={-1，0，1，2，3，4，0，0，0），若在j=4處匹配失敗，那么還需要進行j=3、j-2、j=1、j=0的比較，但是這些比較都是沒有必要的，因為j=4處模式串是d，前面的字符與j=4相同，故應直接進行主串的下一個字符與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”對應的next[]數(shù)組應為：next[]={-1，0，0，-1，1}

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

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

4 結語

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

參考文獻

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

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

[1]鄧芳.關于遞歸算法時間復雜度分析的探討[J].浙江萬里學院學報，2005（04）：26.

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