イノベーション エンジニアブログ


株式会社イノベーションのエンジニアたちの技術系ブログです。ITトレンド・List Finderの開発をベースに、業務外での技術研究などもブログとして発信していってます!


このエントリーをはてなブックマークに追加

アルゴリズム計算量入門 〜 ①

はじめに

どうも、bigenです。
最近、弊社の新人エンジニア向けに勉強会が頻繁に行われています。
その中で、ソートアルゴリズムやサーチアルゴリズムを自力で実装してみる練習問題がありました。

ソートやサーチなどのアルゴリズムは計算量の考え方を学ぶのにもちょうどいい題材で、知っていることを社内共有用も兼ねてブログにまとめて行こうかと思います。

今回はソートアルゴリズムの計算量について考えていきます。

内容

  • 計算量とは

    • リソースの種類による分類

      • 時間計算量(time complexity)

      • 空間計算量(space complexity)

    • 扱うデータの種類による分類

      • 最悪計算量(worst-case complexity)

      • 平均計算量(average-case complexity)

  • ソートアルゴリズムの計算量について

    • バブルソート

    • バケツソート

    • マージソート

    • どう違うの?

計算量とは

計算量とは、英語ではcomputatoinal complexityあるいは単にcomplexityといいます。
直訳すると「計算の複雑さ」です。
複雑さといっても、指標は色々あり、

  • 計算にどのぐらいの時間がかかるか(時間計算量)

  • 計算にどれぐらいのメモリが必要か(空間計算量)

  • どれぐらい計算時間にばらつきがあるか(平均計算量、最悪計算量、最良計算量)

といった観点があります。

時間計算量(time complexity)

時間計算量は、計算にどのぐらいの時間がかかるか、を示す指標です。
計算量について議論する場合、やはり時間についてに制約がネックになる場合が多く、 単に「計算量」といった場合「時間計算量」を指すことが多いです。

具体的な時間(xx秒で終わる、xx日で終わる)で議論しようとすると CPUやメモリのスペック、場合によってはインターネット環境など色々な要素に左右されてしまうため、 アルゴリズムについて考える場合は

  • 「データの規模」に対して計算時間がどれぐらい依存するか

という観点で議論されます。
たとえばソートアルゴリズムだと、配列の要素数が100倍になったら計算時間は10000倍になるよね、とかとういった具合です。

空間計算量(space complexity)

空間計算量(あるいは領域計算量)は、計算にどれぐらいメモリが必要か、を示す指標です。
こちらも時間計算量と同様に、「データの規模が大きくなるにつれ専有するメモリがどのくらい増えるか」という観点で議論されます。

処理を並列化させて同時に複数の計算を進めるようなアルゴリズムの場合、 空間計算量がネックとなる場合があります。

最悪計算量(worst-case complexity)

最悪計算量は、もっとも時間がかかるデータを相手にした場合、計算量がどれぐらいになるかを考える指標です。
通常、時間計算量に対して考えますが、明示的でない場合は「最悪時間計算量」「最悪空間計算量」などと使い分けます。

アルゴリズムの性能を考える場合は、多くの場合この最悪計算量を基準に考えます。
「平均1分で終わるんだけど、運が悪いと1年かかるんだよねー」
とか言われたら使えないですよね?
そういうことです。

同様に最良計算量という指標もありますが、アルゴリズムの性能を議論する際にはあまり使われません。

平均計算量(average-case complexity)

平均計算量は、あらゆる種類のデータを相手にしたときに、平均的に計算量がどのくらいになるかを考える指標です。
通常、時間計算量に対して考えますが、明示的でない場合は「平均時間計算量」「平均空間計算量」などと使い分けます。

最悪計算量となるケースが極端に少ないとわかっている場合や、最悪ケースになった計算を無視できる(時間がかかるデータは処理を中断して破棄してもよいケースなど)場合などは平均計算量が重視されます。+

ソートアルゴリズムの計算量について

ソートアルゴリズムの中から、代表的なアルゴリズム3つについて、計算量の特徴を見ていきたいと思います。


バブルソート

言わずも知れたバブルソートです。
データの数をnとすると、最悪時間計算量はO(n2)空間計算量はO(n)となります。

計算量の導出などは下記の資料が非常に参考になりますので、参考にしてみてください。
アルゴリズムとデータ構造第2回 東北大学 塩浦昭義

はい。多分多くの人はこれで意味わかんねってなりますよね?
詳しい説明は資料を参照してほしいのですが、
「計算時間はデータの数の(だいたい)2乗に比例する」
という意味です。
もう少し具体的に言うと、 データの数が10倍になったら計算時間は100倍、データの数が100倍になったら計算時間は10000倍になる、ということです。

