(1) – Substitution?Method

?

整個recurrence就是研究一個數學表達式：T(n) = aT(n/b)+f(n) ? 意思是先有一個問題T(n), 解決思路為把T(n)切分成a個小問題， 每個小問題的代價是T(n/b), 然后把a個T(n/b)的結果合并起來的代價是f(n)；依次類推，直到T(k)的粒度小到其復雜度是一個常數。很像是遞歸吧～～遞歸只是一種實現方式，這里介紹的是一種思路和評估這種思路復雜度的方法。

經典的評估Recurrence的方法有3種，Substitutuon, Recursion Tree和Master Method.? 看下面的命題：

T(n) = 4T(n/2) + n ,需要證明T(n)=O(n² )

Substitution：

假設T(k) <= ck^2? k<n; 所以 T(n) <= 4(n/2)² +n = n² +n 要證明n² +n<=cn² 好像不容易。

我們換個假設，假設T(k)<=c₁ k² -c₂ k ，這樣的話T(n) <= c₁ n² -(2c₂ -1)n = c₁ n² -c₂ n-(c₂ -1)n. 所以只要 c₂ >= 1,就證明成功了。注意這里，似乎沒有對c₁ 任何限制。其實不是的！對于所有的induction方法來說，我們都需要一個初始條件，T(n₀ ) = H(1) <=c₁ n₀ ² -c₂ n₀ 這里我使用H(1) 代表常數復雜度。為了滿足初始條件，我們需要恰當的選擇 c₁ ，c₂ 和n₀ 。

其實這里的初始條件就對應了算法設計里面的Base Case。Base Case就是將問題切分到最后那個粒度最小的復雜度為常數的Case。就上面的那個例子來說，c₁ 和c₂ ，對運行時起主導作用的是前者，你在實現時設計的Base Case能使c₁ 越小，程序運行越快。

?

(2) – Recursion?Tree

?

T(n) = T(n/3) + T(2n/3) + n

Recursion Tree其實就是Iteration，只不過圖型化以后我們看起來更容易理解了。

T(n) = T(n/3) + T(2n/3) + n
?????? = [T(n/9) + T(2n/9) + n/3] + [T(2n/9) + T(4n/9) + 2n/3]
?????? = ……
畫成圖就是：

?

總的cost就是把每一層的cost加起來。層數就是樹的高度。上面的這個問題有點tricky的。從圖上看分兩種情況，一種以1/3的方式減少n,還有一種是以2/3的方式。前一種方式經過log₃ n次就到達葉子節點，后一種方式經過log_3/2 n次，因為log_3/2 n > log₃ n，樹的高度為log_3/2 n。每一層加起來的代價是cn, 其實越到下面，每一層的cost會小于cn的，因為那時候按照1/3的方式減少的那一枝已經不存在了。

T(n) <= cn x log_3/2 n = O(nlgn)

Recursion tree很直觀，我們可以用它來幫助我們猜測規律，然后再用Substitution方法Double Confirm。

不過無論是Substitution還是Recursion Tree都比較煩，不能馬上得出結果。有人總結了規律，叫做Mater Method。使用Master Method, 我們很快就可以直接寫出T(n)=aT(n/b)+f(n)的時間復雜度。

?

(3) – Master?Method

?

?

前面分別介紹了 Resolving Recurrence(1) – Substitution Method 和 Resolving Recurrence(2) – Recursion Tree 來評估
T(n) = aT(n/b) + f(n) 的時間復雜度。

這一節介紹Master Method，既然叫Master，可見其重要程度。掌握了Master Method,我們可以很快寫出Merge Sort, Heap Sort以及Quick Sort的時間復雜度。

Master Method: ? (在 a>=1 并且 b>1 的情況下)

• 如果f(n) is polynomially smaller than n^log _b ^a , polynomially smaller就是grow slower, 數學表達式f(n)=O(n^log _b ^a-e ), e>0。 T(n) = O(n^log _b ^a )
• 如果f(n) is polynomially same as n^log _b ^a , T(n) = O(n^log _b ^a lgn)
• 如果f(n) is polynomially faster than? n^log _b ^a , 并且 af(n/b) <= cf(n),? c<1 && n>=b , T(n) = H(f(n)) . H表示復雜度相當。

舉個例子T(n)=4T(n/2)+n , 其中a=4, b=2, –> n^log _b ^a =? n² , 而f(n)=n, 屬于第一種情況所以 T(n) = O(n² )。 如果T(n)=2T(n/2)+n, 則屬于第二種情況，T(n) = O(n lgn).

在算法導論中有詳細的證明，太符號化的東西往往難以記憶，下面我們用recursion tree的方式，幫助理解和記憶。

可見， 第一層有一個節點，第二層有a的節點，第 i 層有aⁱ 個節點，所以到葉子節點那層，葉子的個數就是 a的 樹高 次冪。而樹高=log_b n ， 我們可以很容易證明 a^log _b ⁿ = n^log _b ^a 。所以一共有n^log _b ^a 個葉子，每個葉子其實就是我們的initial condition，就是我們的base case，是整個算法的基石。

cost of all the leaves nodes = H(n^log _b ^a )

現在對照recursion tree再來回顧一下Master Method 的 3 種情況：

1. 當所有葉子的代價比根節點高時， O(n^log _b ^a ) > f(n), 從root到leaves，每層的cost在geometry increase,由葉子主導整個算法的時間復雜度，所以 T(n) = O(n^log _b ^a )

2. 當所有葉子的代價和根節點相當時，表示從root 到 leaves的每一層的cost 是 幾乎balance的，總代價應該是 每一層代價乘以樹高， T(n) = n^log _b ^a x log_b n = H(f(n) x log_b n = O(n^log _b ^a lgn)。

3. 當所有葉子的代價比根節點低時，由根節點主導整個算法的時間復雜度。af(n/b) <= cf(n),? c<1 && n>=b 表示把任務T(n)切分成a個T(n/b)的過程中，必須保證a個T(n/b)的合并代價必須小于上層任務的合并代價，并且每次切分，其單個節點的合并代價都是在減少的。簡單來說就是 從root 到leaves的過程中，代價是geometry decrease的。 結論是 T(n) = H(f(n))。

?

?

總結

以上是生活随笔為你收集整理的Resolving Recurrence的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。