第一章

算法的概念1.1 算法的概念和描述1.2 算法的時間復(fù)雜度和空間復(fù)雜度1.1 算法的概念和描述【1.1.1 算法的概念】

算法是一系列解決問題的清晰指令，也就是對于符合一定規(guī)范的輸入在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗點(diǎn)說，就是計(jì)算機(jī)解題的過程。在這個過程中，無論是形成解題思路還是編寫程序，都是在實(shí)施某種算法。前者是推理實(shí)現(xiàn)的算法，后者是操作實(shí)現(xiàn)的算法。

這個定義可以用一幅簡明的圖來說明，如圖1.1所示。

一個算法應(yīng)該具有以下五個重要的特征：①有窮性：一個算法必須保證執(zhí)行有限步之后結(jié)束，并且每一步都在有窮時間內(nèi)完成。②確定性：算法的每一步驟都必須有確切的定義。③輸入：一個算法有零個或多個輸入，以刻畫運(yùn)算對象的初始情況。④輸出：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的。⑤可行性：算法應(yīng)該是可行的，這意味著所有待實(shí)現(xiàn)的算法都是能夠理解和實(shí)現(xiàn)的，并可通過有限次運(yùn)算完成。

為了闡明算法的概念，本節(jié)將以三種方法為例來解決同一個問題：計(jì)算兩個整數(shù)的最大公約數(shù)。這些例子會幫助我們闡明以下幾項(xiàng)要點(diǎn)：圖1.1算法的概念1.1 算法的概念和描述①算法的每一個步驟都必須沒有歧義，不能有半點(diǎn)含糊。②必須認(rèn)真確定算法所處理的輸入的值域。③同一算法可以用幾種不同的形式來描述。④同一問題，可能存在幾種不同的算法。⑤針對同一問題的算法可能會基于完全不同的解題思路而且解題速度也會有顯著不同。

還記得最大公約數(shù)的定義嗎?將兩個不全為0的非負(fù)整數(shù)m和n的最大公約數(shù)記為gcd（m，n），代表能夠整除（即余數(shù)為0）m和n的最大正整數(shù)。亞歷山大的歐幾里得（公元前3世紀(jì)）所著的《幾何原本》，以系統(tǒng)論述幾何學(xué)而著稱，在其中的一卷里，他簡要地描述了一個最大公約數(shù)算法。用現(xiàn)代數(shù)學(xué)的術(shù)語來表述，歐幾里得算法基于的方法重復(fù)應(yīng)用下列等式，直到mmodn等于0。 gcd（m，n）=gcd（n，mmodn）（mmodn表示m除以n之后的余數(shù)）

因?yàn)間cd（m，0）=m，m最后的取值也就是m和n的初值的最大公約數(shù)。

舉例來說，gcd（60，24）可以這樣計(jì)算： gcd(60,24)=gcd(24,60mod24)=gcd(24,12) =gcd(12,24mod12)=gcd(12,0)=12

下面是該算法的一個更加結(jié)構(gòu)化的描述。1.1 算法的概念和描述

用于計(jì)算gcd（m，n）的歐幾里得算法：

第一步：如果n=0，返回m的值作為結(jié)果，同時函數(shù)結(jié)束；否則，進(jìn)入第二步。

第二步：m除以n，將余數(shù)賦給r。

第三步：將n的值賦給m，將r的值賦給n，返回第一步。

我們也可以使用偽代碼來描述這個算法：

算法Euclid（m，n） //使用歐幾里得算法計(jì)算gcd（m，n） //輸入∶兩個不全為0的非負(fù)整數(shù)m，n //輸出∶m，n的最大公約數(shù)

whilen≠0do {r←mmodn m←n n←r } returnm

上面的偽代碼也可以用流程圖來加以描述，如圖1.2所示。圖1.2歐幾里得算法的流程圖1.1 算法的概念和描述

我們怎么知道歐幾里得算法最終一定會結(jié)束呢？通過觀察，我們發(fā)現(xiàn)，每經(jīng)過一次循環(huán)，參加運(yùn)算的兩個算子中的后一個都會變得更小，而且絕對不會變成負(fù)數(shù)。確實(shí)，下一次循環(huán)時，n的新值是mmodn，這個值總是比n小。所以，第二個算子的值最終會變成0，此時，這個算法也就停止了。

