第３回計算量 - noldor's diary

計算量とは、アルゴリズムの速さの目安になるものです。入力データの個数をnとしたときの処理回数を大雑把に表します。
先のバブルソートだと $O(n^2)$ 、クイックソートだと $O(n log n)$ と書きます。

第１回のデータは

$input = array(5, 2, 4, 3, 4, 8, 7, 2, 1);

だったので、n = 9です。
計算量となる処理回数ですが、ループで何度もまわすので

2, 4, 3, 4, 5, 7, 2, 1, 8
2, 3, 4, 4, 5, 2, 1, 7, 8
2, 3, 4, 4, 2, 1, 5, 7, 8
2, 3, 4, 2, 1, 4, 5, 7, 8
2, 3, 2, 1, 4, 4, 5, 7, 8
2, 2, 1, 3, 4, 4, 5, 7, 8
2, 1, 2, 3, 4, 4, 5, 7, 8
1, 2, 2, 3, 4, 4, 5, 7, 8

で、台形の面積の公式に当てはめると (9 + 2) * 8 / 2 = 44 回です。
nで書くと (n + 2) * (n - 1) / 2 ですが、めんどくさいので

1, 2, 2, 3, 4, 4, 5, 7, 8

を足して三角形の面積の公式 n * n / 2 としましょう。 $\frac{1}{2}n^2$ ですが,計算量で書くときは係数の1/2は無視して $O(n^2)$ と書きます。
これは「このアルゴリズムは個数nの２乗に比例した処理回数ですよ」ということを表しており、データ数が増えれば増えるほど爆発的に処理時間がかかるということです。中学で習った放物線のグラフになります。
台形に戻ると、(n + 2) * (n - 1) / 2 = $\frac{1}{2}n^2 + \frac{1}{2}n - 1$ ですが、結局のところ放物線なので、一番次数の高い $n^2$ だけを書いて $O(n^2)$ と書きます。

つまり、計算量はデータ量の増加に対する処理回数の増え方の程度を表します。

ではクイックソートの $O(n log n)$ というのはどうなのかというと、一番効率よく処理されると

1, 2, 4, 3, 5, 6, 8, 7
1, 2, 3, 4, 5, 6, 7, 8
1, 2, 3, 4, 5, 6, 7, 8

というように、半分、また半分、と分割されるのでループ回数がかなり少なくなります。
正方形の面積の公式になりますが、横は n 、縦は log n になるので処理回数は n log n 、計算量は $O(n log n)$ になります（ log n は対数関数です。wikipediaのグラフを見ると、nの増加に対してあんまり上に伸びていかないのがわかります）。

さて、この例は「一番効率よく処理されると」という前提でした。では一番効率悪いとどうなるかというと「たまたま基準値に対し常に小さい状態だった」とかなると

1, 2, 3, 4, 5, 6, 7, 8
1, 2, 3, 4, 5, 6, 7, 8
1, 2, 3, 4, 5, 6, 7, 8
1, 2, 3, 4, 5, 6, 7, 8
1, 2, 3, 4, 5, 6, 7, 8
1, 2, 3, 4, 5, 6, 7, 8
1, 2, 3, 4, 5, 6, 7, 8
1, 2, 3, 4, 5, 6, 7, 8

という不幸な状態になり、これは $O(n^2)$ です。最悪なことにすでに整列されているデータに対してクイックソートかけるとこうなります（実際には実装の工夫によりこういう事態が起こらないようにします）。
一方、これにバブルソートをかけるとやっぱり $O(n^2)$ ではあるのですが、一度もデータ入れ替えが発生しないため処理１回あたりのスピードがむちゃくちゃ速く終わり、クイックソートの最速パターンより速く処理されます。

つまり、計算量は処理１回あたりの重さを考慮していないので、あくまで目安ということになります。たとえばマージソートというものはどんなデータが来ても $O(n log n)$ ですが、処理１回の重さでクイックソートに劣ります。

数学の難しいことはわからんという人は、 $O(n^2) > O(n log n) > O(n) > O(log n) > O(1)$ の順に軽いということと、log nが「半分また半分」であるということを押さえておけば良いと思います。

データが少ないうちはどのアルゴリズムでもすぐ処理が終わるので気にすることはありません。しかし「処理が重い」とユーザから言われるのはデータ量が多いときです。計算量を把握しておくと、実装するときのパフォーマンスの目安として良いものになります。
次は「最速」であるはずのクイックソートより速い $O(n)$ を実現する「分布数え上げソート」です。