[Algo] 0-1. 複雜度分析 Algorithmic complexity / Big-O / Asymptotic analysis

Big O 的數學定義： $\boxed{O(g(n)) = \lbrace{f(n):存在正常量\space c\space 和\space n_0，使得對所有\space n\ge n_0，有\space 0 \le f(n) \le cg(n)\rbrace}}$
我們常用的 big O 表示法中的 $O$ 其實代表了一個函數的集合，比方說 $O(n^2)$ 代表著一個由 $g(n) = n^2$ 派生出來的一個函數集合；我們說一個演算法的時間複雜度為 $O(n^2)$ ，意思就是描述該演算法的複雜度函數屬於這個函數集合之中。
分析複雜度時，常用的兩個特性：
1. 只保留增長速率最快的項，其它省略
  - $\boxed{O(2n+100) = O(n)}$
  - $\boxed{O(2^{n+1}) = O(2^n)}$
  - $\boxed{O(m+3n+99) = O(m+n)}$
  - $\boxed{O(n^3+999\times n^2+999\times n) = O(n^3)}$
2. Big O 記號表示複雜度的「上限」
  - 換句話說，只要給出的是一個上限，用 Big O 表示法都是正確的。
  - 但在習慣上，我們特別取最緊臨的上限。但若複雜度會跟算法的輸入數據有關，沒辦法提前給出一個特別精確的時間複雜度時，擴大時間複雜度的上限就變得有意義了。
    - 例如湊零錢問題中，金額 amount 的值為 n，coins 列表中的個數為 k，則這棵遞迴樹就是 K 叉樹。而節點的數量與樹的結構有關，而我們無法提前知道樹的結構，所以我們按照最壞情形來處理，高度為 n 的一棵滿 k 叉樹，其節點數為 $\frac{k^n-1}{k-1}$ ，用 big O 表示就是 $O(k^n)$ 。