就像其他許多問題—樣，最大公約數(shù)問題也有多種算法。讓我們看看解這個問題的另外兩種方法。第—個方法只基于最大公約數(shù)的定義；m和n的最大公約數(shù)就是能夠同時整除它們的最大正整數(shù)。顯然，這樣一個公約數(shù)不會大干兩數(shù)中的較小者，因此，我們先有：t=min{m，n}。現(xiàn)在可以開始檢查t是否能夠整除m和n：如果能，t就是最大公約數(shù)；如果不能，我們就將t減1，然后繼續(xù)嘗試（我們?nèi)绾未_定該算法最終一定會結(jié)束呢?）。 例如，對于60和24這兩個數(shù)來說，該算法會先嘗試24，然后是23，這樣一值嘗試到12，算法就結(jié)束了。我們給這種算法命名為連續(xù)整數(shù)檢測算法，下面是該算法的具體描述。 用于計(jì)算gcd（m，n）的連續(xù)整數(shù)檢測算法∶ 第一步∶將min{m，n}的值賦給t。 第二步∶m除以t，如果余數(shù)為0，進(jìn)入第三步；否則，進(jìn)入第四步。 第三步∶n除以t，如果余數(shù)為0，返回t的值作為結(jié)果；否則，進(jìn)入第四步。 第四步∶把t的值減1。返回第二步。

1.1 算法的概念和描述

注意：和歐幾里得算法不同，按照這個算法的當(dāng)前形式，當(dāng)它的—個輸入為0時，計(jì)算出來的結(jié)果是錯誤的。這個例子說明了為什么必須認(rèn)真、清晰地規(guī)定算法輸入的值域。

求最大公約數(shù)的第三種方法，我們應(yīng)該在中學(xué)時就很熟悉了。

中學(xué)里計(jì)算gcd（m，n）的方法：

第一步：找到m的所有質(zhì)因數(shù)。

第二步：找到n的所有質(zhì)因數(shù)。

第三步：從第一步和第二步求得的質(zhì)因數(shù)分解式中找出所有的公因數(shù)（如果P是一個公因數(shù)，而且在m和n的質(zhì)因數(shù)分解式分別出現(xiàn)過Pm和pn次，那么應(yīng)該將P重復(fù)min{pm，pn}次）。

第四步：將第三步中找到的公因數(shù)相乘，其結(jié)果作為給定數(shù)m和n的最大公約數(shù)。

這樣，對于60和24這兩個數(shù)，我們得到： 60=2×2×3×5 24=2×2×2×3 gcd(60,24)=2×2×3=12

我們能夠看到，第三種方法比歐幾里得算法要復(fù)雜得多，也慢得多。撇開低劣的性能不談，以這種形式表述的中學(xué)求解過程還不能稱為一個真正意義上的算法。為什么?因?yàn)槠渲星筚|(zhì)因數(shù)的步驟并沒有明確定義。1.1 算法的概念和描述【1.1.2 算法的描述】

上一節(jié)中，我們已經(jīng)用文字、偽代碼及流程圖分別描述了歐幾里得算法。這是當(dāng)今描述算法的三種最常用的做法。

使用自然語言描述算法顯然很有吸引力，但是自然語言固有的不嚴(yán)密性使得要簡單清晰地描述算法變得很困難。不過，這也是我們在學(xué)習(xí)算法的過程中需要努力掌握的一個重要技巧。

偽代碼是自然語言和類編程語言組成的混合結(jié)構(gòu)。偽代碼往往比自然語言更精確，而且用偽代碼描述的算法通常會更簡潔。令人驚訝的是，計(jì)算機(jī)科學(xué)家從來沒有就偽代碼的形式達(dá)成過共識，而是讓教材的作者去設(shè)計(jì)他們自己的"方言"。幸運(yùn)的是，這些方言彼此十分相似，任何熟悉一門現(xiàn)代編程語言的人都完全能夠理解。

在計(jì)算機(jī)應(yīng)用早期，描述算法的主要工具是流程圖。流程圖使用一系列相連的幾何圖形來描述算法，幾何圖形內(nèi)部包含對算法步驟的描述。實(shí)踐證明，除了一些非常簡單的算法以外，這種表示方法使用起來非常不便。如今，我們只能在早期的算法教材里找到它的蹤影。

