アルゴリズムの計り方 - big-O notation -

近頃、各ソート技法をアニメーションで表示するAnimated Sorting Algorithm Demo | 秋元@サイボウズラボ・プログラマー・ブログがオレンジニュースで紹介されていたり、そういえば、WEB+DB PRESS vol.42にアルゴリズムとデータ構造の特集があったりと、アルゴリズムの話を目にすることがありました。気になったので、はるか昔に勉強したことを思い出しつつのメモです。
まずは基本となるbig-O notationから。
big-O notationというのは、とあるアルゴリズムがどれだけ効果的かを、そのアルゴリズムで扱われるデータ量をもとにした表記です。例えば、O(N)とか、O(log(N))とかです。大文字で書く"O"はorderのOで、読み方はO(n)の場合、"big o of n"となります。big-Oが一般的ですが、実はlittle-o notationというのもあって、bigもlittleも合わせてLandau Symbolsと呼ばれているようです。(Landau Symbols -- from Wolfram MathWorld)
よく目にする代表的なbig-O notaionの例を「Algorithmic Efficiency and Big-O notation - Cprogramming.com」を参考にいくつかあげてみます。

  • O(1)
    • アルゴリズムは何もせず、何が入力されても同じ定数を返す。つまり、計算量は1。
  • O(log(N))
    • Binary trees(完全な二分木のデータ構造)の計算量はこれになる場合が多い。木を構成するとあるノードを見つけ出す場合に、右か左かでデータは全体の1/2に限定し、さらに1/2の1/2の1/2、、、と限定していってひとつのノードを見つけるため。1/2*1/2*1/2*...となるので、底の2を省略してO(log(N))という表記を行う。
  • O(N)
    • A linear search algorithm。Linked listデータ構造の中から、とある要素を見つけ出す場合にこの計算量になることが多い。配列の要素は常に順番に一つずつチェックされる(ランダムにはアクセスできない)状況では入力がN個あると、N回探索を繰り返すことになるため(N個の入力に対応する値をlinked listから見つけ出すのにN回のループが必要)。
  • O(N*log(N))
    • Merge Sortのような効率の良いソートアルゴリズムはこの計算量になることが多い。Quick Sortはthe best caseではこの計算量になるが、the worst caseではO(N^2)(big o of n squared)に落ちてしまう。Merge Sortは入力データを再帰的に1/2, 1/2, 1/2,,,と分割していって、merge(統合)しながら、線形の比較を行うので、外側のループはO(log(N))、内側のループはO(N)となり、全体的にO(N*log(N))となる。
  • O(N^2) (big o of n squared)
  • O(2^N) (big o of two to the power of N)
    • 非常に大きな数字を素因数分解などする場合はこの計算量になることがある。

また、それぞれの計算時間は「Topcoder」によると、

[訂正(Sep. 04, 08)] Dijkstraのアルゴリズムのcomplexityは、O(2^N)ではなく、O(N^2)でした。

N=100の場合に、

  • O(log(N)): 10^-7 seconds (10の-7乗秒)
  • O(N): 10^-6 seconds
  • O(N*log(N)): 10^-5 seconds
  • O(N^2): 10^-4 seconds
  • O(2^N): 10^14 years

という数値があげられています。(最後のひとつはこれで正しいのかどうか疑問なのですが)

できるだけ少ない計算量で済ませられるようにプログラムを改善するための指標ですね。