《算法導(dǎo)論》的確是本了不起的書(shū)，以我現(xiàn)在的水平即使是開(kāi)頭的幾章也難以理解透徹，于是就有了”與其問(wèn)題越堆積越多，不如停下來(lái)整理一下所學(xué)“這樣的念頭。

1. 分治

維基百科——
在計(jì)算機(jī)科學(xué)中，分治法是建基于多項(xiàng)分支遞歸的一種很重要的算法范式。字面上的解釋是“分而治之”，就是把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題，直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題的解即子問(wèn)題的解的合并。

維基百科給出了分治法的定義，我相信這比我自己總結(jié)的要精確的多，因此直接引用。
分治策略是一種常用的算法策略，它是許多高效算法的基礎(chǔ)，其中最耳熟能詳?shù)哪^(guò)于快速傅里葉變換與歸并算法。
在分治策略中，我們遞歸的求解一個(gè)問(wèn)題，在每層遞歸中應(yīng)用下面三個(gè)步驟：

1. 分解：將問(wèn)題劃分為一些子問(wèn)題，子問(wèn)題的形式與原問(wèn)題一樣，只是規(guī)模更?。?/li>
2. 解決：遞歸的求解出子問(wèn)題，如果子問(wèn)題的規(guī)模夠小，停止遞歸，直接求解。
3. 合并：將子問(wèn)題的解組合成原問(wèn)題的解。

求解子問(wèn)題時(shí)可能存在兩種情況：

1. 遞歸情況：子問(wèn)題足夠大，需要繼續(xù)遞歸求解；
2. 基本情況：子問(wèn)題已經(jīng)足夠小，不再需要遞歸求解，可以直接得出當(dāng)前子問(wèn)題的解。

除了這兩種與原問(wèn)題形式相同的子問(wèn)題情況外，還可能要求求解原問(wèn)題不一樣的子問(wèn)題，我們將這些子問(wèn)題的求解看做合并步驟的一部分。

2. 歸并算法的例子

我們首先來(lái)看看最常見(jiàn)的歸并排序算法，關(guān)于歸并排序的說(shuō)明實(shí)在太多，我相信任何一篇說(shuō)明該方面的文章都要比我講述的好，因此在此不再贅述歸并排序的詳細(xì)內(nèi)容。
簡(jiǎn)單了解歸并排序后，即可發(fā)現(xiàn)，歸并排序算法完全遵循分治模式，直觀上歸并排序可以理解為——

• 分解：分解待排序的n個(gè)元素的序列成各具n/2個(gè)元素的兩個(gè)子序列；
• 解決：判斷問(wèn)題規(guī)模，若是足夠小則直接求出答案，若是較大則繼續(xù)分解問(wèn)題，遞歸的求解答案；
• 合并：合并兩個(gè)已經(jīng)完成排序的子序列以產(chǎn)生排序的答案。

在歸并排序問(wèn)題中，序列的長(zhǎng)度為1時(shí)，達(dá)到上述的基本情況的要求，不需要做任何工作。因?yàn)殚L(zhǎng)度為1的序列必定是有序的。
算法導(dǎo)論中的偽代碼如下：

合并過(guò)程代碼片段1

合并過(guò)程代碼片段2

歸并排序算法的關(guān)鍵是“合并”步驟中兩個(gè)已排序序列的合并，這個(gè)過(guò)程多次調(diào)用并且不需要遞歸，因此我們?cè)O(shè)計(jì)一個(gè)輔助過(guò)程來(lái)實(shí)現(xiàn)。應(yīng)該注意到的是該偽代碼設(shè)計(jì)中使用了“哨兵“，即在數(shù)組的最后一個(gè)元素后多設(shè)一個(gè)單元的空間，存放一個(gè)特殊值（這里是∞），每當(dāng)處理到∞ 時(shí)即說(shuō)明該數(shù)組的非哨兵元素都已經(jīng)處理完畢。而∞ 大于任意常量，因此無(wú)元素?cái)?shù)組不會(huì)再被提取元素，后續(xù)循環(huán)會(huì)將未處理完的數(shù)組元素一一提取插入新數(shù)組。