本書選擇的描述方式力求不給讀者帶來困難，出于對簡單性的偏好，我們忽略了對變量的定義，并使用了縮進(jìn)來表示for、if和while語句的作用域。正像大家在前一節(jié)里看到的那樣，我們將使用箭頭“←”表示賦值操作，用雙斜線“∥"表示注釋。1.2 算法的時間復(fù)雜度和空間復(fù)雜度【1.2.1 算法的評價】

這正是我們本節(jié)要討論的問題——算法的復(fù)雜度，即估計(jì)、評價算法運(yùn)行時所需要花費(fèi)的時間及空間。

算法的時間復(fù)雜度和空間復(fù)雜度合稱為算法的復(fù)雜度。

那么，算法一旦確定，如何計(jì)算它的復(fù)雜度，衡量其優(yōu)劣呢?通常從下面幾個方面來考慮：

（1）正確性：也稱有效性，是指算法能滿足具體問題的要求。即對任何合法的輸入，算法都會得出正確的結(jié)果。確認(rèn)正確性的根本方法是進(jìn)行形式化的證明。但對一些較復(fù)雜的問題，這是一件相當(dāng)困難的事。許多計(jì)算機(jī)科學(xué)工作者正致力于這方面的研究，目前尚處于初級階段。因此，實(shí)際中常常用測試的方法驗(yàn)證算法的正確性。測試是指用精心選定的輸入（測試數(shù)據(jù)）去運(yùn)行算法，檢查其結(jié)果是否正確。但正如著名的計(jì)算機(jī)科學(xué)家E.Dijkstra所說的那樣，"測試只能指出有錯誤，而不能指出不存在錯誤"。

（2）可讀性：指算法被理解的難易程度。人們常把算法的可讀性放在比較重要的位置，主要是因?yàn)榛逎y懂的算法不易交流和推廣使用，也難以修改、擴(kuò)展與調(diào)試，而且可能隱藏較多的錯誤?？勺x性實(shí)質(zhì)上強(qiáng)調(diào)的是越簡單的東西越美。1.2 算法的時間復(fù)雜度和空間復(fù)雜度

（3）健壯性：對非法輸入的抵抗能力。它強(qiáng)調(diào)的是：如果輸入非法數(shù)據(jù)，算法應(yīng)能加以識別并做出處理，而不是產(chǎn)生誤操作或陷入癱瘓。

（4）時間復(fù)雜度與空間復(fù)雜度。時間復(fù)雜度是算法的計(jì)算復(fù)雜性的時間度量，粗略地講，就是該算法的運(yùn)行時間。同一個問題，不同的算法可能有不同的時間復(fù)雜度。問題規(guī)模較大時，時間復(fù)雜度就變得十分重要。盡管計(jì)算機(jī)的運(yùn)行速度提高很快，但這種提高無法滿足問題規(guī)模加大帶來的速度要求。所以追求高速算法仍然是件重要的事情?？臻g復(fù)雜度是指算法運(yùn)行所需的存儲空間的多少。相比起來，人們一般會更多地關(guān)注算法的時間復(fù)雜度，但這并不是因?yàn)橛?jì)算機(jī)的存儲空間是海量的，而是由人們面臨的問題的本質(zhì)決定的。時間復(fù)雜度與空間復(fù)雜度往往是一對矛盾。常?？梢杂每臻g換取速度，反之亦然。1.2 算法的時間復(fù)雜度和空間復(fù)雜度【1.2.2 算法的時間復(fù)雜度】

給定一個算法，如何確定該算法的時間復(fù)雜度呢?我們可以采用事后統(tǒng)計(jì)的辦法得出執(zhí)行算法所用的具體時間。因?yàn)楹芏嘤?jì)算機(jī)都有這種計(jì)時的功能，甚至可以獲取精確到毫秒級的統(tǒng)計(jì)數(shù)據(jù)。但這種辦法有兩個缺陷：第一，必須先運(yùn)行才能分辨出算法的好壞;第二，所得的時間的統(tǒng)計(jì)量過分依賴于計(jì)算機(jī)的硬件、軟件等環(huán)境因素，這些因素容易掩蓋算法本身的優(yōu)劣，因?yàn)橐粋€笨拙的算法在先進(jìn)的大型機(jī)上運(yùn)行可能比一個同功能的優(yōu)化算法在微型機(jī)上運(yùn)行更省時間。

