在有限的步驟內，解決特定問題的方法
【 e.g. 偽幣問題 】
Q：在n個真幣中，藏入1個假幣，如何找出他？
| 循序比較法 | $O(n)$ | 一個一個去比較 |
|---|---|---|
| 淘汰與搜尋法 | ||
| prune and search | $O(log_2(n))$ | 一半一半去篩掉 |
分成 Best Case B(n)、Average Case A(n)、Worst Case W(n)
| $L(n)$ | 某問題 最少 需要的運算量 | 當 $L(n)$ = $W(n)$ 代表是最佳演算法 |
|---|
e.g. 循序搜尋
| $Ω(n)$ | 成長速度至少跟 g(n) 一樣快 | 下界 |
|---|---|---|
| $Θ(n)$ | 成長速度 = g(n) | 精準界限 |
| $O(n)$ | 成長速度不快於 g(n) | 上界 |