アルゴリズムを思い出してみると、n個のデータそれぞれに対して、自分以外のn-1個のデータに対して「俺より大きい?小さい?」と比較を繰り返します。
ソートが終わったデータに対しては比較する必要がないのでもう少し少なくなるんですが、それを込みで考えても計算時間は
(n-1)(n-2)/2回 * (比較一回の計算時間) = (n2 - 3n + 2) * c
の比較が行われます。
nの数がかなり大きくなっていくと、-3nに比べてn2は爆発的に大きくなり、 -3nだとかcしてるだとかの部分はほぼ無視できるようになります。
【参考(n=10000のとき)】
(n2 - 3n + 2)c = (100000000 - 30000 + 2)c
        ↑これに比べて↑これはほぼ無視できる

結局n2の部分がどれぐらい大きいかだけ注目しておけば大体の計算量を見るには十分ということになり、これを数学的に表現したのが O(n2)という記号です。

空間計算量については、バブルソートは計算用に一時的にデータを記憶したりする必要はないので、データの数分の配列が確保できれば十分です。
なので、 O(n) となります。

バケツソート

バケツソートは少し特殊なアルゴリズムで、あらかじめデータのとりうる範囲がわかっている必要があります。
データの数を n個、データのとりうる範囲(用意するバケツの数)をmとすると、最悪時間計算量はO(m+n)、空間計算量も O(m+n) となります。

計算量の導出について詳しくは
アルゴリズムとデータ構造第3回 東北大学 塩浦昭義
がわかりやすいくまとまっています。

簡単にいうと、ぞれぞれのデータを1回ずつ見て(合計n回)バケツに投げ入れ、各バケツに入っているデータの数を調べる(m回)ので、大体n + m回ぐらい計算するよね、っていうことです。
空間計算量も、n個のデータを保持する配列と、m個のバケツを保持する配列ぐらいのメモリがあればOKということです。

マージソート

マージソートは、最悪時間計算量 O(n log n)、空間計算量 O(n) となります。

ここでまた多くの人がつまずきがちな log nという謎の記号が出てきました。
log というのは対数と呼ばれる記号で、超ざっくり説明すると 「データの数が100倍になっても計算時間は3倍、データの数が10000倍になっても計算時間は5倍」っていうことです。
データの数が増えれば確かにlog nも増えるんですが、そのスピードはめっちゃ遅いです。

計算量の導出はかなり難しいですが、興味ある人は下記を参照してください。
アルゴリズムとデータ構造第2回 東北大学 塩浦昭義

どう違うの?

ここまで O()という記号についても触れ、めっちゃ大きいとかめっちゃ遅いとか書いてましたが、具体的にどれぐらい差があるか見てみましょう。

n = 100 n=10000 n=1000000 100000000

log n

2

5

7

9

n

100

10000

1000000

100000000

n log n

200

50000

7000000

900000000

n2

10000

100000000

1000000000000

10000000000000000

具体的に見ても0の数が多すぎて分かりづらいかもしれませんが、100万件のデータをソートするのに
・バケツソートだと1時間
・マージソートだと7時間
・バブルソートだと114年
ぐらいの差が出るってことですね。

途中の計算の時に「1回の反復にかかる時間cとか無視しちゃいましょう」、とか言っていたことを思い出してほしいのですが、 これを見ると
「一回の反復はバブルソートよりマージソートのほうが複雑だから、マージソートはcが30倍ぐらい違うよ!」
とか言っても 「だから?」 ってなるのがよく分かりますね

あと、対数logがめっちゃ遅いっていうのもわかってもらえるかと思います。


時間計算量 だけを見るとバケツソート最強じゃんと思いますが、バケツソートはあらかじめデータの取りうる値の範囲がわかっていないと使えないという強い制約があります。

これは、例えばメールアドレスのような長さがはっきりとは決まっていないものには使えないということになります。
他にも、空間計算量がデータの範囲mに依存しているため、日本語の名前などにも使えません。
常用漢字だけでも2136字あり、名前に使われる文字数が最大6文字としても、21366 ~ 1020、つまり1垓個の配列を用意する必要があります。

このような制約をクリアできるデータであれば、バケツソートは非常に高速だと言えるでしょう。

おわりに

今回は計算量を考える時の基本的なスキーマについて説明し、ソートアルゴリズムの計算量について少し具体的な数値を見てみました。
興味が湧いた方は、ぜひ導出方法についても見てみてください。

こちらからは以上です。