計算量（オーダー）の見積もり方と、オーダー記法

第2回で説明した通り、アルゴリズムによっては計算量が非常に大きくなり、実用的なプログラムではなくなってしまう場合もあります。そうした事態を回避するため、プログラムを書く際には「どれくらいの実行時間が必要か」を考えることが大切です。しかしながら、演算の種類によって 1 回の計算にかかる時間が異なることもあるため、正確な実行時間を見積もるのは困難です。そこで今回は、大まかな計算量を見積もる方法と、それを表記するための「オーダー記法」について記します。

第2回「全探索とは」はこちらから

計算量とオーダー記法

計算量は、アルゴリズムの効率の良し悪しを測る重要な指標です^※。通常、オーダー記法を使って O(N)、O(N²) などといった形式で表します。ここで N は入力のサイズや、入力で扱う値などを指します。具体例は次の通りです。

• 計算回数が N² 回のアルゴリズムは、計算量 O(N²)
• 計算回数が 2N+M 回のアルゴリズムは、計算量 O(N+M)
• 計算回数が 2^N+N 回のアルゴリズムは、計算量 O(2^N)

オーダー記法は大まかな計算回数を表すことを目的としているため、2 つ目の例では「2N」の係数 2 の部分が省略されて O(N+M) になっていることに注意してください。また、3 つ目の例については、N の値が大きいとき N は 2^N に比べて無視できるほど小さいので、オーダー記法の中身には 2^N のみが残っています。

^{※厳密には、計算量には計算回数を表す「時間計算量」とメモリ使用量を表す「空間計算量」の 2 種類がありますが、本連載では時間計算量のみを考えるものとします。}

計算量の例 (1)： 1 から N まで全部足す

上の説明だけではよく分からないと思うので、いくつか具体例を挙げます。まずは 1 から N までの総和を計算する以下のプログラムについて、計算量を考えてみましょう。

N = int(input())           # N を入力
Answer = 0                 # 答えの値
for i in range(1, N + 1):
    Answer += i
print(Answer)              # 答えを出力

このプログラムは足し算を N 回行っているので、計算量は O(N) です。入力・出力・変数の初期化などを含めると計算回数が N+3 回になりますが、N が大きいとき「+3」の部分は無視できるほど小さいので、計算量は変わりません。