資料結構-時間複雜度

考研相關文章參考資料為 wjungle 大神提供的筆記

漸進式符號

Asymptotic Notations

• 表示時間函數的成長速率 (growth rate) 等級

符號

• $O$
  • $f(n) = O(g(n))$ iff exist two positive constants $c$ and $n_0$ such that $f(n) \leq c*g(n)$, for all $n \geq n_0$
  • 視為理論的 Upper-Bound
• $\Omega$
  • $f(n) = \Omega(g(n))$ iff exist two positive constants $c$ and $n_0$ such that $f(n) \geq c*g(n)$, for all $n \geq n_0$
  • 視為理論的 Lower-Bound
• $\Theta$
  • $f(n) = \Theta(g(n))$ iff exist three positive constants $c_1,c_2$ and $n_0$ such that $c_1*g(n) \leq f(n) \leq c_2*g(n)$, for all $n \geq n_0$
• $o$
  • $f(n) = o(g(n))$ iff for all constants $c>0$, exist $n_0>0$ such that $0 \leq f(n) < c*g(n)$, for all $n \geq n_0$
• $\omega$
  • $f(n) = o(g(n))$ iff for all constants $c>0$, exist $n_0>0$ such that $0 \leq c*g(n) < f(n)$, for all $n \geq n_0$

常見成長速率

• 由小到大
  • 常數、對數:
    • $O(1)$
    • $O(\log^*n) = O(\log\log...\log n)$
    • $O(\log\log n)$
    • $O(\log n) = O(2^{\log\log n})$
    • $O(\log^k n)$
  • 線性、多次方:
    • $O(n) = O(2^{\log n})$
    • $O(n\log n)$、$O(n!)$
    • $O(n^2)$
    • $O(n^k)$
  • 指數:
    • $O(2^n)$
    • $O(k^n)$
  • 階乘、多指數:
    • $O(n!)$
    • $O((n+1)!)$
    • $O(n^n)$
    • $O(n^{2n})$

實用操作:

• $a^{\log_bc} = c^{\log_ba}$

求解遞迴時間函數

展開帶入法

ex: $T(n) = 2T(n-1) + 1,~T(1) = 1$，求 $T(n),~O(n)$?

$T(n) = 2T(n-1) + 1$
$= 2[2T(n - 2) + 1] + 1 = 4T(n - 2) + 3$
$= 4[2T(n - 3) + 1] + 1 = 8T(n - 3) + 7$
$= 16T(n - 4) + 15$
$...$
$= 2^{n - 1}T(1)+2^{n - 1} - 1$
得 $O(2^n)$

• 更多看筆記 P.37

Master Method

• 若 $T(n) = aT(\frac{n}{b})+f(n)$，其中 $a \geq 1,~b > 1$ 之 constants，$f(n)$ 是一個正成長之函數，則可使用此定理求出 $T(n) = \Theta(?)$
• 求出 $n^{\log_ba}$ 並與 $f(n)$ 比較，分為 3 case:
  • case 1:
    • 若 $f(n) = O(n^{\log_ba - \varepsilon}),~\varepsilon > 0$
    • 則 $T(n) = \Theta(n^{\log_ba})$
  • case 2:
    • 若 $f(n) = \Theta(n^{\log_ba})$
    • 則 $T(n) = \Theta(n^{\log_ba} * \log n)$
  • case 3:
    • 若 $f(n) = \Omega(n^{\log_ba + \varepsilon}),~\varepsilon > 0$
    • 且 $af(\frac{n}{b}) \leq cf(n),~where~0 < c < 1$
    • 則 $T(n) = \Theta(n^{\log_ba})$

Extended Master Method

• 若 $T(n) = aT(\frac{n}{b})+f(n)$ 且 $\frac{f(n)}{n^{\log_ba}} = \log^kn,~k \geq 1$
• 則不使用 case 3，而是使用此定理，即 $T(n) = \Theta(n^{\log_ba} * \log^{k + 1}n)$

Recursive Tree

• 分為兩種類型:
  • 每一 level 之 cost 皆相同
    • 則 $T(n) = \Theta(level~cost * \log n)$
  • 每一 level 之 cost 皆不相同，且 $\leq$ level 1 之 cost
    • 則 $T(n) = \Theta(level~1~cost)$

ex:

• $T(n) = T(\frac{n}{5}) + T(\frac{4n}{5}) + n$
  • level 1: $n$
  • level 2: $\frac{n}{5} + \frac{4n}{5} = n$
  • 得 $\Theta(n\log n)$
• $T(n) = T(\frac{n}{4}) + T(\frac{n}{2}) + T(\frac{n}{8}) + n$
  • level 1: $n$
  • level 2: $\frac{n}{4} + \frac{n}{2} + \frac{n}{8} = \frac{7n}{8}$
  • 得 $\Theta(n)$
• $T(n) = T(\frac{n}{5}) + T(\frac{7n}{10}) + n$
  • level 1: $n$
  • level 2: $\frac{n}{5} + \frac{7n}{10} = \frac{9n}{10}$
  • 得 $\Theta(n)$

特徵方程式

ex: $T(n) = T(n - 1) + T(n - 2),~T(0) = 0,~T(1) = 1$

特徵方程式: $x^2 = x + 1 \Rightarrow x^2 - x - 1 = 0$
解出兩根為 $\frac{1 \pm \sqrt{5}}{2}$
$\Rightarrow T(n) = A(\frac{1 + \sqrt{5}}{2}) + B(\frac{1 - \sqrt{5}}{2})$
帶入 $T(0) = 0,~T(1) = 1$ 求 $A,B$
得 $T(n) = \frac{1}{\sqrt{5}}(\frac{1 + \sqrt{5}}{2}) - \frac{1}{\sqrt{5}}(\frac{1 - \sqrt{5}}{2})$

Divide-and-Conquer

• 將一個大問題分割 (Divide) 為幾個獨立的子問題，每個子問題各自求解 (Conquer)，最後合併所有子問題的解成為整個大問題之解
• 與 $T(n) = aT(\frac{n}{b})+f(n)$ 之關係:
  • $n$ 為資料量
  • $a$ 代表子問題數量
  • $\frac{n}{b}$ 代表子問題資料量
    • $T(\frac{n}{b})$ 代表一個子問題之時間
  • $f(n)$ 代表所有切割及合併的成本和