どれくらい速い？ビッグO記法

1秒に10億ステップなら、100万個の値に対して n² の方法は約17分かかりますが、n log n の方法は0.02秒です。

正確な回数より増え方が大切

ここまでは、比較45回、交換4回、調べる回数20回のように、ステップを正確に数えてきました。正確な回数は小さな例では役に立ちますが、バブルソートが途中で止まるかどうか、ピボットをどう選ぶかといった細かい点に左右されます。入力が大きくなると、ほかのすべてを圧倒するものが1つあります。nが大きくなるにつれて回数がどう増えるかです。ステップ数が n² のように増えるアルゴリズムは、どんなに念入りに調整しても、いずれは n log n のように増えるアルゴリズムに負けます。

ビッグO記法は、その増え方を短く書く方法です。アルゴリズムが O(n²)（「オーダー n の2乗」と読みます）であると書くのは、nが大きいとき、ステップ数がある定数かける n² 以下になるという意味です。2つのルールを使えば簡単に扱えます。定数倍は捨てます。3n も n/2 もどちらも O(n) です。いちばん速く増える項だけを残します。選択ソートの比較回数 n²/2 − n/2 は O(n²) です。nが大きいと、ほとんどが n² の部分になるからです。MITの6.006の講義でも、データ構造やソートを漸近的な実行時間で比べるときに、同じ考え方を使っています。

よく出てくる増え方

• O(1)、定数時間。仕事量がnによらない。リストの最初の値や、位置がわかっている値を読むことなど。
• O(log n)、対数時間。1ステップごとに問題が半分になる。二分探索。100万個の値で約20ステップ。
• O(n)、線形時間。各値を1回ずつ扱う。線形探索、最大の値を見つけること、リストの合計を求めることなど。
• O(n log n)。マージソートと、平均の場合のクイックソート。比較によるソートで達成できる最善。
• O(n²)、2乗時間。すべての組を調べる。最悪の場合のバブルソート、選択ソート、挿入ソート、または入れ子になった2つのループ。
• O(2ⁿ)、指数時間。値が1つ増えるごとに仕事量が2倍になる。n個のものの部分集合をすべて試すことや、ハノイの塔でn枚の円盤を動かすことなど。

数を秒になおすと

コンピューターが1秒に10億（10⁹）回の基本ステップを行うとしましょう。プロセッサのコア1つとして手ごろな概数です。100万個の値に対して、それぞれの増え方が何を意味するかを見てみます。O(log n) は約20ステップで、1マイクロ秒よりずっと短い時間です。O(n) は100万ステップで、1ミリ秒です。O(n log n) は約2,000万（20 million）ステップで、0.02秒です。O(n²) は 10¹² ステップで、1,000秒、約17分です。O(2ⁿ) は終わりません。2の100万乗は300,000桁を超える数です。アルゴリズムを正しく選ぶことが、たいてい速いコンピューターを買うよりずっと大切なのはこのためです。10倍速い機械なら17分は1.7分になりますが、O(n²) から O(n log n) に切りかえれば50分の1秒になります。

コードからビッグOを読み取る

増え方は、コードの形から直接読み取れることがよくあります。リストを1回たどるループは O(n) です。どちらもリスト全体をたどる2つのループが入れ子になっていれば O(n²) です。外側のn回それぞれで、内側のループが最大n回まわるからです。while (n > 1) n = Math.floor(n / 2) のように毎回数を半分にするループは O(log n) で、1,000から始めると9回、100万からなら19回まわります。順に続く手順は足し合わされ、大きいほうの項が勝ちます。O(n) のループの後に O(n²) のループが続けば、全体は O(n²) です。

// O(n): 1回たどる
let total = 0;
for (const x of list) total += x;

// O(n²): すべての組
for (let i = 0; i < list.length; i++)
  for (let j = i + 1; j < list.length; j++)
    if (list[i] === list[j]) console.log("duplicate", list[i]);

// O(log n): 半分にする
let k = list.length, rounds = 0;
while (k > 1) { k = Math.floor(k / 2); rounds++; }

最善、平均、最悪の場合

1つのアルゴリズムでも、入力によってふるまいが大きく違うことがあります。挿入ソートは、すでに整列したリストでは O(n)、逆順のリストでは O(n²) です。クイックソートは平均で O(n log n)、いつも悪いピボットを選ぶと O(n²) です。どの場合かを言わずにビッグOを1つだけ挙げるときは、ふつう最悪の場合を指します。それが保証になるからです。アルゴリズムはそれより悪くなることはありません。ビッグOには省かれていることもあります。定数倍を無視するので、小さな入力では、手順がとても簡単な O(n²) の方法が O(n log n) の方法に勝つことがあります。実際の多くのソート処理が、リストの短い部分では挿入ソートに切りかえるのはそのためです。