アルゴリズム・プログラミング応用問題
クイックソートにおいて、毎回選択したピボットが常にその時点の部分配列の最小値または最大値になった場合、時間計算量はどうなるか。
A.O(n log n) のまま変わらない
✗ ピボットが常に端値になると分割が偏り、再帰の深さが n になるため O(n log n) は維持できません。
B.O(n²) に悪化する← 正解
✓ 正解です。ピボットが常に最小・最大値になると分割が 0:n-1 に偏り、再帰が n 段になるため最悪 O(n²) になります。
C.O(log n) に改善される
✗ O(log n) はデータ量を半減し続けた場合の探索計算量であり、ソート全体の計算量としてはあり得ません。
D.O(n) に改善される
✗ O(n) 未満のソートは比較ベースでは理論上不可能であり、ピボット偏りで改善されることはありません。