演算法導論題解

㈠ 《演算法導論》第三章-思考題（參考答案）

（多項式的漸進行為） 假設 是一個關於 的 次多項式，其中 ， 是一個常量。使用漸進符號的定義來證明下面的性質。

a. 若 ，則 。

b. 若 ，則 。

c. 若 ，則 。

d. 若 ，則 。

e. 若 ，則 。

已知： ，易得 。

故 。

情況 1：

，即： 。

故 。

情況 2：

，即： 。

故 。

情況 3：

，即： 。

故 。

情況 4：

，即： 。

故 。

情況 5：

，即： 。

故 。

（相對漸進增長） 為下表中的每對表達式 指出 是否是 的 或 。假設 且 均為常量。回答應以表格的形式，將「是」或「否」寫在每個空格中。

a.

令 代替 ，並令 代替 a，可得：

即： 。

又：若 。故： 。

b.

故， 。

令 。故 。

c.

。又 的值為在區間 中波動，故 與 無任何關系

d.

嚴格遞增，故對於任意正常量 ，總存在 ，使得 ，即：

也易證：故對於任意正常量 ，總存在 ，使得 ，即：

e.

。故 。

f.

故，

又， 是嚴格遞增的函數。故，

故， ，也即

也即

（根據漸進增長率排序）

a. 根據增長的階來排序下面的函數，即求出滿足 的函數的一種排列 。把你的表劃分成等價類，使得函數 和 在相同類中當且僅當 。

b.給出非負函數 的一個例子，使得對所有在（a）部分中的函數 ， 既不是 也不是 。

（漸進記號的性質） 假設 和 為漸進正函數。證明或反駁下面的每個猜測。

a. 蘊含 。

錯。例如： 。

b. 。

錯。例如： 。

c. 蘊含 ，其中對所有足夠大的 ，有 且 。

正確。

對於足夠大的 ，有 ；且 ，則存在正常量 ，使得 ，有

​

​

又 ，故當 ，且 足夠大，有：

​

故原問題成立。

d. 蘊含 。

錯。例如： 。

e. 。

當 時， ；其他條件下，不成立。

f. 蘊含 。

正確。 ，即存在正常量 ，使得 ，有

​ ，即

令 ，得 。

g. 。

錯。例如： 。

h. 。

正確。

易得， ，即存在正常量 ，使得 ，都有 。

令 ，即存在正常量 ，使得 ，都有 。

令 ，則 ，有 。

即 。

（ 與 的一些變形） 某些作者用一種與我們稍微不同的方式來定義 ；假設我們使用 （讀作「 無窮」）來標識這種可選的定義。若存在正常量 ，使得對無窮多個整數 ，有 ，則稱 。

a. 證明：對漸進非負的任意兩個函數 和 ，或者 或者 或者二者均成立，然而，如果使用 來代替 ，那麼該命題並不為真。

主要缺少了 這個條件；則若 ，必然有無窮多個正整數 ，使得 成立；

若 ，則上述兩者均成立；

反例： ，但 。

b. 描述用 代替 來刻畫程序運行時間的潛在優點與缺點。

優點： 對下屆的要求更寬松，可以兼容更多的情況；

缺點： 並非嚴格的漸進下界。因此實際意義並不大。

​ 某些作者也用一種稍微不同的方式來定義 ；假設使用 來標識這種可選的定義。我們稱 當且僅當 。

c. 如果使用 代替 但仍然使用 ，定理 3.1 中的「當且僅當」的每個方向將出現什麼情況？

沒有變化。 成立意味著 漸進非負，故 。

​ 有些作者定義 （讀作「軟 」）來意指忽略對數因子的 ：

：存在正常量 和 ，使得對所有 ，有 。

d. 用一種類似的方式定義 和 。證明與定理 3.1 相對應的類似結論。

：存在正常量 和 ，使得對所有 ，有 。

：存在正常量 和 ，使得對所有 ，有 。

（多重函數） 我們可以把用於函數 中的多重操作符 * 應用於實數集上的任意單調遞增函數 。對給定的常量 ，我們定義多重函數 為