因此，人們常常對算法進(jìn)行事前的時間估算。可利用語句的"頻度"和算法的漸進(jìn)時間復(fù)雜度這兩個與軟、硬件無關(guān)的度量來討論算法執(zhí)行的時間消耗。

設(shè)n稱為問題的規(guī)模，當(dāng)n不斷變化時，算法中的基本語句執(zhí)行的頻度（我們且稱為時間頻度）T（n）也會不斷變化。一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T（n）表示，若有某個輔助函數(shù)f（n），使得當(dāng)n趨近于無窮大時，T（n）/f（n）的極限值為不等于零的常數(shù)，則稱f（n）是T（n）的同數(shù)量級函數(shù)。記作T（n）=O（f(n)），稱O（f(n)）為算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。

時間頻度不同，但時間復(fù)雜度可能相同。如： T（n）=n2＋3n+4與T（n）=4n2＋2n＋1它們的頻度不同，但時間復(fù)雜度相同，都為O（n2）。

1.2 算法的時間復(fù)雜度和空間復(fù)雜度

用兩個算法A1和A2來求解同一問題，時間復(fù)雜度分別是T1（n）=100n2，T2（n）=5n3。

（1）當(dāng)輸入量n<20時，有T1（n）>T2（n），后者花費(fèi)的時間較少。

（2）隨著問題規(guī)模n的增大，兩個算法的時間開銷之比5n3/100n2=n/20亦隨著增大。即當(dāng)問題規(guī)模較大時，算法Al比算法A要有效得多。它們的漸近時間復(fù)雜度O（n2）和O（n3）從宏觀上評價了這兩個算法在時間方面的質(zhì)量。在算法分析時，往往對算法的時間復(fù)雜度和漸近時間復(fù)雜度不予區(qū)分，而經(jīng)常是將漸近時間復(fù)雜度T（n）=O（f（n））簡稱為時間復(fù)雜度，其中的f（n）一般是算法中頻度最大的語句的頻度。

研究算法的時間復(fù)雜度，通?？紤]的是算法在最壞情況下的時間復(fù)雜度。稱為最壞時間復(fù)雜度。一般不特別說明，討論的時間復(fù)雜度均是最壞情況下的時間復(fù)雜度。這樣做的原因是;最壞情況下的時間復(fù)雜度T（n）=O（n），是算法在任何輸入實(shí)例上運(yùn)行時間的上界，即它表示對于任何輸入實(shí)例，該算法的運(yùn)行時間不可能大于O（n）。

另一個衡量算法復(fù)雜度的指標(biāo)是平均時間復(fù)雜度，它是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下，算法的期望運(yùn)行時間。1.2 算法的時間復(fù)雜度和空間復(fù)雜度1.2 算法的時間復(fù)雜度和空間復(fù)雜度1.2 算法的時間復(fù)雜度和空間復(fù)雜度1.2 算法的時間復(fù)雜度和空間復(fù)雜度

（4）算法的時間復(fù)雜度不僅僅依賴于問題的規(guī)模，還與輸入實(shí)例的初始狀態(tài)有關(guān)。例如： i=1； while(i＜n)and(x≠a[i]) #i=i+1； ifa[i]=xthenreturn(i)

此程序段中語句#的頻度不僅是n的函數(shù)，而且與x及數(shù)組a中各元素的具體值有關(guān)，在這種情況下，通常按最壞的情況考慮。由于while循環(huán)執(zhí)行的最大次數(shù)為n—1，則語句#的頻度的最大值為f（n）=n—1，則認(rèn)為此程序段的時間復(fù)雜度為T（n）=O（n）。

（5）遞歸算法的頻度不容易估算，須由遞推公式計(jì)算求得。其基本方法是：方程右邊較小的項(xiàng)根據(jù)定義被依次替代，如此反復(fù)擴(kuò)展，直到得到一個沒有遞歸式的完整數(shù)列，從而將復(fù)雜的遞歸問題轉(zhuǎn)化為了新的求和問題。以有名的Hanoi塔問題為例，其解是一個遞歸形式的算法： void hanoi（intn,charA,charB,charC)

