基本情報技術者試験「整列アルゴリズム」の問題
クイックソートの平均計算量と、最悪計算量の組合せとして正しいものはどれか。
ア平均O(n)で最悪はO(n log n)である
イ平均も最悪も常にO(n log n)である
ウ平均O(n log n)、最悪はO(n^2)
エ平均O(n^2)で最悪はO(n log n)である
正解
ウ．平均O(n log n)、最悪はO(n^2)
クイックソートは基準値で分割し再帰する。分割が均等に近い平均はO(n log n)だが、毎回片側に偏る最悪はO(n^2)となるため正しい。
?選択肢ごとの解説
ア ×平均O(n)は比較ソートの下限O(n log n)を下回り得ず、最悪O(n log n)も偏り時の劣化を見落とした誤りである。
イ ×平均も最悪もO(n log n)なのはマージソートやヒープソートであり、クイックソートは最悪でO(n^2)に劣化する。
ウ ○クイックソートは基準値で分割し再帰する。分割が均等に近い平均はO(n log n)だが、毎回片側に偏る最悪はO(n^2)となるため正しい。
エ ×平均O(n^2)は実態より悪く見積もった誤りで、最悪をO(n log n)とする点も偏り時の劣化を見落としている。
✎くわしく
クイックソートの計算量は基準値(ピボット)の選び方に依存する。均等分割なら深さlog nで各段nの処理によりO(n log n)、整列済みデータで端を選ぶと深さnになりO(n^2)に劣化する。実用上は高速で内部整列だが不安定である。
✓本番での押さえどころ
試験のコツ
『クイック=平均速いが最悪二乗』『マージ/ヒープ=常にn log n』とセットで対比して覚える。
覚え方
クイックは『当たれば速い博打型』、偏ると二乗に転ぶ、とリスクのイメージで覚える。
よくある誤り
最悪も常にO(n log n)と誤る(マージソートと混同)、または平均をO(n)と過小評価する誤りが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0032