常見時間複雜度

簡介

在演算法中，我們會用 Big-O 來估計一個演算法的時間複雜度，這裡我們列出一些常見的時間複雜度：

• $O(1)$ : 常數時間，不論輸入的大小，都可以在一個固定的時間內完成，基本輸出 章節的例子就是這個時間複雜度。
• $O(\log n)$ : 在時間複雜度的領域的 log 通常是指以 2 為底的 log，把一個數字轉成二進位時會用到這個時間複雜度。
• $O(n)$ : 線性時間，時間和輸入的大小成正比。
• $O(n \log n)$ : 這個時間複雜度通常出現在一些排序演算法上，我們之前介紹的 簡易排序 就是這個時間複雜度。
• $O(n^2)$ : 平方時間，時間和輸入的平方成正比，如果你用兩個迴圈去遍歷一個二維陣列，那麼這個時間複雜度就是 $O(n^2)$。

對於不同的複雜度，在數據變大會有不同的增長趨勢，如下圖。

時間複雜度與執行時間

仔細觀察上面的圖，我們可以發現，如果複雜度變成指數型會變得增加很快，舉個例子

以大部分的 Judge 系統來說，通常建議以一秒可以跑 $10^9$ 的簡易計算來估計，那對於一個題目只有 $n$ 的輸入，我們有 $O(n), O(n^2), O(n^n)$ 三種演算法可以解決，我們假設三個方法剛好是分別需要 $n, n^2, n^n$ 個簡易計算，且不考慮一些硬體上的問題，對於不同的 $n$，我們討論它需要跑多久，下面是討論的結果（單位為秒）。

n	$O(n)$	$O(n^2)$	$O(n^n)$
1	$10^{-9}$	$10^{-9}$	$10^{-9}$
2	$5 \cdot 10^{-8}$	$2.5 \cdot 10^{-8}$	$2.5 \cdot 10^{-8}$
5	$2 \cdot 10^{-8}$	$4 \cdot 10^{-7}$	$3.1 \times 10^{-6}$
10	$10^{-8}$	$10^{-7}$	$10$
100	$10^{-7}$	$10^{-9}$	$10^{191}$
1000	$10^{-6}$	$10^{-9}$	$10^{2991}$
$10^5$	$10^{-4}$	$10$	--
$10^6$	$10^{-3}$	$1000$	--

可以看到 $O(n^n)$ 的演算法，在 $n = 100$ 時已經需要很大量的時間了，而 $O(n^2)$ 在 $n = 10^6$ 也需要不少時間，$O(n)$ 的則都可以在 1 秒內完成。