分解過(guò)程代碼片段

現(xiàn)在我們將過(guò)程MERGE作為一個(gè)子程序來(lái)調(diào)用，若p>=r,則子數(shù)組最多有一個(gè)元素，所以已經(jīng)排好序。為了排序整個(gè)序列A={ A[1],A[2],.....,A[n] },我們執(zhí)行初始調(diào)用MEAGE-SORT(A,1,A.length),這里A.length=n。

3. 分析歸并排序算法

3.1 MERGE

我們首先分析MERGE的時(shí)間復(fù)雜度，假設(shè)第1行到第17行運(yùn)行一次的代價(jià)分別為常量c1,c2....c17，合并后的數(shù)組長(zhǎng)度為n1+n2=r-p+1=n,可分析得出——

• 第1-3行僅執(zhí)行一次，代價(jià)和為C1+C2+C3；
• 第4,5行執(zhí)行n1次，第6,7行執(zhí)行n2次，代價(jià)和為n1*(C4+C5)+n2*(C6+C7)；
• 第8-11行執(zhí)行一次，代價(jià)和為C8+C9+C10+C11；
• 第12,13行執(zhí)行n次，14-15行目的為將分?jǐn)?shù)組L的元素逐個(gè)插入合數(shù)組A中，而L中只有n1個(gè)有效元素，因此該部分執(zhí)行n1次，同理，16-17行執(zhí)行n2次，代價(jià)和為： n*(C12+C13)+n1*(C14+C15)+n2*(C16+C17)。

將以上分析結(jié)果累加，常數(shù)項(xiàng)合并為CK，得時(shí)間復(fù)雜度

f(n) = n*(C12+C13)+n1*(C14+C15+C4+C5)+n2*(C16+C17+C6+C7)+CK
=Θ(n)+Θ(n1)+Θ(n2)+Θ(1)
=Θ(n)

3.2 總體

雖然歸并排序在元素?cái)?shù)并非偶數(shù)時(shí)仍然能工作，但為了簡(jiǎn)化分析過(guò)程，我們假定問(wèn)題的規(guī)模是2的冪，這時(shí)每個(gè)分解步驟將產(chǎn)生規(guī)模正好為n/2的兩個(gè)子序列。這個(gè)假設(shè)將不會(huì)影響結(jié)果的增長(zhǎng)量級(jí)。
當(dāng)有n>1個(gè)元素時(shí)，設(shè)運(yùn)行時(shí)間為T（n），我們分解運(yùn)行時(shí)間為：

• 分解：分解步驟僅僅計(jì)算數(shù)組的中間位置，需要常量時(shí)間，時(shí)間復(fù)雜度為Θ（1）；
• 解決：遞歸的求解兩個(gè)規(guī)模均為n/2的子問(wèn)題，將貢獻(xiàn)2T(n/2)的運(yùn)行時(shí)間；
• 合并：之前的分析可知在一個(gè)具有n個(gè)元素的子數(shù)組過(guò)程上MERGE需要Θ（n）的時(shí)間。
  由此可得出歸并排序最壞情況的運(yùn)行時(shí)間為

當(dāng)n=1時(shí)，T(n) = Θ(1);
當(dāng)n>1時(shí)，T(n)=2T(n/2)+Θ(n)。

畫(huà)出遞歸樹(shù)

歸并算法遞歸樹(shù)

