tags: ADA 3.3 Master Method

ADA 3.3: Master Method 大師套公式法

Textbook Chapter 4.5 - The master method for solving recurrences

Master Theorem

The proof is in Ch. 4.6 課本 p.118

divide a problem of size n into a subproblems, each of size

$\frac{n}{b}$ is solved in time

$T(\frac{n}{b})$ recursively

Let

$T(n)$ be a positive function satisfying the following recurrence relation

$T(n)=\{\begin{array}{ll}O(1)& \text{if }n\le 1\\ a\cdot T(\frac{n}{b})+f(n)& \text{if }n>1,\end{array}$

符合上面的格式，就可以套用公式

where

$a\ge 1$ and

$b>1$ are constants.

• Case 1: If
  $f(n)=O(n^{{\log }_{b}a-ϵ})$ for some constant
  $ϵ>0$, then
  $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$.
• Case 2: If
  $f(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$, then
  $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\cdot \log n)$.
• Case 3: If
  • $f(n)=\mathrm{\Omega }(n^{{\log }_{b}a+ϵ})$ for some constant
    $ϵ>0$, and
  • $a\cdot f(\frac{n}{b})\le c\cdot f(n)$ for some constant
    $c<1$ and all sufficiently large
    $n$, then
    $T(n)=\mathrm{\Theta }(f(n))$.

💡 Compare

$f(n)$ with

$n^{{\log }_{b}a}$

Recursion-Tree for Master Theorem

$T(n)=aT(\frac{n}{b})+f(n)$

複習一下數學

對數：

${\log }_2{2}^3=3,{\log }_b{b}^n=n$

a 的次方數就是展開的層數，和b的次方的成長速度是一樣的，所以如果可以得到b的次方數的話就可以知道a的次方數

可以看到最後

$T(1)$ 時代表 n 就等於他的分母

例如：最後一層是

$b^3$ 好了那 a 的次方就可以這樣表示

$a^{{\log }_b{b}^3}=a^3$

只是我們不知道會展開幾層所以只能用 n 代替，所以這裡才會寫成

$a^{{\log }_{b}n}T(1)$

Recursion-Tree for Master Theorem(2)

回到之前的計算

$T(n)=f(n)+af(\frac{n}{b})+a^{2}f(\frac{n}{b^2})+a^{3}f(\frac{n}{b^3})+...+a^{{\log }_{b}n}T(1)$

$a^{{\log }_{b}n}=n^{{\log }_{n}a\cdot {\log }_{b}n}=n^{{\log }_{b}a}$

$a^{{\log }_{b}n}T(1)=n^{lo{g}_{b}a}T(1)$

為什麼要換成 n 為底呢？因為 n 是我們的 problem size 用 n 為底的話比較好判斷，也就會跟上面三個 case 長得差不多了

複習一下數學(2)

1. $a^{{\log }_{b}n}$ 是怎麼變成
   $n^{{\log }_{n}a\cdot {\log }_{b}n}$的呢？
   1. 需要的知識是對數律
      ${\log }_a(b^n)=n({\log }_{a}b)$ → 真數 n 次方 ，對數 n 倍
   2. 還有
      $3^{{\log }_{3}4}=4,n^{{\log }_{n}a}=a$

   知道這些之後就可以開始推導

   $a^{{\log }_{b}n}=n^{{\log }_n{a}^{lo{g}_{b}n}}$ 再用對數律真數 n 次方 ，對數 n 倍
   $=n^{{\log }_{n}a\cdot {\log }_{b}n}$

2. $a^{{\log }_{b}n}$ 又是怎麼變成
   $n^{{\log }_{b}a}$ 的呢？
   1. 這裡老師就有解釋了使用換底公式
      ${\log }_{a}b=\frac{{\log }_{c}b}{{\log }_{c}a}$

   知道換底公式之後就可以再從上面的結果繼續推導

   $n^{{\log }_{n}a\cdot {\log }_{b}n}=n^{\frac{{\log }_{b}a}{{\log }_{b}n}\cdot {\log }_{b}n}$
   $=n^{{\log }_{b}a}$

Three Case

• $T(n)=aT(\frac{n}{b})+f(n)$
  • $a\ge 1$, the number of subproblems
  • $b>1$, the factor by which the subproblem size decreases
  • $f(n)=$ work to divide/combine subproblems
  $T(n)=f(n)+af(\frac{n}{b})+a^{2}f(\frac{n}{b^2})+a^{3}f(\frac{n}{b^3})+...+a^{{\log }_{b}n}T(1)$

• Compare

  $f(n)$ with
  $n^{{\log }_{b}a}$
  1. Case 1:
     $f(n)$ grows polynomially slower then
     $n^{{\log }_{b}a}$
  2. Case 2:
     $f(n)$ and
     $n^{{\log }_{b}a}$ grow at similar rate
  3. Case 3:
     $f(n)$ grows polynomially faster then
     $n^{{\log }_{b}a}$

Case 1: Total dominated by leaves

ex.

$T(n)=9T(\frac{n}{3})+n,T(1)=1$

💡

$f(n)$ grows polynomially slower then

$n^{{\log }_{b}a}$

$T(n)=(1+\frac{9}{3}+(\frac{9}{3}{)}^2+...+(\frac{9}{3}{)}^{{\log }_{3}n})n$

💡 等比級數公式

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

$=\frac{(\frac{9}{3}{)}^{1+{\log }_{3}n}-1}{3-1}n$

$=\frac{3n}{2}\cdot \frac{9^{{\log }_{3}n}}{3^{{\log }_{3}n}}-\frac{1}{2}n$

$=\frac{3n}{2}\cdot \frac{n^{{\log }_{3}9}}{n}-\frac{1}{2}n$

💡 這裡的

$9^{{\log }_{3}n}$ 是如何變成

$n^{{\log }_{3}9}$ 請參考上面的 複習一下數學(2)

$=\mathrm{\Theta }(n^{{\log }_{3}9})=\mathrm{\Theta }(n^2)$

• Case 1: If
  $f(n)=O(n^{{\log }_{b}a-ϵ})$ for some constant
  $ϵ>0$, then
  $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$.

Case 2: Total cost evenly distributed among levels

ex.

$T(n)=T(\frac{2n}{3})+1,T(1)=1$

$a=1,b=\frac{3}{2}$帶入公式

$n^{{\log }_{b}a}$

💡 這裡需要知道的知識是

${\log }_{b}1$ 是多少，這代表的意義是 b 的幾次方是 1，我們知道 0 次方會是 1

$n^{{\log }_{\frac{3}{2}}1}=n^0$

💡

$f(n)$ and

$n^{{\log }_{b}a}$ grow at similar rates

$T(n)=T(\frac{2n}{3})+1,T(1)=1$

$T(n)=1+1+1+...+1$

$={\log }_{\frac{3}{2}}n+1$

$=\mathrm{\Theta }(\log n)$

• Case 2: If
  $f(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$, then
  $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\cdot \log n)$

Case 3: Total cost dominated by root cost

ex.

$T(n)=3T(\frac{n}{4})+n^5,T(1)=1$

💡

$f(n)$ grows polynomially faster then

$n^{{\log }_{b}a}$

$T(n)=3T(\frac{n}{4})+n^5,T(1)=1$

$T(n)=(1+\frac{3}{4^5}+(\frac{3}{4^5}{)}^2+...+(\frac{3}{4^5}{)}^{{\log }_{4}n})n^5$

$T(n)>n^5$

💡 帶入等比級數相加公式

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

$T(n)\le \frac{1}{1-\frac{3}{4^5}}{n}^5$

💡 其中的

$(\frac{3}{4^5}{)}^{{\log }_{4}n}$應該是太小被省略了

$T(n)=\mathrm{\Theta }(n^5)$

• Case 3: If
  • $f(n)=\mathrm{\Omega }(n^{{\log }_{b}a+ϵ})$ for some constant
    $ϵ>0$, and
  • $a\cdot f(\frac{n}{b})\le c\cdot f(n)$ for some constant
    $c<1$ and all sufficiently large
    $n$, then
    $T(n)=\mathrm{\Theta }(f(n))$.

Example

💡 compare

$f(n)$ with

$n^{{\log }_{b}a}$

• Case 1: If

  $T(n)=9\cdot T(n/3)+n$, then
  $T(n)=\mathrm{\Theta }(n^2)$

  Observe that

  $n=O(n^2)=O(n^{{\log }_{3}9})$

• Case 2: If

  $T(n)=T(2n/3)+1$, then
  $T(n)=\mathrm{\Theta }(\log n)$

  Observe that

  $1=\mathrm{\Theta }(n^0)=\mathrm{\Theta }(n^{{\log }_{3/2}1})$

• Case 3: If

  $T(n)=3\cdot T(n/4)+n^5$, then
  $T(n)=\mathrm{\Theta }(n^5)$
  • $n^5=\mathrm{\Omega }(n^{{\log }_{4}3+ϵ})$ with
    $ϵ=0.00001$
  • $3(\frac{n}{4}{)}^5\le c{n}^5$ with
    $c=0.99999$

Floors and Ceilings

• Master theorem can be extended to recurrences with floors and ceilings
• The proof is in the Ch. 4.6

$T(n)=aT(\lceil \frac{n}{b}\rceil )+f(n)$

$T(n)=aT(\lfloor \frac{n}{b}\rfloor )+f(n)$

Theorem 1

試著用 Master method 套用到之前的 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)=O(n\log n)$