​

該函數不必再所有情況下都是良定義的。換句話說，值 是為縮小其參數到 或更小所需函數 重復應用的數目。

​ 對如下每個函數 和常量 ，給出 的一個盡量緊確的界。

㈡ 圖的廣度、深度優先搜索和拓撲排序

廣度優先搜索是最簡單的圖搜索演算法之一。之所以得名是因為該演算法始終將已經發現的結點集合，沿著其 廣度方向 向外擴展去尋找未發現結點。
具體演算法執行過程如下圖所示：

深度優先搜索，只有可能就在圖中盡可能的 深入 ，總是從最近才發現的結點出發，尋找下一個結點。
具體演算法執行過程如下圖所示：

拓撲排序是計算機中經常遇到的概念，下面用於《演算法導論》的定義

如下圖3-1所示，事件E1完成之後，可以同時執行事件E2和E3，兩事件執行結束之後，執行事件E4，最後可以同時執行事件E5和E6。每個事件的執行都依賴於它之前事件是否執余槐陪行完成，執行的順序是固定的，這樣的線性順序就是 拓撲排序 。

圖的廣度、深度優先搜索和拓撲排序是圖論演算法中的基礎，也是實踐中經常遇到的問題。在考研和面試筆試中會通過選擇題或者填空題考察，學習理解上文圖示中的演算法思想，輔助練習問題不大。當然也有關於這里的演算法題，例如LeetCode815公交路線問題，就是利用圖的廣度優先搜索求解，因豎蠢為解題復雜，並且在平時的應試中出現概率不大，這里不做詳細講解。有興趣的可明段以在LeetCode中搜索，題目後面有我提交過的題解。

㈢ 《演算法導論》三種解遞歸式的方法

代入法可以用來確定一個遞歸式的上界或下界。這種方法很有效，但只能用於解的形式很容易猜的情形。

例如，我們需要確定下面遞歸式的上界：

該遞歸式與歸並排序相似，我們可以猜測其解為

代入法要求證明，恰當選擇常數 c>0，可有 T(n)≤cn lgn。首先假設此上界對所有正數 m<n 都成立，特別是對於 m=n/2，有 T(n/2)≤c(n/2)lg(n/2)。將其代入遞歸式，得到：

其中，只要 c≥1，最後一步都會成立。

並不存在通用的方法來猜測遞歸式的正確解，但總有一些試探法可以幫助做出好的猜測：

如果某個遞歸式與先前見過的類似，則可猜測該遞歸式有類似的解。如，遞歸式

看起來比較難解，因為右式 T 的自變數中加了 17，但我們可以猜測這個多出來的項對解的影響不大，因為當 n 很大時， 與 之間的差別並不大，兩者都將 n 分成均勻的兩半。

另一種方法是先證明遞歸式的較松的上下界，然後再縮小不確定性區間。例如，對遞歸式 ，因為遞歸式中有 n，而我們可以證明初始上界為 。然後，逐步降低其上界，提高其下界，直到達到正確的漸近確界 。

有時，我們或許能夠猜出遞歸式解的漸近界，但卻會在歸納證明時出現一些問題。通常，問題出在歸納假設不夠強，無法證明其准確的界，遇到這種情況時，可以去掉一個低階項來修改所猜測的界，以使證明順利進行。如下面的遞歸式：

可以猜測其解為 ，即要證明對適當選擇的 c，有 。有所猜測的界對遞歸式做替換，得到

由此無法得到 ，無論 c 的值如何。如果猜測一個更大的界，如 ，雖然這確實是上界，但事實上，所猜測的解 卻是正確的。為了證明這一點，要做一個更強的歸納假設。

從直覺上說，猜測 幾乎是正確的，只是差了一個常數 1，即一個低階項，然而，就因為差了一項，數學歸納法就無法證明出期望的結果。從所作的猜測中減去一個低階項，即 是個常數。現在有

只要 b≥ 1。這里，c 要選的足夠大，以便能處理邊界條件。

