數學相關
級數推導
- 等差級數: 反過來相加之後得到2S求S
- 等比級數: 嘗試位移項並減去
- Telescoping 級數: 因式分解
級數和
- 一次方k: \( \sum_{k=1}^{n} k = \frac{n(n + 1)}{2} \)
- 三次方k 為 一次方k級數和平方: \( \sum_{k=1}^{n} k^3 = (\sum_{k=1}^{n} k)^2 \)
- 平方k: \( \sum_{k=1}^{n} k^2 = (\sum_{k=1}^{n} k) (\frac{2n + 1}{3}) = \frac{n(n + 1)(2n + 1)}{6} \)
- x 的 k 次方: \(\sum_{k=0}^{n} x ^ k = \frac{1-x ^ {n+1}}{1 - x}\)
- 上下兩 1 - x ，分子x為 n + 1 次方
- 完全二元樹節點計算可以透過此公式推導
時間複雜度
適用於for迴圈的策略:
- 自外而內: 透過\(\sum\)表達每個迴圈內的計算次數
- 如果是巢狀迴圈，自外而內求解理論上應該由多個\(\sum\)組成求解的運算式
- 求解複雜度的運算式，可以由\(\sum 1\)表達，視情況調整範圍
數學歸納法
- 基底(初始值): 證明n = k, k = 0 or 1時成立
- 歸納用假說: 假設n成立
- 步階: 證明n+1時成立，n+1代入會等於n代入遞迴關係求n+1時成立
Catalan Number
$$b_n = \frac{1}{n + 1} \binom{2n}{n}$$
適用於
- 二元樹變形
- 多邊形三角分割法: n = 頂點 - 2, 頂點 >= 3
- 運算元括號區分的方法(類似二元樹變形)
- 正方棋盤走法
二項係數分解
- 大問題: n取k個 \(\binom{n}{k}\) 大問題拆解
- 大問題中已經選取: \(\binom{n-1}{k-1}\) 當中 k - 1 代表子問題以外已經選取
- 大問題中尚未選取: \(\binom{n-1}{k}\)，而 k 代表在子問題內嘗試選取
綜合以上兩點可得 $$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $$
演算法
演算法的條件(特性)
- 輸入: k個輸入, k >= 0
- 輸出: k個, k > 0
- 明確性: 每個步驟必須清楚定義
- 有限性: 必須在有限的步驟內終結
- 有效性: 每個步驟必須可實現
演算法的正確性檢驗 Correctness of Algorithms
- Initializaion: 證明初始條件成立
- Maintenance: 中間每個步階行為都必須成立
- Termination: 終結時必須正確
其他
- 插入排序法: 穩定的, 最糟\( \Theta (n^2)\), 最佳\( \Theta (n^2)\)
時間複雜度比較
先備知識
- log運算常用公式
- 級數和
分類
- 常數
- 對數
- 多對數
- 多項式
- 線性
- 平方
- 立方
- 指數
- 階乘
常見概念
- \(log(n!) = n\, log(n)\)1
- \(n! = n ^ n\) 同一層級， 可以透過\(log(n!) = n \, log(n) = log(n^n)\) 並且取反對數理解
- 與指數對數相關的，可以取對數或指數並且與接近的對數比較大小， 比較時其他值取對數，並且把相同的地方(如相乘相同的對數)透過同除等方法去除， 進行比較
- 透過時間反過來推測時間複雜度時，可以觀察不同n時的倍率關係。
Asymptotic 表示法
比較大小，注意其等號代表屬於(∈)何種集合， 大小希臘字母比較的時大寫可以相等，小寫則不包含相等的情況。
- 上界: \( O \), \( o \)
- 介於上下界: \( \Theta \)
- 下界: \( \Omega \), \( \omega \)
Asymptotic 表示法會取\(n_0\)與正常數\(c\)，在這個值之後所有的\(n\)代入 \(c \, g(n)\)後，函數\(f(n)\)為正常數並且滿足特定的條件(看取\(O,o, \omega, \Omega \)等等)。
相加
兩個 Asymptotic 表示法相加時，如 $$ \Omega (n) + O(n)$$ 這代表\(f1(n) \in \Omega (n), f2(n) \in O(n) \)，並且\(f1(n) + f2(n)\) 總是大於或相同屬於\(\Omega (n)\)的函數，因此可視為\(\Omega (n)\)。2
概念釐清
- positive constant(正常數): \( k\geq 0 \)
- positive integers(正整數): \( k > 0 , k \in \mathbb{Z}\)
演算法設計
遞迴式的解決方法
- master
- 迭代法：對遞迴式迭代幾次之後，觀察數列變化規律導出時間複雜度。
- 多次展開遞迴式
- 透過代數表達展開式總和
- 總和求解
動態規劃
- 分解大問題成子問題
- 列表法
可以保證最佳解
複雜度
皆為 Theta
- Assembly Line: n
- Rod Cutting: n^2
- Matrix-Chain Multiplication = Optimal BST: n^3
- LCS = Edit Distance: m * n
Assembly Line
切鋼條
從最少開始，並且考慮不同位置切割
-
算法
- r[目前長度]: 當前利潤 = max{切割利潤 + 先前最大利益}
- s[目前長度] = 最大利潤切割大小
-
複雜度: Theta(n^2)
輸出
- 給予長度
- 找出該長度的最大利潤切割大小
- 扣除大小後，重複執行直到相等
Matrix-Chain Multiplication
複雜度: Theta(n^3)
- 宣告矩陣 m (最小值) 與 s (最佳解)
- m 對角全填 0
- 由對角線往角做計算，往上時分割一次在不同位置取最小得出解
- 將分割位置存到 s (最佳解) 中
輸出
S 矩陣的 i, j 項代表分割位置， 並且透過該分割位置繼續往下分割到相同為止。
LCS
與 Edit Distance 類似，時間複雜度也類似
填寫矩陣的 Case
- Default 往上指
- 兩字元相等往左上，並且數值+1
- 字元不同指向最大
LCS的解可以理解在兩個維度走訪，對角代表Match，非斜線代表略過。
複雜度: Theta(m*n)，兩個字串的長度 m, n
習題: leetcode longest common subsequence solve
LIS
最長遞增子序列
待補
Knapsack
- 0-1 背包問題可以透過動態規劃進行解題
- dp 複雜度 Theta(nW)
- 動態規劃範例: knapsack.py
貪婪法
- 選取當下最優解
- 不保證最佳解
可貪婪的
- Huffman code
- Activity Selection
- Fractional Knapsack
Making Change
貪婪法不見得可以獲得最佳解
- 題解: leetcode-322
Huffman Codes
最佳解
- 求出機率
- 透過最小優先佇列建樹
- 將建立好的節點放入佇列繼續建樹
Theta(n lg n)
Activity Selection
嘗試找出最大相容子級，意指時間不交疊
- 最佳解
- 動態規劃 Theta(n^3)
- 貪婪法 Theta(n) or Theta(n lg n)
Knapsack
每次嘗試取高 V/W
-
Fractional knapsack 保證最佳，如果不是的話不保證
-
貪婪法無法解決 0-1 背包問題
-
貪婪法 Theta(n lg n)
償還分析
計算平均的 worst case
Potential
Accounting
Aggregate
Fibonacci Heap
透過 Doubly Linked List 串接 roots
- Insert
- Extract-Min
- Union
- Decreasing-Key
- Deletion
時間複雜度
- Theta(1): Insert, Decreasing-Key, Union
- O(lg n): Delete, Extract-Min
Struct
- Parent, child, left, right
- degree
- Child Mark
Union
- 將兩個 Heap 相串
- 由於兩個 Heap 都有 Min 值，更新 Min 值
Extract-Min
Solid Fibonacci Heap 當中的 Tree 分支度(Degree)都不同
- 將最小樹根移除後，把子節點串在原位置上
- Consolidate() 操作用來將 Heap 轉成 Solid Heap
Decreasing-Key
第二次切的非根節點移動到連結串列
Algorithm Analysis Algorithm