アルゴリズムとプログラミングアルゴリズム実践

ヒープソートの計算量として正しいものはどれか。

ア.最良・平均・最悪ともにO(n^2)

イ.平均O(n log n)だが最悪O(n^2)になる場合がある

ウ.最良・平均・最悪ともにO(n log n)が保証される正解

エ.O(n)で動作する線形時間アルゴリズムである

解説

ヒープソートは「絶対に遅刻しない几帳面な人」みたいなもの。クイックソートという天才は普段は速いけど最悪の日（最悪ケース）はO(n^2)まで落ちる。でもヒープソートは「最悪の状況でも必ずO(n log n)を守る」という約束を絶対破らない。安定感では随一！

なぜウが正解か

ヒープソートの計算量分析：①ヒープ構築フェーズ：O(n)②n回のヒープ操作（最大値取り出し+ヒープ再構成）：各O(log n)×n回 = O(n log n)③合計：O(n) + O(n log n) = O(n log n)。最良・平均・最悪のすべてのケースでO(n log n)が保証される。これがヒープソートの最大の強み（クイックソートは最悪O(n^2)）。

なぜアは間違いか

O(n^2)はバブルソートや選択ソートの計算量。ヒープソートは完全2分木(ヒープ)を利用することでO(n log n)を実現している。

なぜイは間違いか

最悪O(n^2)になるのはクイックソートの弱点。ヒープソートの最大の利点はまさに最悪ケースでもO(n log n)を保証する点にある。

なぜエは間違いか

O(n)の線形時間ソートは比較ソートでは理論的に不可能（下限Ω(n log n)）。基数ソートやバケットソートなど比較を使わないソートでO(n)が可能だが、ヒープソートは比較ソート。

出典: AI生成問題（学習用）

← 前の問題

シェルソートの特徴として最も正しいものはどれか。

次の問題 →

基数ソートの動作原理として最も正しいものはどれか。

アルゴリズムとプログラミングの問題を解くこの分野の問題一覧を見る