你可能會覺得從所作的猜測中減去一項有點兒與直覺不符。為什麼不是增加一項來解決問題呢？關鍵在於要理解我們是在用數學歸納法：通過對更小的值作更強的假設，就可以證明對某個給定值的更強的結論。

在運用漸近表示時很容易出錯。例如，對遞歸式 ，由假設 ，並證明

就是錯誤的，因為 c 是常數，因而錯誤地證明了 。錯誤在於沒有證明歸納假設的准確形式，即 。

有時，對一個陌生的遞歸式作一些簡單的代數變換，就會使之變成讀者較熟悉的形式。如下例子：

這個式子看上去比較難，但可以對它進行簡化，方法是改動變數。為了方便起見，不考慮數的截取整數問題，如將 化為整數。設 ，得

再設 ，得到新的遞歸式

這個式子看起來與 就非常像了，這個新的遞歸式的界是： 。將 帶回 ，有 。

有時候，畫出一個遞歸樹是一種得到好猜測的直接方法。在遞歸樹中，每一個節點都代表遞歸函數調用集合中一個子問題的代價。將樹中每一層內的代價相加得到一個每層代價的集合，再將每層的代價相加，得到的結果是所有層次的總代價。當用遞歸式表示分治演算法的運行時間時，遞歸樹的方法尤其有用。

遞歸樹最適合用來產生好的猜測，然後用代入法加以驗證。但使用遞歸樹產生好的猜測時，通常可以容忍小量的「不良量」，因為稍後就會證明所做的猜測。如果畫遞歸樹時非常地仔細，並且將代價都加了起來，那麼就可以直接用遞歸樹作為遞歸式的解的證明。

在講述例子之前，我們先來看一個幾何級數公式

對於實數 x≠1，式

是一個幾何級數（或稱指數級數），其值為

當和是無限的且 |x|<1 時，有無限遞減幾何級數

我們以遞歸式

為例來看一下如何用遞歸樹生成一個好的猜測。首先關注如何尋找解的一個上界，因為我們知道舍入對求解遞歸式通常沒有影響（此處即是我們需要忍受不精確的一個例子），因此可以為遞歸式

創建一顆遞歸樹，其中已將漸近符號改寫為隱含的常數系數 c>0。

構造的遞歸樹如下：

求所有層次的代價之和，確定整棵樹的代價：

最後的這個公式看起來不夠整潔，但我們可以再次充分利用一定程度的不精確，並利用無限遞減幾何級數作為上界。回退一步，得到：

此時，我們得到了遞歸式的一個猜測，在上面的例子里， 系數形成了一個遞減的等比級數，可知這些系數的總和的上界是常數 。由於樹根所需的代價為 ，所以根部的代價占總代價的一個常數部分。換句話說，整棵樹的總代價是由根部的代價所決定的。

事實上，如果 確實是此遞歸式的上界，那麼它一定是確界，為什麼呢？第一個遞歸調用所需要的代價是 ，所以 一定是此遞歸式的下界。

現在我們可以使用代換法來驗證猜測的正確性， 是遞歸式 的一個上界。只需要證明，當某常數 d>0， 成立。適用與前面相同的常數 c>0，有

只要 d≥ ，最後一步都會成立。

上圖是遞歸式

對應的遞歸樹。我們還是使用 c 來代表 項常數因子。當將遞歸樹內各層的數值加起來時，可以得到每一層的 cn 值。從根部到葉子的最長路徑是 。因為當 時， ，所以樹的深度是 。

直覺上，我們預期遞歸式的解至多是層數乘以每層的代價，也就是 。總代價被均勻地分布到遞歸樹內的每一層上。這里還有一個復雜點：我們還沒有考慮葉子的代價。如果這棵樹是高度為 的完整二叉樹，那麼有 個葉子節點。由於葉子代價是常數，因此所有葉子代價的總和為 ，或者說 。然而，這棵遞歸樹並不是完整的二叉樹，少於 個葉子，而且從樹根往下的過程中，越來越多的內部結點在消失。因此，並不是所有層次都剛好需要 cn 代價；越靠近底層，需要的代價越少。我們可以計算出准確的總代價，但記住我們只是想要找出一個猜測來使用到代入法中。讓我們容忍這些誤差，而來證明上界為 的猜測是正確的。

