オーダー記法の考え方がわかりません。

Question

オーダー記法についてです。
100(n^3)logn=O((n^3)logn)
上記が正しいかどうかを確認したいです。

こちらのURLを見たら、logn=O(n)と書いてあったのでわからなくなりました。
lognがO(n)になるのなら問題の(n^3)lognは
n^3*n=n^4だから、O(n^4)
という形になるのでしょうか。

Answer 1

オーダー記法には上界と下界とその両方を示すものの3種類があります。
そのPDFでは、定義上、上界のみを問題にしてるのでlogn=O(n)が正しいということになります。
同様に100(n^3)logn=O(n^4)も100(n^3)logn=O((n^3)logn)も正しいです。

Comments

[langhtorn]

PDFの内容についてよくわかりました。ありがとうございます。

Answer 2

f(n)=O(g(n))
であるとは、nが大きくなった時、f(n)とg(n)の増え方を比較するとf(n)の方がg(n)よりも増え方が遅い、もしくは同じ程度であることを意味します。
log n = O(n)は、log n の方がnよりも増え方は遅いという意味になります。
グラフを書いてみたりすると、このことは容易に確認できます。
同様に、n^2やn^3よりもlog nの増え方が遅いので、
log n = O(n^2)
log n = O(n^3)
と表すこともできます。

Comments

[langhtorn]

これからグラフも交えて考えてみます。ありがとうございました。