• Case 2

$f(n)=\mathrm{\Theta }(n)=\mathrm{\Theta }(n^1)=\mathrm{\Theta }(n^{{\log }_{2}2})=\mathrm{\Theta }(n^{{\log }_{b}a})$

$T(n)=\mathrm{\Theta }(f(n)\log n)=O(n\log n)$

Theorem 2

試著用 Master method 套用到之前的 Bitonic Champion Problem

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

• Case 1

$f(n)=O(1)=O(n)=O(n^{{\log }_{2}2})=O(n^{{\log }_{b}a})$

$T(n)=\mathrm{\Theta }(n^{{\log }_{2}2})=\mathrm{\Theta }(n)$

Theorem 3

試著用 Master method 套用到之前的改進的 Bitonic Champion Problem

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

$f(n)=\mathrm{\Theta }(1)=\mathrm{\Theta }(n^0)=\mathrm{\Theta }(n^{{\log }_{2}1})=\mathrm{\Theta }(n^{{\log }_{b}a})$

$T(n)=\mathrm{\Theta }(f(n)\log n)=O(\log n)$

---

Andy結論

需要注意的是, 不論大 O 記法還是大 Θ 記法還是大 Ω 記法, 默認討論的都是最壞情況, 並不是像很多高票答主說的那樣, 大 Ω 記法就是討論最好情況了. 它們三個描述的都是同一個估計值 (比如某算法的最壞時間複雜度), 只是 O 描述這個估計值的上限, Ω 描述這個估計值的下限, 而 Θ 描述的是這個估計值的上限和下限相同 (即很確定了, 就在這一階了).