事實上，可以用代入法來證明 是遞歸式解的上界。下面證明 ，當 d 是一個合適的正值常數，則

上式成立的條件是 。因此，沒有必要去更准確地計算遞歸樹中的代價。

主方法給出了求解遞歸式的「食譜」方法，即將規模為 n 的問題劃分為 a 個子問題的演算法的運行時間，每個子問題規模為 ，a 和 b 是正常數。a 個子問題被分別遞歸地解決，時間各為 。劃分原問題和合並答案的代價由函數 描述。

從技術正確性角度來看，遞歸式實際上沒有得到很好的定義，因為 可能不是一個整數。但用 向上取整或向下取整來代替 a 項 並不影響遞歸式的漸近行為，因而，在寫分治演算法時略去向下取整和向上取整函數會帶給很大的方便。

其中我們將 n/b 解釋為 n 除以 b 的向下取整或向上取整。那麼 T(n) 有如下漸近界：

在使用主定理之前，我們需要花一點時間嘗試理解它的含義。對於三種情況的每一種，將函數 f(n) 與函數 進行比較。直覺上，兩個函數較大者決定了遞歸式的解。若函數 更大，如情況 1，則解為 T(n)= ( )。若函數 f(n) 更大，如情況 3，則解為 T(n)= (f(n))。若兩個函數大小相當，如情況 2，則乘上一個對數因子，解為 T(n)= ( )= ( )。

另外還有一些技術問題需要加以理解。在第一種情況下，不僅要有 小於 ，還必須是多項式地小於，也就是說， 必須漸近小於 ，要相差一個因子 ，其中 是大於 0 的常數。在第三種情況下，不是 大於 就夠了，而是要多項式意義上的大於，而且還要滿足「正則」條件 。

注意：三種情況並沒有覆蓋所有可能的 f(n)。當 f(n) 只是小於 但不是多項式地小於時，在第一種情況和第二種情況之間就存在一條「溝」。類似情況下，當 f(n) 大於 ，但不是多項式地大於時，第二種情況和第三種情況之間就會存在一條「溝」。如果 f(n) 落在任一條「溝」中，或是第三種情況種規則性條件不成立，則主方法就不能用於解遞歸式。

使用主方法很簡單，首先確定主定理的哪種情況成立，即可得到解。

例如：

對於這個遞歸式，我們有 a=9，b=3，f(n)=n，因此 = = 。由於 f(n) = ，其中 ， 因此可以應用於主定理的情況 1，從而得到解 T(n) = Θ( ) 。

現在考慮

其中，a = 1， b = 3/2， f(n) = 1，因此 = = = 1 。由於 f(n) = = Θ(1) ，因此可應用於情況2，從而得到解 T(n) = Θ( ) 。

對於遞歸式

我們有 a = 3，b = 4，f(n) = nlgn，因此 = =O( )。由於 當 n，其中 ，因此，如果可以證明正則條件成立，即應用於情況 3。當 n 足夠大時，對於 ， ，因此，由情況 3，遞歸式的解為 T(n)= ( )。

主方法不能用於如下遞歸式：

雖然這個遞歸式看起來有恰當的形式：a=2，b=2， ，以及 。你可能錯誤地認為應該應用情況 3，因為 漸近大於 。問題出現在它並不是多項式意義上的大於。對任意正常數 ，比值 都漸近小於 。因此，遞歸式落入了情況 2 和情況 3 之間的間隙。

證明分為兩部分。第一部分分析「主」遞歸式 ，並作了簡化假設 僅定義在 b>1 的整數冪上，即 ， ， ，…。這部分從直覺上說明該定理為什麼是正確的。第二部分說明如何將分析擴展至對所有的正整數 n 都成立，主要是應用數學技巧來解決向下取整函數和向上取整函數的處理問題。

取正合冪時的證明

對於遞歸式

