時間計算量

時間計算量は、アルゴリズムが完了するまでに行う基本演算回数を入力サイズnの関数として数え、実行時間の増加傾向を評価したものです。

■ 試験で押さえるポイント

• 実際の秒数ではなく比較、代入、加算等の支配的な基本操作を数えるため、機種や言語が異なっても拡張性を比較できます。

• 最悪時間、平均時間、最良時間を区別します。入力分布や要求保証によって、どの時間計算量を採用するかが変わります。

• 二分探索は探索範囲を毎回半分にするため最大比較回数が約$\log_2n$で$O(\log n)$、線形探索は最大n回で$O(n)$です。

• 処理時間を減らすため索引や表を保持すると空間計算量が増える場合があり、時間と記憶量のトレードオフを評価します。

■ 選択肢での判断ポイント

ループ回数や再帰式から基本演算回数を求め、支配項をオーダーへ直します。実測時間と時間計算量を混同しません。

例: 要素数1,024の整列済み配列を二分探索すると、$1{,}024=2^{10}$なので、範囲を10回半減すれば候補は1要素となり、比較回数は約10回です。