関数の増大のイメージとBig O記法

先に、「\(n^2\) あるいは\(n \log(n)\)に対応した計算複雑性を考えることは、もちろんできます。\(n^2\)は、多項式時間のPに属しますが、\(n\log(n)\)は、nの多項式ではありません。Pとは別の、\(n\log(n)\)という計算複雑性を考えることは可能です。」と書きました。

ここでは、ある関数f(n)が、nが増えるにつれてどのように増大するかを具体的に見ておきましょう。次の図を見てください。

ここでは、次の8つの関数が表示されています。\(n!,  2^n,  n^2, n\log{n}, n, \sqrt {n}, \log {n}, 1 \)

\(n!,  2^n,  n^2, n\log{n} \)が nと比べて急速に大きくなることがわかります。それでも、\(n! > 2^n >  n^2 > n\log{n} \)ですね。nが大きくなるにつれて、その差はもっと大きなものになります。例えば、n=10の時、\(2^n\)は1024ですが、\(n^2\)は100、\(n\log{n}\)は、10の自然対数は、2.302... ですので、約23になります。

二つの関数 f(x)とg(x)があって、xがある値以上の時、ある正の定数cが存在して、常に f(x)よりcg(x)が大きい時、\(f(x) \in O(g(x))\)と表します。これをBig O記法と言います。イメージとしては、関数の値の増大に一番寄与している項を上限として取り出したものです（他の項は捨てます）。関数の定数倍の定数cも捨てます。

例えば、\(f(x)=4x^3-2x^2+5 \)という関数のBig O 表記を考えましょう。xが大きくなるにつれてf(x)の値の増大に一番寄与するのは、\(4x^3\)の項です。\(f(x)=O(4x^3)\)ですが、この定数の部分も省略して、\(f(x)=O(x^3)\)と表すことができます。

この表記で、多項式中のnの最大次数をkとして、多項式 poly(n)は、\(O(n^k)\)と表すことができます。