iT邦幫忙

2021 iThome 鐵人賽

DAY 7
0
自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列 第 7

Day-7 Divide-and-Conquer-2 : 求解遞迴式

如何求解遞迴式

目前主要有三種方法來求解遞迴式(至今沒有任何一個好的演算法可以有效地解決遞迴式)

代換法(substitution method)

他主要遵循以下三種想法

  1. 猜大概的答案,例如猜測演算法大約為https://chart.googleapis.com/chart?cht=tx&chl=%7Bcn%7D%5E2
  2. 我們要試著解出常數c,我們會試著驗證這個遞迴式是否成立,使用數學歸納法進行驗證。
  3. 找到常數,使問題或是我們的想法可以成立。

Example 1. https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3D4T(n%2F2)%20%2B%20n, https://chart.googleapis.com/chart?cht=tx&chl=T(1)%3DΘhttps://chart.googleapis.com/chart?cht=tx&chl=(1)
我們先猜測大約https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20O(n%5E3)
先證明基本情況,https://chart.googleapis.com/chart?cht=tx&chl=T(1)%20%3D%20Θhttps://chart.googleapis.com/chart?cht=tx&chl=(1) https://chart.googleapis.com/chart?cht=tx&chl=%3C%3D%20%7Bc_1%7D%5E3,當c足夠大時,不等式成立。
接下來證明https://chart.googleapis.com/chart?cht=tx&chl=T(n)最多達到https://chart.googleapis.com/chart?cht=tx&chl=%7Bcn%7D%5E3,我們將這個表示式展開,https://chart.googleapis.com/chart?cht=tx&chl=T(k)%3C%3D%7Bck%7D%5E3https://chart.googleapis.com/chart?cht=tx&chl=k%20%3C%3D%20n成立,這裡不使用Big-O符號作為表示原因在於不能對Big-O符號進行歸納,以下面例子來說:

假設https://chart.googleapis.com/chart?cht=tx&chl=n%20%3D%20O(1),當n足夠大時,n會小於等於常數1,也就是n不會超出常數時間。如果這個為真,那任何演算法都將會是常數時間複雜度,但顯然這是錯的
基本情況https://chart.googleapis.com/chart?cht=tx&chl=1%20%3D%20O(1)
根據數學歸納法,如果假設https://chart.googleapis.com/chart?cht=tx&chl=n%20-%201%20%3D%20O(1)
我們可以推出https://chart.googleapis.com/chart?cht=tx&chl=n%20%3D%20(n%20-%201)%20%2B%201,如果https://chart.googleapis.com/chart?cht=tx&chl=n%20-%201https://chart.googleapis.com/chart?cht=tx&chl=O(1),1也是https://chart.googleapis.com/chart?cht=tx&chl=O(1)
則總和還是https://chart.googleapis.com/chart?cht=tx&chl=O(1),因此由數學歸納法,https://chart.googleapis.com/chart?cht=tx&chl=n%20%3D%20O(1)正確

但這是一個錯誤的證明,問題點是我們忽略了常數的變化https://chart.googleapis.com/chart?cht=tx&chl=O(1)%20%2B%20O(1)可能會使常數加倍,如果是有限情況下,常數不斷加倍仍然是常數,但如果這是一個無窮表示式,常數乘了n倍,那就會出問題了,常數會根據n變化,因此不能被忽略。

為了避免上面這個問題,於是我們將常數寫出來,以k做為表示,https://chart.googleapis.com/chart?cht=tx&chl=T(k)%3C%3D%7Bck%7D%5E3https://chart.googleapis.com/chart?cht=tx&chl=k%20%3C%20n成立,我們將https://chart.googleapis.com/chart?cht=tx&chl=T(n)展開,https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3D4T(%5Cfrac%7Bn%7D%7B2%7D)%20%2B%20n,根據我們上面的歸納假設
https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3D4T(%5Cfrac%7Bn%7D%7B2%7D)%20%2B%20n%20%3C%3D%204c(%5Cfrac%7Bn%7D%7B2%7D)%5E3%20%2B%20n
https://chart.googleapis.com/chart?cht=tx&chl=%3D%20%5Cfrac%7B1%7D%7B2%7Dcn%5E3%2Bn
https://chart.googleapis.com/chart?cht=tx&chl=%3D%20cn%5E3%20-%20(%5Cfrac%7B1%7D%7B2%7Dcn%5E3-n)(小括弧部分為剩餘項,是為了化簡到https://chart.googleapis.com/chart?cht=tx&chl=cn%5E3)
https://chart.googleapis.com/chart?cht=tx&chl=%3C%3D%20cn%5E3, 當餘項大於或是等於零時

我們證明一下餘項必定大於或等於零,如果c為2,則https://chart.googleapis.com/chart?cht=tx&chl=n%5E3%20-%20n必定大於零成立,如果c為1,則https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7B1%7D%7B2%7Dn%5E3%20-%20n,當n大於1點多時,必成立。

