読者です 読者をやめる 読者になる 読者になる

素人がプログラミングを勉強していたブログ

プログラミング、セキュリティ、英語、Webなどのブログ since 2008

連絡先: すかいぷ:javascripter_  か javascripter あっと tsukkun.net skypeのほうがいいです

計算量とBig-O記法

プログラマであればアルゴリズムに関する話で、O(n)だとかO(log n)だとか、O(n2)だとか、そういった記号を目にすることはよくあると思う。 なんとなく、log n < n < n2の順に計算量が増加していくとかそういうことも知っていると思うが、計算量の増加とは何か説明しろと言われると、なかなか難しいと思う。この記事では高校数学レベルでわかるように考えていきたい。

まず、計算にかかる時間を、nを入力のサイズとしてf(n)を計算にかかる最大時間を返す関数とすると、計算量一般を、O(f(n))という、入力に対する計算時間の増加率として定義することができる(より厳密には、f:R+ -> R+ where R+=[0,∞)で、a>bであればf(a) >= f(b)であるとき)。

g(n) = n ^ 2

はn = 1に対して1を返す一方、より増加率の低い

h(n) = n + 100

は、n = 1に対して101を返すことに注意したい。言い換えると、関数の増加率の大きさと数字の大きさは違う。

では、どのように比較すればいいかというと、nが十分に大きくなると、増加量が大きい関数(n)>増加量が小さい関数(n)になるという性質を利用する。つまり、nを無限大に近づけて行ったときにおけるlim (n -> ∞)における大きさの違いを利用する。 ここで注意したいのは、正の極限値付近について

lim (n -> ∞) n + 100 = ∞
lim (n -> ∞) n ^ 2 = ∞

であることからわかるように、limによって導き出した∞は極限であって、大小の概念を含む一般の数値と違うことから、大小の比較には使えないということである。ただし、∞と∞の比較を避けることができれば、limを使っても、極値での大きさの比較はできる。つまり、

lim (n -> ∞) g(n) / h(n)

というように、比較したい二つの関数を分数の形にして∞自体を直接比較しなくて済むように変換する。

追記:コメント欄で指摘されたが、上記の定義だと、関数によっては振動して収束しない場合がある。limではなく、limsup/liminfを使って、上極限/下極限について考えると、これらも含めて定義できる。例えば、limsup( n -> ∞) |g(n) / h(n)| < ∞であればg(n) = O(h(n))、など。

この場合、lim(n -> ∞) g(n) / h(n)の値をkとしたとき (g(n)もh(n)も定義により常に正なので0/0は生じないことに注意)

追記2:最初O(f(n)) < O(g(n))と書いていたが、記号の使い方が不適切との指摘を受けたので訂正した。

  • kが正の無限大に発散するとき: O(f(n)) ⊊ O(g(n))
  • k∈Rでk != 0のとき: f(n) ∈ O(g(n))かつg(n) ∈ O(f(n))
  • k=0: O(g(n)) ⊊ O(h(n) となる。

先ほどの例の場合、

lim (n -> ∞) (n^2) / (n + 100) = ∞

となり、nは∞になるので、O(n2)の増加率のほうがO(n + 100)より大きいことがわかる。同様に lim (n -> ∞) (n + 100) / n = 1なのでO(n + 100)とO(n)が同一であることなどもわかる。

参考: ランダウの記号 - Wikipedia