Algorithm - Ch1 漸近表示法、遞迴與複雜度 Asymptotic Notation, Recurrences and Complexity

Chapter 1  漸近表示法、遞迴與複雜度 Asymptotic Notation, Recurrences and Complexity

1.1  漸進表示法 Asymptotic Notation

時間複雜度是指完成演算法所需的時間，一般為輸入資料量 $n$ 的函數 $T(n)$，以「漸進式表示法」表示。Θ-notation 是最為精確的表示法，但 O-notation 較常使用，因為我們關心的是它的上限。空間複雜度為演算法執行過程中瞬間使用的最大存儲空間，通常也使用漸進式表示法。

• 定義 : 以Upper bound O-notation來舉例
• Exist constant $c > 0, n_0 > 0$  (small o using “for any”)
  Such that $0 ≤ f(n) ≤ cg(n)$ for all $n \leq n_0$ 

• 種類
• O-notation (upper bounds)
• Ω-notation (lower bounds) 
• Θ-notation (tight bounds) 
• ο-notation (strict upper bounds)
• ω-notation (strict lower bounds)
• 關於 Θ -notation 的理論
• For any $f(n)$ and $g(n)$, $f(n) = Θ(g(n))$ iff $f(n) = Ω(g(n))$ and$ f(n) = O(g(n))$ 
• $f(n) + g(n) = Θ(  max\{ f(n), g(n)\}   )$
• 比較複雜度常使用的數學工具
• Log法
• $log( f(n) ) = o( log(g(n)) )$ 可保證 $f(n) = o(g(n))$
• $log( f(n) ) = ω( log(g(n)) )$ 可保證 $f(n) = ω(g(n))$
• 但$log(f(n)) = Θ( log(g(n)) )$ 不可保證 $f(n) = Θ(g(n))$ 
• Limit法
• $\lim_{x \rightarrow\infty}\frac{f(x)}{g(x)}=0$ ，則 $f(n) = o(g(n))$ 
• $\lim_{x \rightarrow\infty}\frac{f(x)}{g(x)}= \infty$， 則為$f(n) = ω(g(n))$
• $\lim_{x \rightarrow\infty}\frac{f(x)}{g(x)}= constant$， 則為$f(n) = Θ(g(n))$
• 通常搭配L'Hôpital's rule來計算結果
• 常用公式  
• Stirling’s rule : 解題非常實用，Stirling’s rule 的 upper bound 和 lower bound要記 !
• $n! \sim \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n. $
• $\lim_{n \rightarrow \infty} {\frac{n!}{\sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n}}} = 1$
• $n! = o(n^n)$
• $n! = ω(2^n)$
• 可以用Stirling’s rule導出 $log(n!) = Θ( nlogn )$，這個結論之後的章節會用來求comparison sort (如quick sort) 的 lower bound。

• 常用的數列總和複雜度
• 等差數列： $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} )$

• 調和數列：$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...\frac{1}{n} = O (logn)$

• 常見的時間複雜度

1.2  遞迴關係 Recurrence Relation

當我們應用遞迴思考求解問題時, 所導出的遞迴關係式可能有二種意義

1. 它表示問題解的遞迴關係，所以求出遞迴關係式的解即得到問題的答案。
2. 它代表問題遞迴解的方式，亦即遞迴關係式，表示遞迴演算法演算步驟的遞迴關係， 所以求出遞迴關係式的解即得知遞迴演算法所須的演算步驟。

以下是一些遞迴關係常用的解法。

• Substitution method
1. Guess the form of the solution. 
2. Verify by induction.
3. Solve for constants. 
• EXAMPLE : $T(n) = 4T(n/2) + n$ 

1. Guess $O(n^3)$. (Prove O and Ω separately.) 
2. Assume that $T(k) ≤ ck^3$ for  $k< n$ .
3. Prove $T(n) ≤cn^3$ by induction. 
• $T(n) = 4T(n/2) + n ≤ 4c(n/2)^3+ n$
          $= (c/2)n^3+ n$
          $= cn^3–((c/2)n^3– n)$ ← desired – residual
          $≤ cn^3$ ← desired
          Whenever $ (c/2)n^3– n ≥ 0 $,
          for example, if $c ≥ 2$ and $n ≥ 1$. 

• A tighter upper bound : Strengthen the inductive hypothesis. A subtract low-order term.   Inductive hypothesis: $T(k) ≤ c_1k^2– c_2k$ for $k < n$.
• $T(n)= 4T(n/2) + n$
         $= 4(c_1(n/2)^2 – c_2(n/2))+ n = c_1n^2 – 2c_2n+ n$
         $= c_1n^2 – c_2n – (c_2n–n)$
         $≤ c_1n^2–c_2n$      if $c_2≥1$.
         Pick $c_1$ big enough to handle the initial conditions.

• Recursion-tree method
1. 依照遞迴定義展開
2. 對每一層的cost加總，得到per-level cost 
3. 加總per-level cost，得到total cost
• Theorem : Given positive constants: c₁, c₂, … c_k, c’, T(n) = T(c₁n) + T(c₂n) + … + T(c_kn) + c’n
• case 1 : c₁ + c₂ + … + c_k < 1,  T(n) = O(n)
• case 2 : c₁ + c₂ + … + c_k = 1,  T(n) = O(nlogn)

• Master Method
• T(n) = aT(n/b) + f(n) ,  where a≥1, b> 1, and f is asymptotically positive. 

1. f (n) = O (n^logba–ε)for some constant ε> 0.
   f (n) grows polynomially slower than n^logba (by n^ε factor)
   Solution: T(n) = Θ(n^logba)
    
2. f (n) = Θ(n^logba lg^kn)for some constant k≥0
   f (n) and n^logba–ε grow at similar rates.
   Solution: T(n) = Θ(n^logba  lg^k+1n).
   T(n) = 3T(n / 3) + n log n , answer: T(n) = Θ(n log²n)
     
3. f (n) grows polynomially faster than n^logba (by n^ε factor)
   and f (n) satisfies regularity condition that af(n/b) ≤ cf(n) for some constant c< 1.
   Solution: T(n) = Θ(f(n)).  

• 例外情況

• Idea of master theorem