簡介#
在演算法中，我們會用 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 秒內完成。
