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

第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」の部分は無視できるほど小さいので、計算量は変わりません。

計算量の例 (2)： 2N+3 を出力する

次の例として、整数 N を入力して 2N+3 を出力する以下のプログラムを考えましょう。入力・出力を各 1 回の計算とすると、プログラム全体の計算回数は入力の大きさ N によらず 2 回となります。

N = int(input())  # N を入力
print(2 * N + 3)  # 答えを出力

そこで計算量を O(2) と表しても良いですが、大まかな計算回数を考える際には 2 回も 1 回もあまり変わらないので、慣例的には O(1) と表します。また、このような計算回数になるアルゴリズムを「定数時間である」といいます。

計算量の例 (3)： 配列のソート

アルゴリズムを扱う場面では、計算回数が log₂ N 回になるなど、対数関数が出てくることがあります。この場合、オーダー記法では慣例的に O(log N) のように対数の底を省略した形で表します。

例えば、長さ N の配列を小さい順に並び替える sorted 関数は、計算量が O(N log N) です。

# 入力
N = int(input())
A = list(map(int, input().split()))

# 配列のソート
B = sorted(A)

計算量の例 (4) ： 転倒数の計算

次の例として、長さ N の配列 A = [A₀, A₁, ..., A_N-1] を入力として受け取り、i < j かつ A_i > A_j であるような組 (i, j) の個数（「転倒数」といいます）を求める以下のプログラムを考えましょう。

# 整数 N と配列 A を入力
N = int(input())
A = list(map(int, input().split()))

# 答えを全探索によって求める
Answer = 0  
for i in range(N):
    for j in range(i + 1, N): # j = i+1, i+2, ..., N についてループ
        if A[i] > A[j]:
            Answer += 1

# 答えを出力            
print(Answer)

このプログラムが A_i > A_j かどうかの判定を行う回数は、次の表のようになります。これらを全て足すと N²/2-N/2 回となりますが、オーダーを求める際には「大まかな値」しか考えなくても良いので、計算量は O(N²) と表されます。

i=0 のとき	i=1 のとき	i=2 のとき	......	i=N-1 のとき
N-1 回	N-2 回	N-3 回	......	0 回

計算量の比較

最後に、入力データの大きさ N と計算回数の目安の関係を以下の表に示します。一般の家庭用コンピュータの計算速度は 1 秒当たり 10⁸ ～ 10⁹ 回程度ですので、10⁹ を超える場合は「一瞬では計算が終わらない」と思って問題ないでしょう。特に、10²⁵ を超える場合は、2021 年 6 月時点で世界最速の処理能力を持つ「スパコン富岳」を使っても現実的な時間内には計算が終わりません。

• 

なお、例えば計算量が同じ O(N) でも、計算回数が N 回だったり 3N 回だったりする場合があります。しかし、実用上は数倍しか差がつかないことが多いため、極限までプログラムを高速化するような場面でなければ、オーダーの中身（N, N² など）から大まかな計算回数や実行時間を推定することも可能です。

今回はアルゴリズムを考える上での基本となる計算量の見積もり方と、それを表記するためのオーダー記法について説明しました。次回からはいよいよ本格的なアルゴリズムの解説に入っていきます。ご期待ください。