｛ if(n==1)move(n,A,C)； else

｛hanoi(n—1,A,C,B)； move(n,A,C)； hanoi(n-1,B,A,C)；

｝

｝1.2 算法的時間復(fù)雜度和空間復(fù)雜度

顯見問題的規(guī)模是n，move（n，A，C）語句的頻度為1，若整個算法的頻度為f（n），則遞歸調(diào)用hanoi（n—1，A，C，B）和hanoi（n—1，B，A，C）語句的頻度應(yīng)為f（n一1），于是有

f(n)=f(n—1)＋1＋f(n—1)即

f(n)=2f(n—1)＋1,進(jìn)行遞推，有

f(n)=2(2f(n—2)＋1)＋1 =4f(n—2)＋3 =4(2f(n—3)＋1)＋3 =8f（n一3）十7 … =2kf(n—k)＋2k—1

當(dāng)n=k＋1時，f（n）=2n—1f（1）＋2n—1—1。

f（1）是n=1時算法的頻度，它只有move（n，A，C）語句，其值為1。最后得到f（n）=2n—1。時間復(fù)雜度T（n）=O（2n）。1.2 算法的時間復(fù)雜度和空間復(fù)雜度 總之，頻度和時間復(fù)雜度雖不能精確地確定一個算法或程序的執(zhí)行時間，但可以讓人們知道隨著問題的規(guī)模增大，算法耗用時間的增長趨勢。由于討論算法的好壞不是針對某個特定大小的問題（這樣做本身沒有意義），因此，時間復(fù)雜度對算法來說是一個較恰當(dāng)?shù)牧慷取?較常見的時間復(fù)雜度有O（1）（常量型）、O（n）、O（n2）、…、O（nk）（多項(xiàng)式型）、O（lbn）、O（nlbn）（對數(shù)型）和O（n!）（階乘型）。顯然，時間復(fù)雜度為O（2n）或O（en）的指數(shù)型算法的效率極低，在n較大時無法實(shí)用。如圖1.3所示表明了各種時間復(fù)雜度的增長率。圖1.3各種時間復(fù)雜度的增長率1.2 算法的時間復(fù)雜度和空間復(fù)雜度

表1.1是我們所熟悉的各種排序算法的復(fù)雜度，讀者可以分析思考。表1.1常用排序算法的時間復(fù)雜度和空間復(fù)雜度 實(shí)踐中我們可以把事前估算和事后統(tǒng)計(jì)兩種辦法結(jié)合起來使用，例如，若上機(jī)運(yùn)行一個10×10矩陣模型，執(zhí)行時間為12ms，則由算法的時間復(fù)雜度T（n）=O（n3）可估算一個31×31矩陣自乘的時間大約為（31/10）3×12ms≈358ms。這種辦法很有實(shí)用價值，它用小模型可推得大尺寸問題的耗用機(jī)時。1.2 算法的時間復(fù)雜度和空間復(fù)雜度1.2 算法的時間復(fù)雜度和空間復(fù)雜度

可見，這個簡單的遞歸算法雖然正確，但卻毫無效率。那么，fibl算法能改進(jìn)嗎?

首先，我們分析fib1算法為什么如此之慢呢?如圖1.4所示提示了由一個單獨(dú)的fib1（n）調(diào)用過程觸發(fā)的一系列遞歸操作。請注意很多計(jì)算步驟都是重復(fù)的！圖1.4fib1（n）遞歸調(diào)用的擴(kuò)張過程1.2 算法的時間復(fù)雜度和空間復(fù)雜度

正是由于重復(fù)計(jì)算才導(dǎo)致了fibl算法如此之慢。一種更合理的算法是隨時存儲中間計(jì)算結(jié)果——F0，F(xiàn)1，…，F(xiàn)n-1的值。

voidfib2(intn)

｛

if(n==0)return0；

f[0]=0；f[1]=1；

fori=2tondo f[i]=f[i—1]+f[i—2]；

returnf[n]； ｝ 與fibl算法一樣，由于該算法直接應(yīng)用了Fn