符號與說明

時間複雜度

對於一個演算法，考慮所有大小為 \(n\) 的輸入，若它的最差執行時間為 \(T(n)\)，那麼我們便說該演算法的最差時間複雜度為 \(T(n)\)。 通常我們會關心在 \(n\) 趨近無窮大的時候，這個函數的成長幅度為何。因此我們通常關心的是 \(T(n)\) 的漸進時間複雜度（Asymptotic Time Complexity）。 常見的漸進符號如下：

• Big-\(O\)：我們說一個演算法的執行時間為 \(O(f(n))\)，若存在一個常數 \(c > 0\)、以及一個 \(n_0\in\mathbb{N}\)，使得對所有的 \(n > n_0\) 皆有 \(T(n) \le cf(n)\)。
• Big-\(\Omega\)：我們說一個演算法的執行時間為 \(\Omega(f(n))\)，若存在一個常數 \(c > 0\)、以及一個 \(n_0\in\mathbb{N}\)，使得對所有的 \(n > n_0\) 皆有 \(T(n) \ge cf(n)\)。
• Big-\(\Theta\)：我們說一個演算法的執行時間為 \(\Theta(f(n))\)，若存在兩個常數 \(c_1, c_2 > 0\)、以及一個 \(n_0\in\mathbb{N}\)，使得對於任意的 \(n > n_0\) 都有 \(c_1f(n) \le T(n) \le c_2f(n)\)。

計算模型

最簡單的說法，是指計算模型嚴謹地定義了「\(O(1)\) 的時間可以做什麼」、以及「資料的存取方式」。

Misc

• 身為一個資訊系理論宅，我們使用的對數函數 \(\log\)，在沒有額外說明的情形下，一律以 2 為底。