入力が増えた先まで見通すものさし

同じ答えを出す手順でも、調べるデータが増えるにつれて処理回数がどう増えるかは異なります。そこで、入力の大きさをふつう n と置き、必要な処理回数の増え方を比べます。これが計算量を考える中心です。秒数そのものではなく「増え方」に注目するため、特定のコンピュータの速さに強く左右されず、複数のアルゴリズムを共通のものさしで比較できます。

処理時間に関するものは時間計算量、処理の途中で必要になる記憶領域に関するものは空間計算量と呼びます。たとえば、入力を先頭から一度ずつ調べるなら、入力が2倍になったときの処理回数もおおむね2倍です。一方、すべての要素とすべての要素を組み合わせて調べるような二重の繰り返しでは、処理回数が n² に比例して増えることがあります。小さな入力では目立たない違いも、入力が大きくなると実用性を左右します。

O記法は細かな差を捨てて増え方を残す

計算量は、O記法（オーダー記法）で表すことがよくあります。O記法では、入力が十分に大きくなったときの増え方に注目し、定数倍や影響の小さい項を省きます。たとえば、処理回数が 3n+10 の形なら、増え方の中心は n なので O(n) と表します。O(3n) や O(n+10) とは通常書きません。

よく現れる増え方には次のものがあります。

  • O(1)：入力の大きさにかかわらず、処理回数が一定の範囲に収まります。
  • O(log n)：調べる範囲を半分ずつに狭める処理などに現れます。
  • O(n)：入力を一通り調べる処理などに現れます。
  • O(n log n)：効率のよい比較による整列アルゴリズムに現れる代表的な増え方です。
  • O(n²)：二重の繰り返しで、各要素の組を広く調べる処理などに現れます。

O記法は実行時間を直接示す単位ではありません。O(n) だから必ず何秒、という読み方はできず、同じO(n)でも一回の処理内容やプログラムの実装によって実測時間は変わります。

線形探索と二分探索を同じ名簿で比べる

名前順に並んだ名簿から特定の名前を探す場面を考えます。先頭から一人ずつ確認する線形探索では、探す名前が末尾にある場合や見つからない場合、最大で全体を確認します。入力数を n とすると、この増え方は O(n) です。

二分探索では、中央の名前と比較し、目的の名前が前半と後半のどちらにあるかを判断して、候補を半分に絞ります。これを繰り返すため O(log n) です。ただし、二分探索にはデータが探索に使う順序で整列済みであるという前提があります。この前提を整える時間まで含めると、単純に探索部分だけを比較できない場合もあります。探索アルゴリズムの効率は、計算量だけでなく、データの並び方や探索を何回行うかと合わせて判断する必要があります。

また、データを番号で直接参照しやすい配列か、順にたどる必要がある構造かによっても、同じ発想の手順をそのまま実行できるとは限りません。アルゴリズムの前提条件を確かめることも、計算量を正しく読む一部です。

速さと記憶領域は交換条件になる

時間計算量だけが小さければ、常に最良とは限りません。途中の結果を保存して同じ計算を避ければ、処理を速くできる一方で、より多くのメモリが必要になることがあります。反対に、保存を減らして必要な値をその都度計算すれば、使用する記憶領域を抑えられても処理回数が増えることがあります。この関係は、時間と空間のトレードオフと呼ばれます。

再帰を使う手順では、呼び出し途中の状態を保持する領域も無視できません。同じ時間計算量の二つの方法でも、入力が大きくなると、一方だけが多くの作業用メモリを必要とする場合があります。使えるメモリに制限がある機器や、大量のデータを扱う処理では、時間計算量と空間計算量の両方を確認します。

最悪・平均・最良で計算量は変わる

一つのアルゴリズムにも、入力の状態によって処理回数が変わるものがあります。線形探索なら、目的の要素が先頭にあればすぐ終わりますが、末尾にある場合や存在しない場合は多くの比較が必要です。このため、最も処理が多い「最悪の場合」、入力の現れ方を仮定した「平均的な場合」、最も早く終わる「最良の場合」を区別します。

どの計算量を示しているかを明記せずにO記法だけを見ると、比較を誤ることがあります。特に平均の場合は、どのような入力がどの程度現れると仮定したかが結果に関わります。実際の選択では、計算量による見積もりに加えて、想定するデータで実行時間やメモリ使用量を測ることも大切です。理論的な増え方と実測値は、どちらか一方で代用するものではなく、異なる角度から効率を確かめる手段です。

O(log n)で対数の底を書かない理由

数学の対数には底がありますが、計算量の O(log n) では底を省くことが一般的です。底が異なる対数どうしは、定数倍の関係になるからです。たとえば、範囲を半分ずつ絞る処理は底が2の対数で考えられますが、別の一定割合で絞る処理の対数も、O記法で定数倍を省けば同じ O(log n) の増え方として扱えます。

これは、底が何でも実際の処理回数が同じという意味ではありません。O記法が比較しているのは、入力が大きくなったときの増え方の種類です。細かな速さを知りたいときは定数倍や一回ごとの処理も重要ですが、規模が拡大したときの傾向を比べる段階では、O(log n)というまとめ方が役立ちます。