計算量

速さを桁で比べる

ここまでで、同じ「探す」「並べる」でも方法によって手間が大きく違うことを見てきました。その違いを比べるためのものさしが計算量です。実際の秒数はコンピュータの性能で変わってしまうので、データの個数 n が増えたときに手間がどう増えるか、という増え方だけを見ます。この表し方を O記法（オーダー記法）と呼びます。

主な形

よく出るのは次の5つです。

O(1) は、データが何個あっても手間が変わらない形です。配列の3番目を取り出す操作や、ハッシュで位置を計算して1発で取りに行く操作がこれにあたります。

O(log n) は、1回で候補が半分になる形です。二分探索がこれです。n が1000倍になっても手間は10回ぶんしか増えません。

O(n) は、n に比例する形です。線形探索や、配列を1周して合計を求める処理がこれです。

O(n log n) は、分割統治の整列です。マージソートやクイックソートの平均がこれです。

O(n の2乗) は、二重ループでデータ全体を何度も見る形です。交換法、選択法、挿入法がこれです。

速い順に並べると O(1)、O(log n)、O(n)、O(n log n)、O(n の2乗) となります。この並びは問題文の選択肢そのものとして出てくるので、順番を言えるようにしてください。

定数と小さい項は捨てます

O記法では、係数と、増え方の小さい項を落とします。処理の回数が 3n + 100 回でも O(n) と書きますし、n の2乗 + 10n でも O(n の2乗) です。

落としてよい理由は、n が十分に大きいときに全体を決めるのはいちばん増え方の速い項だからです。n が 1000 のとき n の2乗は100万で、10n の1万は誤差の範囲になります。逆に言えば、n が小さいうちは O(n の2乗) のほうが速いこともあります。要素数が数十個なら挿入法のほうがクイックソートより速い、という現実もここから来ています。

コードから読み取る手順

擬似言語を見て計算量を答えるときは、ループの入れ子の深さを数えるのが基本です。データ全体を1周する for が1つならその中は O(n)、その中にもう1つ全体を回る for があれば O(n の2乗) です。

ただし内側のループの回数が n に比例しない場合は別です。交換法の内側の for は 1 回目が n - 1 回、2 回目が n - 2 回と減っていきますが、合計すると n(n - 1) ÷ 2 回なので、係数の 2 分の 1 を落として O(n の2乗) になります。また、範囲が毎回半分になるループは、回数が n ではなく log n です。「何回で終わるか」を1つずつ確かめる癖をつけてください。

記憶領域にも計算量があります

計算量には時間だけでなく領域のものもあります。マージソートが合流用の別領域を必要とするのに対し、交換法は配列の中だけで済みます。時間は速いが領域を食う、という取引が発生している点は、比較の問題でよく問われます。