Pseudo polynomial time complexity 如果一個演算法的傳統時間複雜度位於多項式時間，而標準時間複雜度不在多項式時間 則我們稱這個演算法位於偽多項式時間，以下探討 多項式時間複雜度是甚麼？ \(O(n^k), k \;is\; constant\) Selection ...

Discrete mathematics - Catalan number 給定兩個生成函數： \(A(x) = \sum_{n = 0}^\infty a_nx^n\) \(B(x) = \sum_{n = 0}^\infty b_nx^n\) 則： \(A(x)\pm B(x) = \s ...

Linear algebra - Vandermonde matrix 法國數學家范德蒙 (Alexandre-Théophile Vandermonde) 是行列式的奠基者之一，他在十八世紀提出行列式專有符號，將行列式應用於解線性方程組，並且對行列式理論進行了開創性的研究 兩百多年後，他的名字因 ...

Minimum edit cost problem 最常使用在檔案的比較以及更新上，若在系統上有多個類似的檔案，可以輕鬆比較差異，而若系統中有若干個不同版本的檔案，亦可以藉由此辦法儲存其差異而非整個檔案，如此一來便可以節省其儲存空間。 問題敘述 給定兩個字串 A[1...n]、B[1...m]，在 ...

The structure of graph [Note] Adjacency list 有一圖 G = (V, E), |V| = n, |E| = e，需要 n 條相鄰串列（vertex[1...n] : pointer）來表達，其中 vertex[i] 代表頂點 i 的相鄰串列，紀錄所有與頂點 ...

Binary search Example n 筆資料作「Binary search」最多比較次數？ \(\lceil \lg (n+1) \rceil\) 200 筆資料：最多 8 次的搜尋 1024 筆資料：最多 11 次的搜尋 Example n 筆資料作「Binary search ...

Binary heap Build heap Top down 依序插入所有資料逐步建立「Heap」 Time complexity for heap insertion：log n Time complexity 若要建立一個 n 筆資料之「Heap」 \(\sum_{i = 1}^n \ ...

AVL tree Height balance binary search tree 性質 \(|H_L - H_R| \leq 1\)，其中 \(H_L、H_R\) 為樹根節點左右子樹之高度 左右子樹亦為「AVL tree」 Example (True or False) 若「Bina ...

Binary tree 節點數量計算 二元樹之第 i 階之節點個數為 \(2^{i-1}\)，i ≧ 1 在高度為 k 的二元樹，全部節點之個數為 \(2^k-1\)，k ≧ 1 對於任一非空二原樹 T ，如果令 Leaf 節點的個數為 \(n_0\)， 而 Degree 為 2 的節點的個數為 ...

Minimal solution 假設 \(A \in F^{m\times n}\)，\(b \in F^{m\times 1}\)，其中 Ax = b 有解，若 s 為 Ax = b 的某一解滿足： 「Ax = b 的其他解 u 使得 \(\left \| s \right \| \leq \l ...