クイックソート · 計算量ノート
動画ソース: クイックソート · アルゴリズム
アルゴリズムの考え方
アルゴリズム- 基準値を選ぶ -> 分割する -> 両側を再帰する
- インプレースだが安定ではない
計算量表
アルゴリズム| 場合 | 時間 | 空間 |
|---|---|---|
| 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²) になるのを避けるため。



