[演算法] Ch2 ~ Ch3

本章主要介紹演算法設計與分析的過程，並介紹如 big-O, big-Omega 等表示 running time 的標記。

Intro

沒錯，Ch1 太廢了，懶得介紹 >_<

一般來說，演算法設計與分析大致可以分以下步驟：

1. Formulate Problem：
   • 先定義好問題的 Input, Output
2. Develop Algorithm：
   • 設計演算法
3. Prove Correctness：
   • 證明演算法的正確性與穩定性
     • 正確性：可以找到正確的答案嗎？
     • 穩定性：每個 input、每次執行都能找出正確的結果嗎？
   • 大多數的演算法證明都在這一步
4. Analyze Complexity：
   • 利用 Asymptotic Notation 去分析演算法的時間複雜度
     

Asymptotic notations

Intro

Asymptotic notations 是一個可以簡化演算法 running time 表示的表示法，利用一些常用的函數，來描述 running time 函數的行為。常見的 asymptotic notations 有以下幾種：

種類	意義
\(f = O(g)\)	\(\exists \ c,n_0:f(n) \le cg(n),n \ge n_0\)
\(f = o(g)\)	\(\exists \ c,n_0:f(n) < cg(n),n \ge n_0\)
\(f = \Omega(g)\)	\(\exists \ c,n_0:f(n) \ge cg(n),n \ge n_0\)
\(f = \omega(g)\)	\(\exists \ c,n_0:f(n) > cg(n),n \ge n_0\)
\(f = \Theta(g)\)	\(\exists \ c_1,c_2,n_0: c_1g(n)\le f(n) \le c_2g(n),n \ge n_0\)

Asytotic notations 的優點：把 low-order terms 和係數捨去，大幅簡化演算法複雜度分析

Properties

• Transitivity：
  • \(f = O(g)\) and \(g = O(h)\), then \(f = O(h)\)
  • \(f = \Omega(g)\) and \(g = \Omega(h)\), then \(f = \Omega(h)\)
    依此類推
• Reflexivity：
  • \(f = \Theta(f)\)
  • \(f = O(f)\)
  • \(f = \Omega(f)\)
• Symmetry：
  • \(f = \Theta(g) \Longleftrightarrow g = \Theta(f)\)
• Transpose symmetry：
  • \(f = O(g) \Longleftrightarrow g = \Omega(f)\)
  • \(f = o(g) \Longleftrightarrow g = \omega(f)\)

證明方式

下方是常見的演算法證明方式，可以參考一下：

Stirling's approximation

這個必看，去年期中考有考過，歐姆巴說的

• Stirling formula：
  \((\frac{n}{e})^n < n! < (\frac{n}{e})^n \sqrt{2\pi n}(1 + \frac{1}{11n})\)
• Stirling's approximation：
  \(n! = \sqrt{2 \pi n}(\frac{n}{e})^n(1 + \Theta(\frac{1}{n}))\)

Fibonacci numbers

遞迴解

公式解

• 與黃金比例有關
• 黃金比例 \(\phi\)：
  • \(\phi = \frac{1 + \sqrt{5}}{2}\)
  • \(\hat{\phi } = \frac{1 - \sqrt{5}}{2}\) (\(\phi\) 的共軛根)
  • \(x^2 = x + 1\) 的兩根為 \(\phi\) 與 \(\hat{\phi}\)
• \(F_i = \lfloor \frac{\phi ^i}{\sqrt{5}} + \frac{1}{2} \rfloor\)

常見級數

• \(\sum _{i = 1}^n \frac{1}{i} \simeq \ln n + \gamma,\ \gamma \simeq 0.557\)
• \(\sum_{i = 1}^n i2^i = (n - 1)2^{n+1} + 2\)
• \(\sum_{i = 1}^n \log i = \Theta(n \log n)\)
• \(\sum_{i = 1}^n i^d \log i = \Theta(n^{d+1} \log n)\)