個人覺得考這種 $T(n) = T(n+-*/)$ 啥啥的題目很沒意義，可是一堆教授喜歡考，所以整理這個表，希望大家看到求遞迴複雜度的題目都真的可以5秒內拿分，珍惜生命，請了解原理後使用速解法！
# 這裡假設大家對 Algorithm 聖經本的 Recursive tree method 和 Master theorem 已經熟練
一、強化版 Master Theorem：不要再有人受害了QQ
- $T(n) = 2T(\frac{n}{2}) + n$，可得 $n$ 比上 $n$，複雜度為 $nlogn$
- $T(n) = T(\frac{n}{2}) + 1$，可得 $1$ 比上 $1$，複雜度為 $logn$
CASE 2 : 左邊和右邊一樣次方，右邊多了$log^kn$
- $T(n) = 2T(\frac{n}{2}) + nlogn$ ，可得 $n$ 比上 $nlogn$，複雜度為 $nlog^2n$
- $T(n) = 8T(\frac{n}{2}) + n^3log^2n$ ，可得 $n^3$ 比上 $n^3log^2n$，複雜度為 $n^3log^3n$
- $T(n) = T(\frac{n}{2}) + logn$ ，可得 $1$ 比上 $logn$，複雜度為 $log^2n$
- $T(n) = aT(\frac{n}{b}) + n^{\log_ab }log^kn$ ，可得 $n^{\log_ab }$ 比上 $n^{\log_ab }log^kn$，複雜度為 $n^{\log_ab }log^{k+1}n$
CASE 3 : 左邊和右邊一樣次方，右邊多了$\frac{1}{logn}$
- $T(n) = 2T(\frac{n}{2}) + \frac{n}{logn}$，可得 $n$ 比上 $\frac{n}{logn}$，複雜度為 $nloglogn$
- $T(n) = 8T(\frac{n}{2}) + \frac{n^3}{logn}$，可得 $n^3$ 比上 $\frac{n^3}{logn}$，複雜度為 $n^3loglogn$
- $T(n) = aT(\frac{n}{b}) + \frac{n^{\log_ab}}{logn}$，可得 $n^{\log_ab }$ 比上 $\frac{n^{\log_ab}}{logn}$，複雜度為 $n^{\log_ab }loglogn$
- [注意] $\frac{\log_ab}{log^2n}$或更小就直接捨掉$loglogn$，答案直接為$O(n^{\log_ab })$
二、減法系列 T(n-k)
Example 1 : $T(n) = T(n-1) + \frac{1}{n}$
可以寫成調和數列$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...\frac{1}{n} = O (logn)$
Example 2 : $T(n) = T(n-1) + n^d$
可以寫成$d$次方數列$1^d + 2^d + … + n^d = O ( n^{d+1} )$
Example 3 : $T(n) = T(n-2) + 2logn$
先改寫成特例，$T(n) = T(n-1) + logn$，寫成數列$log1 + log2 + … + logn = log1\times2\times3\times...\times n = logn! = O(nlogn)$(Stirling’s rule)
Example 4 : $T(n) = T(n-a) + T(a) + cn, a \geq 1$
先改寫成特例，$T(n) = T(n-1) + T(1) + cn = T(n-1) + n$，寫成數列 $1+2+3+…+n = O ( n^2 )$
- 常用的數列總和複雜度一覽
- 等差數列： $1+2+3+…+n = O ( n^2 )$
- 等比數列： $r+r^2…+r^n = O ( r^n )$
- 2次方數列：$1^2 + 2^2 + … + n^2 = O ( n^3 )$
- d次方數列：$1^d + 2^d + … + n^d = O ( n^{d+1} )$
三、多個 T 系列
考慮一個多 $T(c_rn)$ 的遞迴 : $T(n) = T(c_1n) + T(c_2n) + … + T(c_kn) + c'n$
CASE 1 : $c_1 + c_2 + … + c_k < 1, T(n) = O(n)$
- $T(n) = T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+n$，複雜度為$O(n)$
- $T(n) \leq T(\frac{n}{5})+T(\frac{7n}{10}+6)+T(\frac{n}{8})+O(n)$，複雜度為$O(n)$
CASE 2 : $c_1 + c_2 + … + c_k = 1, T(n) = O(nlogn)$
- $T(n) = T(\frac{n}{3})+T(\frac{2n}{3})+n$，複雜度為$O(nlogn)$
- $T(n) = T(an) + T((1-a)n) + cn, 0<a<1$，複雜度為$O(nlogn)$
三、根號系列
變數代換$T(n) = T(2^k) = S(k)$, 也就是 $n = 2^k$代入。
CASE 1 : $cT(\sqrt{n})$，T前面是常數
CASE 2 : $\sqrt{n}T(\sqrt{n})$，T前面是根號
發表文章
