計算量オーダー(Big-O)エクスプローラー

Big-Oは入力サイズが増えるにつれて処理量がどう増加するかを表します。単一のループはおおよそNに比例して増加し、入れ子のループはしばしばN²に比例して増加し、分岐する再帰は指数関数的に増加することがあります。重要な教訓はスケールです。Nが小さいうちは多くの手法が似て見えますが、Nが大きくなると増加クラスが実行時間を支配します。

増加クラスを最も直感的につかむには、入力を2倍にして作業量の変化を見ることです。O(log N) ではほとんど動かず — 二分探索は100万個の中から1個を約20回の比較で見つけます。O(N) では作業量が2倍になり、O(N²) では4倍になります。このツールで N を動かせば、その差が見えない状態から圧倒的な状態へ広がる様子がわかります。

増加クラスが低くても、プログラムが速いとは限りません。計算機科学者はその例外を銀河的アルゴリズムと呼びます。Big-O は優れていても、隠れた定数係数が途方もなく大きいため、物理的な宇宙にあるどんなものより大きな入力でしか単純な手法を上回らない手法です。記録を持つ行列乗算アルゴリズムのいくつかが実際には決して使われないのは、まさにこのためです。Big-O は実際の速度を左右する定数を、こっそり切り捨てているのです。