Master Theorem note

note

Mastering Theorem for Dividing Function

這個方法非常有用，在各種研究所題型都管用，除非他有要求，一定要用 Upper & lower bound 解，不然都可以解。

時間複雜度計算

$T(n) = aT(n/b) + θ\left(n^k log^pn \right)$

$\qquad Satisfy \quad ∀ a,b ∈ a \geq 1 ∧ b >1$

$case 1 : log_ba > k$

$\quad then$

$θ(n^{log_ba} )$

$case 2: log_ba = k$

$\quad if \quad p > -1 \quad then$

$θ(n^klog^{p+1}n)$

$\quad if \quad p = -1 \quad then$

$θ(n^kloglogn)$

$\quad if \quad p < -1 \quad then$

$θ(n^k)$

$case 3: log_ba < k$

$\quad if \quad p \geq 0 \quad then$

$θ(n^klog^{p}n)$

$\quad if \quad p < 0 \quad then$

$O(n^k)$

這邊給一個例子:

有一個演算法的時間複雜度是 T(n) = 3T(n / 7) + n log n

$\quad log_ba = log_73 \quad < 1 = k$

為 case 3

$考慮 \quad p = 1 \geq 0$

所以他的時間複雜度就是

$\quad T(n) = θ (n log n)$

Pages

KAIDLOG

NOTE 1 Fizz 操作心得