オーダー記法について

Question

オーダー記法についてなのですが
O()+O()のときは大きい方のO()を見ればいいのはわかるのですが、
O()O()のときのように掛け算のときはどのように簡略化すればよいのでしょうか？
例をあげると
O(n)O(nlogn)のようなときです。
自分は中身をかけて
O(n^2logn)としたのですがあっているのでしょうか？

Answer 1

結論から言えばその通りなのですが、オーダー記号の意味から考え直してみましょう。

O(f(n))とは、端的に言えばnが大きくなった際、最も強い影響を与える項がf(n)であることを示します。
例えばn^2+nは、n=10000のとき10^8+10^4となりますが、nの項による10^4は全体から見て微々たるもの(0.01%程度)なので無視できる項ということになります。したがってn^2+n=O(n^2)と表します。
なお、この記法で書く場合、係数は書きません。

ご呈示のO(n)O(nlogn)の場合ですが、
O(n) = an + (nより弱い項)
O(nlogn) = bnlogn + (nlognより弱い項)
ということになります。この掛け算を考えれば、n^2lognの項以外ははn^2lognよりも弱い項になります。
なので、この式のオーダーはO(n^2logn)になるのです。

Comments

[kotaro0121]

ありがとうございます。
しっかりと理解できました！