KAIDLOG

note




        這個方法非常有用，在各種研究所題型都管用，除非他有要求，一定要用 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)$$

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

為 case 3

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

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