GLOSSARY.md

符號與說明

時間複雜度

對於一個演算法，考慮所有大小為 $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 為底。