ビッグオー記法（計算量）を例でわかりやすく解説

ビッグオー記法が解決する問題

プログラムの実行時間を秒で測っても、わかるのは特定のマシン・言語・入力での結果だけです。ビッグオー記法は、もっと役に立つ問いに答えます。入力が10倍になったとき、仕事量はどれだけ増えるのか、という問いです。仕事量が10倍になるアルゴリズムと100倍になるアルゴリズムでは、規模が大きくなったときの振る舞いがまったく違います。

厳密には、ある定数 c と n₀ が存在し、n ≥ n₀ のすべての n について f(n) ≤ c · g(n) が成り立つとき、f(n) は O(g(n)) であるといいます。平たく言えば、n が十分大きいとき、定数倍を無視して g が f の増加の上限になっているということです。

• n は入力のサイズです。リストの長さ、文字列の文字数、グラフのノード数などを指します。
• 時間計算量は、基本的なステップ（比較・代入・算術演算）の回数を数えます。
• 空間計算量は、入力そのものを除いて追加で使うメモリ量を数えます。

式を簡略化する方法

ステップ数を n の関数として数え、次の2つのルールを適用します。定数倍を捨て、支配的な項だけを残すことです。

独立した入力が2つあるアルゴリズムでは、両方を残します。長さ n のリストをループしてから長さ m のリストをループすると O(n + m)、ループの中にループがあると O(n · m) です。対数の底はビッグオーでは関係ありません。log₂ n と log₁₀ n は定数倍しか違わないからです。

代表的な計算量のクラス

大まかな目安です。現代のコンピュータでは、単純なループはPythonで毎秒数千万ステップ、コンパイル言語ならそれよりずっと多く実行できます。そのため、O(n log n) なら数百万件でも問題なく、O(n²) は数万件あたりから遅くなり、O(2ⁿ) は40〜60件を超えると現実的ではありません。

Pythonコードから計算量を読み取る

まずループに注目します。入力に対する単一のループは O(n)、同じ入力に対するループの入れ子は O(n²)、残りの範囲を毎回半分にするループは O(log n) です。

def first(items):            # O(1): one step, whatever the size
    return items[0]
def total(items):            # O(n): touches each item once
    s = 0
    for x in items:
        s += x
    return s
def has_duplicate(items):    # O(n^2): compares every pair
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False
def halvings(n):             # O(log n): n is halved each step
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps
print(first([7, 8]), total([1, 2, 3]), has_duplicate([1, 2, 1]), halvings(1024))
# 7 6 True 10

ライブラリ呼び出しにも固有のコストがあります。x in some_list は O(n)、x in some_set は平均 O(1)、list.insert(0, x) は全要素がずれるため O(n)、sorted() は O(n log n) です。O(n) の操作を n 回呼び出すループは、一見ひとつのループに見えても O(n²) になります。

def has_duplicate_fast(items):   # O(n) time, O(n) extra space
    seen = set()
    for x in items:
        if x in seen:            # average O(1) set lookup
            return True
        seen.add(x)
    return False
print(has_duplicate_fast([3, 1, 4, 1, 5]))   # True
print(has_duplicate_fast(list(range(10))))   # False

最良・平均・最悪のケース

同じアルゴリズムでも、同じサイズの入力によって仕事量が変わることがあります。そのため、計算量は3つのケースで示されることがよくあります。

単に「X の計算量」と言うときは、たいてい最悪ケースを指します。ハッシュテーブルやクイックソートでは平均ケースを指すこともあります。償却計算量は4つ目の考え方です。Pythonのリストへの追加は、内部の領域を拡張するときだけ O(n) になりますが、多数回の追加を通して平均すると O(1) です。

ビッグオー、ビッグオメガ、ビッグシータ

厳密には、O は上界にすぎないため、O(n) のアルゴリズムは O(n²) でもあります。日常的にはビッグオーと書きつつ、知っている中で最も厳密な界を意味することが多く、それを正確に表すのが Θ です。

よくある間違い

• 組み込み操作のコストを忘れること。たとえばリストへの in や、スライス items[1:] はコピーが発生し、k 要素のコピーなら O(k) です。
• 再帰呼び出しの数え間違い。n − 1 に対して自分自身を2回呼ぶ関数は O(n) ではなく O(2ⁿ) です。
• 空間を無視すること。サイズ n の新しいリストを作ったり、深さ n の再帰を行ったりすると、O(n) のメモリを消費します。
• O(2n) や O(n + 5) と書くこと。どちらも O(n) に簡略化できます。