わかりやすく ビッグオー とは

秒ではなく回数

秒で測ると迷います。速いコンピュータでは、遅い方法も速く見えるからです。
そこで秒のかわりに、「何回働くか」を数えます。
マスがn個のとき、働く回数は方法ごとに違います。

入力の大きさを選ぶと、方法ごとの働く回数が出ます。（一つずつ = n回 · 半分ずつ = ずっと少ない回数）

マスが少ないうちは、二つは似て見えます。
8マスなら一つずつで8回、半分ずつで3回。たいした差はありません。
では、マスをぐっと増やしたらどうなるでしょうか。

大きくするとどうなるか

ここで本当の差が見えてきます。
nを大きくすると、ある方法はマスが増えた分だけゆっくり増え、別の方法はマスが二倍になるたびに仕事が四倍に跳ね上がります。
nかけるn、これをn²と書きます。

ボタンを押すたびにマスが二倍になります。nはマスの分だけ増えますが、n²はマスが大きくなるほど爆発するように増えます。

n²が怖いのは、マスが多いときです。
100マスならnは100、n²は10000。1000マスならnは1000、n²は百万になります。
小さく始まっても、あっという間に手に負えないほど大きくなります。

曲線を並べる

三つの増え方を並べると、ひと目でわかります。
log nは、マスがいくら大きくなってもほとんど上がりません。
nはまっすぐ斜めに上がり、n²は上へ曲がって、はるか高くまで突き抜けます。

曲線を一つずつ点けて比べます。同じnでも、log n · n · n²の高さはまるで違います。

これで、半分ずつ切る方法がなぜあんなに速かったのかがわかります。
半分ずつはlog nなので、マスが千個でも十回ほどで終わります。一つずつはnなので、千個なら千回かかります。
勝負を分けたのは、増え方の形でした。

いちばん大きな項だけ残す

実際の回数を数えると、3n²+5n+9のような込み入った式になります。
でもnがとても大きくなると、n²がほかの項をすべて圧倒します。
だから小さな項は消して、いちばん速く増えるn²だけを残します。

押すたびに、小さな項と前の数字が一つずつ消えます。3n²+5n+9でnが大きいとn²だけが残り、その形を書いたものがビッグオー（O）です。

前の数字も消します。3n²でも100n²でも、増え方の形は同じn²だからです。
そこで、ただO(n²)と書きます。
ビッグオーは、「入力が大きいときにどんな形で増えるか」を一行で書いた名札です。

ここまで来た道

まとめるとこうです。速さは秒ではなく、増え方の形で測ります。
マスnが大きくなると、log nはほとんど増えず、nはマスの分だけ増え、n²は爆発します。
式が込み入っていても、いちばん大きな項一つを見ればよく、それを表す記号がビッグオーです。

三つの項を一つずつ点けて、一行にまとめます。log nはほぼ平ら、nは斜め、n²は上へ爆発。大きな項だけ見れば十分です。

これからは方法を見れば、秒を測らなくても速いかどうか見当がつきます。
マスが二倍のとき仕事も二倍なら大丈夫、四倍に跳ねたら要注意です。
よい方法とは、大きな仕事を前にしてもゆっくりとしか増えない方法です。