クイックソートの最悪計算量と条件
クイックソートの最悪時の時間計算量と、それが起こる条件の組合せとして正しいものはどれか。
解説を見る
クイックソートはピボットで配列を分割する。ピボットが毎回最小(または最大)になると片側が空、もう片側が n-1 個となり、分割が n 回続くため O(n^2) に劣化する。単純に端をピボットに選ぶと、整列済みデータでこの最悪ケースが起こりやすい。平均は O(n log n)。
誤答の解説
B整列済みは(端ピボットだと)むしろ最悪 O(n^2) を招く条件。O(n log n) は平均時の値。
Cランダムなデータは分割が均等になりやすく、平均 O(n log n) に近い。最悪の条件ではない。
Dピボットが常に中央値なら分割は均等で O(n log n)。O(log n) はそもそも比較ソートの下限を下回り不可能。
ヒント
・最悪ケースは分割が最も偏るとき。片側が空になる状況を考える。