此時的假設是 n 為 b>1 的正合冪，且 b 不必是整數。分析可分成三個引理說明，第一個引理是將解原遞歸式的問題歸約為對一個含和式的求值的問題。第二個引理決定含和式的界，第三個引理把前兩個合在一起，證明當 n 為 b 的正合冪時主定理成立。

引理一 ：設 a≥1，b>1 為常數，f(n) 為定義在 b 的正合冪上的非負函數。定義 如下：

其中 i 是正整數，則有

證明：如下圖。根節點代價為 f(n)，它有 a 個子女，每個代價是 。（為方便起見可將 a 視為整數，但這對數學推導沒什麼影響。）每個子女又各有 a 個子女，代價為 。這樣就有 個結點離根的距離為 2。一般地，距根為 j 的結點有 個，每一個的代價為 。每一個葉結點的代價為 ，每一個都距根 ，因為 。樹中共有 個葉結點。

可以將樹中各層上的代價加起來而得到方程 ，第 j 層上內部結點的代價為 ，故各層內部結點的總代價和為

在其所基於的分治演算法中，這個和值表示了將問題分解成為子問題並將子問題的解合並時所花的代價，所有葉子的代價（即解 個規模為 1 的子問題的代價）為 。

根據遞歸樹，主定理的三種情況對應於樹中總代價的三種情況：1、由所有葉子節點的代價決定；2、均勻分布在各層上；3、由根結點的代價決定。

引理二 ：設 a≥1，b≥1 為常數， 為定義在 b 的整數冪上的非負函數。函數 由下式定義

對 b 的整數冪，該函數可被漸近限界為：

證明：對情況 1，有 ，這隱含著 。用它對方程 做代換，得

對 O 標記內的式子限界，方法是提出不變項並作簡化，得到一個上升幾何級數：

因為 b 與 都是常數，最後的表達式可化簡為 。用此表達式對 作替換，得

情況 1 得以驗證。

為證情況 2，假設 ，有 。用此式對方程 作替換，得

對 記號中的式子做類似情況 1 中的限界，但所得並非是幾何級數，而是每項都是相同的:

用此方程對 中的和式做替換，有

則情況 2 得以驗證。情況 3 也可以用類似的方式證明。

引理三 ：設 a≥1，b>1 是常量， 是定義在 b 的整數冪上的非負函數。定義 T(n) 如下：

其中 i 是正整數。對於 b 的整數冪，T(n) 可有如下漸近界：

證明：用引理二給出的界來對引理一中的式 求值。對情況 1 有

對情況 2 有

對情況 3 有

㈣ 演算法導論裡面的大師解法是什麼 用大師解法計算下面遞歸表達式的時間復雜度. T(n)=2T(n/2) + Θ(n^0.1)

#a i從0循環到n，演算法復雜度為O(n)。
#b 一共要做n^2/2次加法，演算法復雜度為O(n^2)。
#c 要求一個k，滿足2^k>=n ，演算法復雜度為O(log(n))
#d 注意到這個函數做的事跟#c的函數恰好相反，演算法復雜度相同，也是O(log(n))
#e 因為已算出#g每次做3(n-3)次加法，那麼i從1到n，一共做2/3*(n^2-5n+6)次加法，所以復雜度為O(n^2)。
#f 這個函數可以寫成公式T(n)=T(n-2)+T(n-1)，這個遞歸式跟黃金分割有關系，解這個遞歸式，可以知道 T(n) = O((√5-1/2)^n)
#g 函數調用一共做3(n-3)次加法，所以復雜度為O(n)
PenitentSin 這位兄台的#c 算的不對啦，#g也不對。還有#f，這個雖然是遞歸，但不是遞歸就等於指數級的復雜度，要解遞歸方程才能斷定的。
關於演算法復雜度，《演算法導論》一書中第四章有一個主定理，記住這個定理之後，這些問題就小case了（除了復雜遞歸之外）。

㈤ 演算法導論中，為什麼合並排序的遞歸樹的高度為lgn

符號問題，這里的lg就是指log2，你的理解是正確的！在計算機科學中有些符號的使用跟我們在數學中使用的有區別。比如有時候log用來表示自然對數(以e為底數)。希望對你有幫助！