問題 No.4096
要素数が $64$ 個の整列されていないデータ配列に対して、マージソート（分割統治法を用いた整列アルゴリズム）を適用して昇順に整列させる。このとき、最悪計算時間オーダーに基づいて実行される「データの比較回数」の最大値として、最も適切なものを次の選択肢から選べ。なお、マージソートにおいて長さ $n$ の配列を分割してマージする際、最大で $n - 1$ 回の比較が行われるものとする。
【正解の解説】
$384$ 回
トランプの束を半分にちぎって綺麗に並べ替えてから合体させる作業を繰り返すイメージです。全64枚のカードを半分に分ける深さが6段階あり、各段階で最大64回の比較が発生するため、64×6＝384回という計算になります。このように、全体を分割して各個撃破し最後に美しく合体させるアルゴリズムの効率性を体感できる典型的な問題です。
スポンサーリンク
【その他の選択肢の解説】
$256$ 回
初学者が「データの数が多いからとりあえず2乗か何かだろう」と勘違いして、64の2乗や適当な数値を計算してしまいがちな罠です。マージソートは単なる力任せの比較ではなく、データを半分ずつ木構造の形に分解していくため、計算量がO(n log n)のオーダーになるという本質を見落としている場合に選んでしまいます。
$4,096$ 回
すべての要素同士を総当たりで比較するバブルソートなどの単純な整列アルゴリズムで現れる計算量O(n^2)の誤りです。マージソートの効率的な分割統治の仕組みを無視して、ただ要素数を2乗してしまう初心者が引っかかりやすい代表的な引っかけ選択肢となっています。
$448$ 回
計算式やアルゴリズムの仕組みをうろ覚えのまま、適当な数値を当てはめてしまったときに迷い込みやすい誤りの選択肢です。基本情報技術者試験では、このように「一見それっぽく計算したような間違いの数値」が巧妙に紛れ込んでいるため、O(n log n)の公式や樹形図のレベルごとのコストを正しく導出できるかが問われます。