到這裡我們證明完畢https://chart.googleapis.com/chart?cht=tx&chl=T(n)小於或等於一個常數乘上https://chart.googleapis.com/chart?cht=tx&chl=n%5E3,這個就是https://chart.googleapis.com/chart?cht=tx&chl=T(n)的上界,但其實這不是一個嚴格的上界,因為https://chart.googleapis.com/chart?cht=tx&chl=n%5E2也同樣會成立。這裡所證明的不是https://chart.googleapis.com/chart?cht=tx&chl=T(n)的答案就是https://chart.googleapis.com/chart?cht=tx&chl=n%5E3,而是https://chart.googleapis.com/chart?cht=tx&chl=T(n)不會超過https://chart.googleapis.com/chart?cht=tx&chl=n%5E3這件事情。

我們試著證明https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20O(n%5E2)
https://chart.googleapis.com/chart?cht=tx&chl=T(k)%3C%3D%7Bck%7D%5E2https://chart.googleapis.com/chart?cht=tx&chl=k%20%3C%20n
https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%204T(%5Cfrac%7Bn%7D%7B2%7D)%20%2B%20n,使用上面歸納法的假設將https://chart.googleapis.com/chart?cht=tx&chl=T(%5Cfrac%7Bn%7D%7B2%7D)展開
https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%204T(%5Cfrac%7Bn%7D%7B2%7D)%20%2B%20n%20%3C%3D%204c(%5Cfrac%7Bn%7D%7B2%7D)%5E2%20%2B%20n
https://chart.googleapis.com/chart?cht=tx&chl=%7Bcn%7D%5E2%2Bn
https://chart.googleapis.com/chart?cht=tx&chl=%7Bcn%7D%5E2%2B(n),(小括號的部分式為餘項)
https://chart.googleapis.com/chart?cht=tx&chl=%7Bcn%7D%5E2-(-n),我們必須讓餘項非負,因為對於遞迴式來說,只討論大於等於1的情況
寫到這裡我們會發現我們無法完成這個歸納法,因此,我們需要修改我們假設
假設https://chart.googleapis.com/chart?cht=tx&chl=T(k)%20%3C%3D%20%7Bc_1%7Dk%5E2-%7Bc_2%7Dk%20https://chart.googleapis.com/chart?cht=tx&chl=k%20%3C%20n,這裡我們改進了我們的歸納法假設,我們之前用的假設是與目前相比較弱的假設,在現在這個假設中,我們把低次項加入進來考慮,先前的假設忽略了常數項與低次項。

我們這裡之所以考慮進來低次項,原因是我們期望在解遞迴式的過程,可以把n給消除掉,只留下https://chart.googleapis.com/chart?cht=tx&chl=%7Bcn%7D%5E2,下面開始證明


https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%204T(%5Cfrac%7Bn%7D%7B2%7D)%20%2B%20n
假設https://chart.googleapis.com/chart?cht=tx&chl=T(k)%20%3C%3D%20%7Bc_1%7Dk%5E2-%7Bc_2%7Dkhttps://chart.googleapis.com/chart?cht=tx&chl=k%20%3C%20n
https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%204T(%5Cfrac%7Bn%7D%7B2%7D)%20%2B%20n%20%3C%3D%204%5Bc_1(%5Cfrac%7Bn%7D%7B2%7D)%5E2-c_2(%5Cfrac%7Bn%7D%7B2%7D)%5D%20%2B%20n
https://chart.googleapis.com/chart?cht=tx&chl=c_1n%5E2%2B(1-2c_2)n,這裡使用了更強的歸納假設,因此需要留下最次低項
https://chart.googleapis.com/chart?cht=tx&chl=c_1n%5E2-c_2n%20-%20%5B(-1%2Bc_2)n%5D 中括號部分為餘項,同時我們希望餘項非負
我們發現當https://chart.googleapis.com/chart?cht=tx&chl=c_2%20%3E%3D%201時,餘項恆正,因此證明
https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3C%3D%20c_1n%5E2-c_2n,當https://chart.googleapis.com/chart?cht=tx&chl=c_2%20%3E%3D%201

接著回頭看到基本情況的部分
https://chart.googleapis.com/chart?cht=tx&chl=T(1)%20%3C%3D%20c_11%5E2-c_2%2C%20T(1)%20%3D Θhttps://chart.googleapis.com/chart?cht=tx&chl=(1)
我們會發現到,https://chart.googleapis.com/chart?cht=tx&chl=c_2需要大於等於1,那https://chart.googleapis.com/chart?cht=tx&chl=c_1需要足夠大,才能滿足https://chart.googleapis.com/chart?cht=tx&chl=T(1)%20%3D Θhttps://chart.googleapis.com/chart?cht=tx&chl=(1),因此整個歸納法的精確結論如下
https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3C%3D%20c_1n%5E2-c_2n,當https://chart.googleapis.com/chart?cht=tx&chl=c_2%20%3E%3D%201https://chart.googleapis.com/chart?cht=tx&chl=c_1相對於https://chart.googleapis.com/chart?cht=tx&chl=c_2足夠大時

