tags: ADA 3.2 Recursion-Tree Method

ADA 3.2: Recursion-Tree Method

Textbook Chapter 4.4 - The recursion-tree method for solving recurrences

Review

Merge Sort

之前ADA 2.4有用過 (Merge Sort)

$T(n)=\{\begin{array}{ll}O(1)& \text{if }n=1\\ 2T(n/2)+O(n)& \text{if }n\ge 2\end{array}$

* T(n): 處理size為N所耗費的時間

Recursion-Tree Method 遞迴樹法

Solving recurrence

• Substitution method(取代法)
• Recursion-Tree method(遞迴樹法)
• Master method(套公式大法/大師法)

Steps to solve

• Expand a recurrence into a tree (把樹給展開)
• Sum up the cost of all nodes as a good guess (加總)
• Verify the guess as in substitution method (驗證)

Advantages

• Promote intuition
• Generate good guesses for the subtitution method
  => 比較直覺, 容易猜

Recursion-Tree Example

舉例

$T(n)=2T(n/2)+cn$ (Merge Sort)

每層都是cn, 故只要求出樹高就知道總和

$2^h=n$

$=>k=lo{g}_{2}n$

總和則為

$cn\cdot$ tree height

$=>cn\cdot lo{g}_{2}n$

$=>O(nlogn)$

$T(n)=T(n/4)+T(n/2)+c{n}^2$

$T(n)=T(n/4)+T(n/2)+c{n}^2$

$=(T(\frac{n}{4}/4)+T(\frac{n}{4}/2)+c(\frac{n}{4}{)}^2)+(T(\frac{n}{2}/4)+T(\frac{n}{2}/2)+c(\frac{n}{2}{)}^2)+c{n}^2$

$=...$

累加後為

$T(n)\le (1+\frac{5}{16}+(\frac{5}{16}{)}^2+(\frac{5}{16}{)}^3+...)c{n}^2$

$=\frac{(1-(\frac{5}{16}{)}^n)}{1-\frac{5}{16}}c{n}^2$

$=\frac{16}{11}c{n}^2$

$=O(n^2)$

當子問題足夠小時(切割次數趨近無限), 可以以O(1)秒解掉

$(\frac{5}{16}{)}^n=0$就可以忽略

等比級數相加公式
💡

$a_1=a,a_n=a\cdot r^{n-1},S_n=\frac{a(1-r^n)}{1-r}$

Proof

$S_0=a+ar+a\cdot r^2+a\cdot r^3+...+a\cdot r^{n-1}...(1)$

兩邊同乘

$r$

$r\cdot S_0=ar+a\cdot r^2+a\cdot r^3+...+a\cdot r^{n-1}+a\cdot r^n...(2)$

$(1)-(2)$

$(1-r)\cdot S_0=a-a\cdot r^n$

$S_0=\frac{a-a\cdot r^n}{(1-r)}$

$=\frac{a(1-r^n)}{(1-r)}$

簡單證明

當

$0<=r<=1$時