クイックソートが最悪計算量 O(n^2) を引き起こす典型的なピボットの選び方はどれか？ 2026.01.31 クイックソートが最悪計算量 O(n^2) を引き起こす典型的なピボットの選び方はどれか？ ランダムにピボットを選ぶ 中央値近似（例: median-of-three）を使う 常に配列の中央の要素を選ぶ 既に整列済みの入力に対して常に先頭要素をピボットに選ぶ クイックソートはピボットによって分割が偏ると深さが増し最悪 O(n^2) になります。特に既に昇順や降順に整列された入力に対して常に先頭要素をピボットに選ぶ戦略は、各分割で一方にほぼ全要素が偏り、再帰が深くなって最悪ケースを引き起こします。ランダム選択や median-of-three はこの偏りを緩和します。 クイズタグ: アルゴン関連記事 アルゴンクイズ！【問題 全10問・答え付き】 | 2026年01月版
