Substution method Example 1 \[ T(n) = T(\sqrt n) + 1 \\ \Rightarrow T(n^{\frac 14}) + 1 + 1 = T(n^{\frac 14}) + 2 \\ \Rightarrow T(n^{\frac 18}) + 3 ...

特殊的函數 \((\log n)^{\log n}\) \[ \Rightarrow n^{\log \log n} \\ 令 \;d \;為一常數\\ \because d\times \log n < \log \log n\times \log n \\ \log \log n \ ...

Approximation ratio A ：「Approximation algorithm」 OPT ：「Optimal algorithm」 對任何輸入 x ∣A(x)∣ ≦ α×∣OPT(x)∣ 稱 A 的「Approximation ratio」為 α （下方討論皆以「最小化問題」 ...

基本概念 目的 將問題依照難度做分類 如何定義 A 問題比 B 問題難？ 如何分類？ 分幾類？ Decision problem 答案只有 Yse/No 的問題 Ex 一個圖中有無「Hamiltonian cycle」？ 每一個最佳化問題 ( Optimization problem ...

Computational geometry The rank of a node rankofnode Dominate and rank \(P_1 = (x_1, y_1)\) dominates \(P_2 = (x_2, y_2)\)：\(x_1 > x_2\) and \( ...

Graph algorithm Depth first search 考慮圖中一點 u color(u)：目前 u 節點的狀態 White 初始值，尚未訪查過 Gray 已被訪查過，但未訪查完其子節點 Black 已經訪查完其子節點 d(u) 發現時間點（Discover ti ...

Segement tree 用來存放紀錄在特定區間內 ( segement, interval ) 的資訊。 Pros 可以動態的更新欲求數組之元素。 數組區間的查詢 區間求和值 區間最大值 區間最小值 區間異或值 ( Exclusive or；XOR ) Cons 無法刪除數值 ...

Dynamic programming 將已計算的結果記錄在表格中的技巧，目的是為了要避免重複計算相同子問題，以「Button up」的方式實踐。 為何要使用這種方法，以費氏數列程式開始討論。 \[ F_n = \left\{\begin{matrix} 0 & , if \; n = ...

Principle of inclusion and exclusion（排容原理） 假設 \(U\) 為與集合，其中 \(|U| = N\)，令 \(a_1, a_2, ..., a_n\) 為 n 個性質，其中這些性質直接定義在 \(U\) 上且 \(N(a_i)\) 表示 \(U\) 中滿足性 ...

File management File open、File close 作業系統對檔案進行任何運作之前，皆必須到磁碟的「Physical directory」找出檔案的配置資訊。 問題 因為檔案數目太龐大，所以搜尋的時間長 磁碟 I/O time(次數)很多，非常耗時 File open ...