為甚麼先做複雜度分析
漸進分析回答的是「輸入變大時成本如何放大」。它比常數項調整更能決 定演算法是否可擴展。
定義
Big-O 上界
表示存在常數 與 ，使得對所有 都有 。
邊讀邊試
在同一 n 比較漸進增長
在同一 n 下比較多種級別，讓相對增長差距具體化。
| Class | Value at n=16 |
|---|---|
| O(1) | 1.00 |
| O(log n) | 4.00 |
| O(n) | 16.00 |
| O(n log n) | 64.00 |
| O(n^2) | 256.00 |
常見級別
O(1)：直接存取、已知節點的 pointer 重連O(log n)：對半縮減搜尋O(n)：線性掃描O(n log n)：分治加線性合併- ：雙層線性迴圈
快速檢查
快速檢查
兩層各跑 n 次的迴圈（內部 O(1)）是甚麼複雜度？
直接乘法則。
解答