遞迴樹法(recursion-tree method)

遞迴樹解法,顧名思義是把遞迴以樹的形式展開,雖然直覺,但是相較於代換法沒有那麼的嚴謹,中間遞迴過程有時候會以...省略,這裡需要特別注意,若要求嚴謹,可以使用代換法去驗證遞迴樹,但一般來說不會那麼做。

Example 1. https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20T(n%2F4)%20%2B%20T(n%2F2)%20%2B%20n%5E2
首先,我們先將這個遞迴式以樹的形式表達,如下圖

再將https://chart.googleapis.com/chart?cht=tx&chl=T(n%2F4)https://chart.googleapis.com/chart?cht=tx&chl=T(n%2F2)帶入https://chart.googleapis.com/chart?cht=tx&chl=T(n),也就是遞迴展開的概念。

然後一直不斷下去,直到最後,我們會得到一堆葉節點,為Θhttps://chart.googleapis.com/chart?cht=tx&chl=(1)

這裡我們可以注意到一件事情,左子樹和右子樹的遞迴展開速度是不一樣的,會導致兩子樹的高度不同,我們會難以計算葉子的數量,但我們能夠確定一件事情,就是葉子的數量一定會少於n,一開始問題的規模為n,每一次遞迴會減少1/4,因此當遞迴結束於,葉的數量必定會少於n,我們試著把這個樹每一層的結果加總

我們會發現每一層都會相差https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%7B5%7D%7B16%7D,我們把加總,也就是求這個等比級數的何
https://chart.googleapis.com/chart?cht=tx&chl=(1%20%2B%20%5Cfrac%7B5%7D%7B16%7D%20%2B%20%5Cfrac%7B25%7D%7B256%7D%20%2B%20...%20%2B%20%5Cfrac%7B5%5Ek%7D%7B16%5Ek%7D%2B...)n%5E2
https://chart.googleapis.com/chart?cht=tx&chl=%5Csum_%7Bi%3D0%7D%5Ek%5Cfrac%7B5%5Ek%7D%7B16%5Ek%7D
我們知道上面這個公式計算之後,我們會得到某個常數,我們以c為代表,整個等比級數的何為
https://chart.googleapis.com/chart?cht=tx&chl=cn%5E2,且https://chart.googleapis.com/chart?cht=tx&chl=cn%5E2%3C2n%5E2,以Ωhttps://chart.googleapis.com/chart?cht=tx&chl=(n%5E2)表示
而這個方法不嚴謹的地方在於等比級數得假設,我們只驗證了前三項就認定他是等比級數。下面會介紹基於遞迴樹的更嚴謹的方法,稱為主定理(master theorem)。

主定理(master theorem)

主定理有一個限制,那就是只能使用到特定的遞迴式上面,這些遞迴式需要符合https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3DaT(n%2Fb)%2Bf(n)這樣的形式,有a個相同的子問題,每個子問題的規模皆相同,不同於上一個例題,有兩個不同規模的子問題。

還有一些限制條件,a需要大於或是等於1,也就是至少要遞迴一次,b需要嚴格大於1,因為我們必須讓子問題的規模越來越小,f(n)需要趨近於正(asymptotically positive),也就是當n足夠大時,https://chart.googleapis.com/chart?cht=tx&chl=f(n)必須為正,以數學式表示,即為存在某一個點https://chart.googleapis.com/chart?cht=tx&chl=n_0,當https://chart.googleapis.com/chart?cht=tx&chl=n%3E%3Dn_0時,https://chart.googleapis.com/chart?cht=tx&chl=f(n)%20%3E%200

