ビッグオー記法とは？時間計算量をやさしく解説

ビッグオー記法は、入力サイズが大きくなるときに、アルゴリズムの実行時間やメモリ使用量がどのように増えるかを表します。「問題がずっと大きくなったらどうなるのか？」に答えるための標準的な方法です。

そのため、線形探索は $O(n)$、二分探索は $O(\log n)$ と言われます。目的は、ある1台のマシンでの正確なミリ秒を予測することではありません。増え方のパターンを比べることです。

ビッグオー記法の意味

入力サイズ $n$ に対して、あるアルゴリズムの実行時間を $T(n)$ とすると、

$$T(n) = O(f(n))$$

とは、ある定数 $C > 0$ と $n_0$ が存在して、

$$T(n) \le C f(n) \quad \text{for all } n \ge n_0$$

が成り立つことを意味します。

つまりビッグオー記法は、十分に大きな入力に対する増え方の上界を表しています。

平たく言えば、$n$ が十分大きくなれば、実行時間は $f(n)$ の定数倍より速くは増えない、ということです。

なぜビッグオー記法が役立つのか

ビッグオー記法を使うと、マシンに依存せずにアルゴリズムを比較できます。あるプログラムが別のノートPCでは速く動くことはあっても、増え方の傾向そのものは重要です。

この傾向が特に大事になるのは、入力サイズが大きく変わるときです。$100$ 個のデータでは問題ないアルゴリズムでも、増え方が悪ければ $10^6$ 個では実用的でなくなることがあります。

よくある時間計算量をひと目で確認

• $O(1)$: $n$ が増えても、処理量は一定の範囲に収まります。
• $O(\log n)$: 処理量はゆっくり増えます。問題サイズを何度も小さくしていく場合によく現れます。
• $O(n)$: 処理量は入力サイズにほぼ比例して増えます。
• $O(n \log n)$: 線形より少し大きい増え方で、効率のよいソートでよく見られます。
• $O(n^2)$: 処理量は入力サイズの二乗のように増えます。同じデータに対する二重ループでよく現れます。

これらのラベルが比べているのは増え方であって、正確な速さではありません。たとえ $O(n)$ のアルゴリズムでも、定数倍が大きければ、小さな入力では $O(n^2)$ のアルゴリズムより遅いことがあります。

具体例：なぜ線形探索は $O(n)$ なのか

左から右へリストを順に見て、目的の値を探す場面を考えましょう。最悪の場合、値が存在しないか、いちばん最後にあるので、すべての要素を1回ずつ確認する必要があります。

リストに $n$ 個の要素があるなら、確認回数は最大でも $n$ 回です。だから最悪時の時間計算量は

$$O(n)$$

となります。

ここで大事なのは、リストの大きさが2倍になれば、最悪時の確認回数もだいたい2倍になるということです。ビッグオー記法が捉えているのは、この増え方のパターンです。

ビッグオー記法が省いているもの

ビッグオー記法は、大きな入力での増え方を比べるとき、定数倍や低次の項を意図的に無視します。

たとえば、

$$T(n) = 3n + 2$$

であっても、$T(n)$ はやはり $O(n)$ です。定数の $3$ や余分な $2$ は正確な実行時間には関係しますが、主要な増え方のパターンは変えません。

だからといって、実際には定数がまったく重要でないという意味ではありません。ビッグオー記法が答えているのは、$n$ が大きくなったときにコストがどうスケールするか、というより限定された問いです。

ビッグオー記法でよくある間違い

間違い1：ビッグオーを正確な実行時間だと思う

$O(n)$ は、実行時間がちょうど $n$ ステップという意味ではありません。$n$ が十分大きいとき、増え方が $n$ の定数倍以下に抑えられるという意味です。

間違い2：大きな $n$ という条件を忘れる

形式的な定義では、すべての $n \ge n_0$ で成り立てば十分です。ビッグオー記法が扱うのは漸近的な振る舞いであり、すべての小さな入力ではありません。

間違い3：ビッグオーはいつも典型的な実行時間を表すと思う

アルゴリズムの説明では、ビッグオー記法は最悪時計算量を指すことが多いですが、それは文脈に依存した慣習です。平均時計算量や最良時計算量は別の問いなので、はっきり区別して示すべきです。

間違い4：ビッグオーだけでアルゴリズムを比較する

ビッグオー記法は重要ですが、実際のシステムではメモリ使用量、実装コスト、定数倍も非常に重要になることがあります。

ビッグオー記法をどこで見るか

ビッグオー記法は、計算機科学、離散数学、性能解析でよく使われます。特に、探索、ソート、グラフ探索、動的計画法のアルゴリズムを比較するときに役立ちます。

もっと広く言えば、ある処理が1つの固定サイズでどう動くかではなく、サイズが変わったときにどうスケールするかを知りたい場面で使われます。

似た例を試してみよう

$n \times n$ の格子全体を走査する単純な二重ループを考えてみましょう。内側の処理が何回実行されるかを数えます。全体の処理量が $n^2$ のように増えるなら、同じデータに対する繰り返しループがなぜ $O(n^2)$ になりやすいのかを具体的に理解できます。