快速排序 · 複雜度筆記
來源: 快速排序 · 演算法課
演算法思路
演算法課- 選擇基準值 -> 分割 -> 遞迴處理兩邊
- 原地排序,但不穩定
複雜度表
演算法課| 情況 | 時間 | 空間 |
|---|---|---|
| Best | Θ(n log n) | O(log n) |
| Average | Θ(n log n) | O(log n) |
| Worst | Θ(n²) | O(n) |
遞迴式
演算法課- T(n) = 2·T(n/2) + Θ(n) ⇒ Θ(n log n)
面試卡片
演算法課- Q: 為什麼用隨機基準值?答:避免在有序或對抗輸入上退化到 Θ(n²)。