主定理是基於將非遞迴函數https://chart.googleapis.com/chart?cht=tx&chl=f(n)https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blogb%5Ea%7D進行比較,而比較的過程,會出現三種情況,分別為大於,等於,小於,我們可能會直觀的想到使用little-o,big-Θ,和smail-ω做為表示,但是,中間會存在一些灰色地帶,是我們無法用這些符號進行表示的。

  • 第一種情況,對於εhttps://chart.googleapis.com/chart?cht=tx&chl=%3E0的情況
    https://chart.googleapis.com/chart?cht=tx&chl=f(n)%20%3D%20O(n%5E%7Blogb%5Ea-%5Cvarepsilon%7D),則
    https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(n%5E%7Blogb%5Ea%7D)
  • 第二種情況,對於εhttps://chart.googleapis.com/chart?cht=tx&chl=%3E%3D0
    https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(n%5E%7Blogb%5Ea%7Dlg%5E%7B%5Cvarepsilon%2B1%7Dn),則
    https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(n%5E%7Blogb%5Ea%7Dlg%5E%7B%5Cvarepsilon%2B1%7Dn)
  • 第三種情況,對於εhttps://chart.googleapis.com/chart?cht=tx&chl=%3E0的情況,且需要確保https://chart.googleapis.com/chart?cht=tx&chl=f(n)在遞迴時不斷地變小
    https://chart.googleapis.com/chart?cht=tx&chl=f(n)%20%3D%20%5COmega(n%5E%7Blogb%5E%7Ba%2B%5Cvarepsilon%7D%7D)且對某個常數https://chart.googleapis.com/chart?cht=tx&chl=c%3C1和足夠大的n,有https://chart.googleapis.com/chart?cht=tx&chl=af(%5Cfrac%7Bn%7D%7Bb%7D)%3C%3Dcf(n),則
    https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(f(n))

Example 1. https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3D4T(%5Cfrac%7Bn%7D%7B2%7D)%2Bn
首先,先確認是否符合主定理的限制,https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3DaT(n%2Fb)%2Bf(n)
發現符合限制,找到https://chart.googleapis.com/chart?cht=tx&chl=a%20%3D%204%2C%20b%20%3D%202,先確認https://chart.googleapis.com/chart?cht=tx&chl=T(n)是屬於哪一種情況,也就是先計算https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea
https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea,將https://chart.googleapis.com/chart?cht=tx&chl=a%20%3D%204%2C%20b%20%3D%202代入,得到
https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7D2%5E4%20%3D%20n%5E2
我們比較https://chart.googleapis.com/chart?cht=tx&chl=f(n)https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea,發現https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea%3Ef(n),也就是https://chart.googleapis.com/chart?cht=tx&chl=f(n)%20%3D%20O(n%5E%7B2-%5Cvarepsilon%7D),因此屬於第一種情況,則結果為https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(n%5E%7Blog_b%5Ea%7D),也就是https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(n%5E2)

Example 2. https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3D4T(%5Cfrac%7Bn%7D%7B2%7D)%2Bn%5E2
首先,先確認是否符合主定理的限制,https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3DaT(n%2Fb)%2Bf(n)
發現符合限制,找到https://chart.googleapis.com/chart?cht=tx&chl=a%20%3D%204%2C%20b%20%3D%202,先確認https://chart.googleapis.com/chart?cht=tx&chl=T(n)是屬於哪一種情況,也就是先計算https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea
https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea,將https://chart.googleapis.com/chart?cht=tx&chl=a%20%3D%204%2C%20b%20%3D%202代入,得到
https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7D2%5E4%20%3D%20n%5E2
我們比較https://chart.googleapis.com/chart?cht=tx&chl=f(n)https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea,發現https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea%3E%3Df(n),也就是https://chart.googleapis.com/chart?cht=tx&chl=f(n)%20%3D%20%5CTheta(n%5E%7Blogb%5Ea%7Dlg%5E%5Cvarepsilon%20n),因此屬於第二種情況,則結果為https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(n%5E%7Blogb%5Ea%7Dlg%5E%7B%5Cvarepsilon%20%2B1%7Dn),也就是https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(n%5E%7B2%7Dlgn)

Example 3. https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3D4T(%5Cfrac%7Bn%7D%7B2%7D)%2Bn%5E3
首先,先確認是否符合主定理的限制,https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3DaT(n%2Fb)%2Bf(n)
發現符合限制,找到https://chart.googleapis.com/chart?cht=tx&chl=a%20%3D%204%2C%20b%20%3D%202,先確認https://chart.googleapis.com/chart?cht=tx&chl=T(n)是屬於哪一種情況,也就是先計算https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea
https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea,將https://chart.googleapis.com/chart?cht=tx&chl=a%20%3D%204%2C%20b%20%3D%202代入,得到
https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7D2%5E4%20%3D%20n%5E2
我們比較https://chart.googleapis.com/chart?cht=tx&chl=f(n)https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea,發現https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7Blog%7Db%5Ea%3Cf(n),也就是https://chart.googleapis.com/chart?cht=tx&chl=f(n)%20%3D%20%5COmega(n%5E%7Blogb%5E%7Ba%2B%5Cvarepsilon%7D%7D),因此屬於第三種情況,則結果為https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(f(n)),也就是https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20%5CTheta(n%5E%7B3%7D)

參考資料: Introduciton to algorithms 3rd


上一篇
Day-6 Divide-and-Conquer-1 : merge sort
下一篇
Day-8 Divide-and-Conquer-3 : 二分搜尋法, 費波那契數列, Strassen’s演算法
系列文
從0開始啃Introduction of algorithms心得與記錄30

尚未有邦友留言

立即登入留言