有關(guān)遞歸樹(shù)的內(nèi)容之后再詳細(xì)說(shuō)明。簡(jiǎn)而言之，遞歸樹(shù)中的每個(gè)節(jié)點(diǎn)都表示了該節(jié)點(diǎn)的代價(jià)。T(n)分解之后本身剩余的是合并的代價(jià)——Θ(n)=cn，分解后的兩個(gè)T(n/2)的和是T(n)代價(jià)的另一部分，作為cn的兩個(gè)葉節(jié)點(diǎn)，由此可知整棵樹(shù)中所有節(jié)點(diǎn)的代價(jià)和即算法的代價(jià)。
將T(n)不斷分解，直到分解到問(wèn)題規(guī)模為1時(shí)，由于n是2的冪，因此需要經(jīng)過(guò)lg(n)層分解。無(wú)論如何分解，算法最終都會(huì)將各個(gè)分?jǐn)?shù)組合并成長(zhǎng)度為n的有序數(shù)組，每層分解都相當(dāng)于將長(zhǎng)度為n的有序數(shù)組不斷劃分為小數(shù)組，即每層操作的數(shù)組長(zhǎng)度和是不變的，和為n。而合并操作的時(shí)間復(fù)雜度為Θ(n)，因此每層的代價(jià)和都為cn。
或者換個(gè)嚴(yán)謹(jǐn)些的方式來(lái)說(shuō)，一般來(lái)說(shuō)，若頂層為0層，頂層下的第i層有2^{i個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)分解解決后合并時(shí)需要的代價(jià)為其自身的長(zhǎng)度，即cn/(2}i)。故每層的代價(jià)和為cn，一共有l(wèi)g(n)+1層，因此整棵樹(shù)的代價(jià)為cn（lg(n)+1）=cn+cn*lg(n)。
忽略低階項(xiàng)和常量c后就得到了期望的結(jié)果Θ(nlg(n))。

4. 遞歸式

現(xiàn)在我們將上面所說(shuō)的最壞情況的運(yùn)行時(shí)間寫成數(shù)學(xué)表達(dá)式的形式：

遞歸式

這就是遞歸式了。遞歸式與分治法是緊密相關(guān)的，因?yàn)槭褂眠f歸式可以很自然的刻畫(huà)分治算法的運(yùn)行時(shí)間。一個(gè)遞歸式就是一個(gè)等式或不等式，它通過(guò)更小的輸入上的函數(shù)值來(lái)描述一個(gè)函數(shù)。遞歸式有很多種形式，例如，算法可能會(huì)將問(wèn)題分解成規(guī)模不等的子問(wèn)題，如2/3和1/3的劃分。同時(shí)，子問(wèn)題的規(guī)模不必是原問(wèn)題規(guī)模的一個(gè)固定比例，例如線性查找的遞歸式T(n)=T(n-1)+Θ(1)。
《算法導(dǎo)論》介紹了三種求解遞歸式的方法，即得出算法的”Θ“或”O(jiān)“漸近界的方法：

• 代入法：我們猜測(cè)一個(gè)界，然后使用數(shù)學(xué)歸納法證明這個(gè)界的正確性；
• 遞歸樹(shù)法：將遞歸式轉(zhuǎn)換為一棵樹(shù)，其節(jié)點(diǎn)表示不同層次的遞歸調(diào)用產(chǎn)生的代價(jià)。然后采用邊界和技術(shù)來(lái)求解遞歸式；
• 主方法：主方法可用于求解形如 T(n)=aT(n/b)+f(n) 的遞歸式的界，其中a>=1,b>1,f(n)是一個(gè)給定的函數(shù)。這種形式的遞歸式很常見(jiàn)，它描述了一種算法：生成a個(gè)子問(wèn)題，每個(gè)子問(wèn)題的規(guī)模是原問(wèn)題規(guī)模的1/b，分解和合并步驟總共花費(fèi)時(shí)間為f(n)。

關(guān)于這三種方法的具體情況，我會(huì)將它整理在下一篇文章中。

參考文獻(xiàn)：Thomas H.Cormen《算法導(dǎo)論》，機(jī)械工業(yè)出版社， 2006-9-1