レッスン
理論 — 計算量オーダー(Big-O)エクスプローラー
Big-Oは時間の測定ではなく、増加速度の上限を示すものです。あるアルゴリズムが O(N²) であると言うことは、ある入力サイズを超えると、その処理量が N² の定数倍以下に収まることを主張しているに過ぎません — そこには実行秒数に関する言及はなく、小さな入力についての主張も一切含まれていません。
各記号の意味
N- 入力サイズ — アルゴリズムに渡される要素の数。上記で設定した2から1,000,000までの数値です。
f(N)- そのサイズで実際に実行される計算量 — 秒数ではなく抽象的な操作回数でカウントされます。
c- 表記上、隠すことが許されている定数倍の係数。ここでの主張は
f(N) ≤ c·g(N)であり、c は 2 かもしれませんし 2000 かもしれません。そしてそれこそが、Big-Oが意図的に切り捨てる情報です。 n₀- 上限が成立しなければならない境界となるサイズ。
n₀未満では、各計算量クラスの大小関係はどのようになっていてもかまいません。上記の5つの数値が小さな N で密集しているのはそのためです。
公式の導き方
- 厳密にする必要のある主張から始めましょう。すなわち、計算量
f(N)は最終的に、ある基準関数g(N)よりも速く増加することはない、という主張です。 - “より速く増加することはない”という表現は、定数倍の差を許容する必要があります。なぜなら、内部ループを最適化しても変わるのは定数係数であり、グラフの形状ではないからです。したがって、係数を許容します：
f(N) ≤ c·g(N)。 - また、“最終的に”という条件は、何が起こるかわからない小さな入力を除外するためのものです。不等式が成り立つことを
N ≥ n₀以降でのみ求めます。これらを合わせると：f(N) = O(g(N))とは、すべてのN ≥ n₀に対してf(N) ≤ c·g(N)を満たすような、あるc > 0とあるn₀が存在することを意味します。
表示の読み方
5つの行は、すべての定数を 1 に設定した状態で、1つの入力サイズを5つの増加クラスに適用した結果を示しています — したがってこれらは実行時間ではなく、操作回数です。デフォルトの N = 100 では、それらの値は 1、7、100、664、10,000 となります。対数の底は 2 であり（log₂ 100 ≈ 6.64）、そのため O(log N) は 7 を示し、O(N log N) は 700 ではなく 664 を示します。
- 前提
- すべての操作コストが同等であり、カウントが実測値ではなく厳密な計算値であると仮定しています。これによって比較が明快になる一方で、同時にモデルが抽象的なものとなります — メモリアクセスパターン、キャッシュの挙動、ディスク処理などはすべてこのモデルの対象外であり、実際のハードウェア上では、それらが2つのアルゴリズムのどちらが優れているかを決める決定打となることが多々あります。
- 成り立たない場合
- この上限は
n₀未満では何も保証しません。それは実際に確かめることができます。N = 2に設定すると、5つのクラスは1、1、2、2、4となり — ほとんど区別がつきません。記法が保証する大小関係は N が十分に大きくなって初めて現れます。だからこそ、定数倍が小さなO(N²)の手法が、実際に向き合うあらゆる入力サイズにおいてO(N log N)の手法を上回るということが起こり得るのです。
全プロセスの詳細解説
-
N log N と N ² の間に隔たりが生じる箇所 5 ステップ
N = 100 のとき、パネルには N log N に対して 664、N² に対して 10 000 と表示される。それはわずか15倍の差に過ぎず、計算複雑性クラスがもたらすとされる決定的な格差とは程遠い。その格差が実際にどこで開くのかを突き止めよ。
-
まず2つの数値から始める。log₂ 100 は 6.6439 であるため、N log₂ N は 664 となり、N² は 10 000 となる。
-
それらの比率は定数ではなく、それこそが計算複雑性クラスの真髄である。割り算を行うと N が1回約分され、N/log N が残る — これは、成長速度こそ遅いものの、限りなく増大する量である。
-
N = 100 において、その値は 15.1 である。これは実在する差ではあるが、目覚ましいものではない。15倍の高速化はより優れた定数係数によってもたらされ得る程度のものであり、小さな入力に対するベンチマークが人を誤解させるのはまさにこれが理由である。
-
ここで100万を入力してみる。対数は 6.6 から 19.9 へと3倍にしか増えていないのに対し、N は1万倍に成長している。現在の比率は 50 172 である。
-
そして、この傾向が逆転することはない。N/log N の導関数は、N が e を超えるすべての範囲において正となるため、2次アルゴリズムが追いつくような入力サイズは存在しない。
解答
ツールには N = 100 において 664 対 10 000 と表示される。覚えておくべき数値はもう一方である。100万において、これら同じ2つの曲線は 50 172 も離れる。計算複雑性クラスとは100個の要素についての主張ではなく、そこを比較することは誤ったアルゴリズムを選択するように自らを説得してしまう典型的な方法である — 15倍の差は、より高速なプログラミング言語を使えば埋められるように思えてしまう。スライダーを上に動かして、比率がそれに伴って増大するのを確認してほしい。実務において対数が軽視されがちであるのもこれが理由である。入力が1万倍に増える間に、対数は3倍にしか増えなかったのである。
-
学習の道すじ
秒ではなく仕事量を数える
参考文献 (1)
- The definition the lesson states, and the case for using it carefully: D. E. Knuth, “Big Omicron and big Omega and big Theta.” ACM SIGACT News 8, 18–24, 1976.