O(n log n)について2

質問

n log nはつまり１０の(nのn乗）乗という事ですね？
なにやらこちらの参考文献にはNの２乗よりn log nの方が効率が良いとあるのですが計算するとn log nのほうが数値が高くなるのですが、これはどういうことでしょう？

回答No.1

rinkun · ベストアンサー

> n log nはつまり１０の(nのn乗）乗という事ですね？
違う。logは対数だから、何乗かしたらnになる数を求める。
すなわち
　2^x=n
となるとき
　x=log n
だ。
なお、演算量の話をするときはlogの底は2を使うことが多い。
# オーダーの話では底が何でも結局は同じだが

具体的な数字で話をすると、n=1024のとき、log n = 10で、
　n log n = 10240
だ。
　n^2 = 1048576
なので、100倍以上小さいことが分かるだろう。

お礼

ありがとうございます！やっと分かりました。
No２さんの話も組み合わせれば、すなわち
　2^x=n 　　x=log n　　とは
(2^1)= 2 　1 = log 2　ということですね。
ちなみに底なるものが定数でないとき(9^1)= 9 1 = log 9と(3^2)= 9 2 = log 9は同じlog９でも数字が違うことから、底が定数でなければlog9のみから底の数字が何であるかは分からない分けですね。
n=1024　log n = 10は10=log1024であり2^10=1024という分けなのですね。
n log nは（n×log n）というわけですか。
ありがとうございました。

回答No.3

mtaka2

logそのものの意味については他の方が既に書かれているので省きますが、
オーダーは定性的な評価をするためのものですので、
「nが大きくなったとき、(計算時間やメモリ使用量が)どのような増え方をするか」という「式の性質」だけを考えます。
そういう点では「nに何らかの値を代入して個々の式の値を比較する」のは意味がありません。

たとえば、計算量が 100n に比例するものと n^2 に比例するものを比較して、
「n=10の時、100n=1000、n^2=100だから、n^2 の方が小さい」というのは無意味。
「100n は、nが2倍になると2倍になる」
「n^2 は、nが2倍になると4倍になる」
ので、最初は100n の方が大きくても、nがどんどん大きくなると、いつか必ず n^2 の方が大きくなります。

そういう観点では、100n も n も、性質は同じですので、オーダーを記述するときは定数倍数は省いて、どちらもO(n)と表します。

オーダーの基本的な性質としては、とりあえず最低限

O(n) > O(√n) > O(log n) > O(1)

という関係は成り立つのだ、と覚えておけばいいです。
(この関係が成り立つことを正しく説明するのは難しいのですが、
直感的に説明するなら、nに非常に大きな数を代入して調べればいいです。たとえば 1048576 を代入すると、
n= 1048576
√n= 1024
log n= 20
1 = 1
ですので、 n > √n > log n > 1 となります。

上記関係をおさえておけば、上記不等式をそれぞれn倍すれば、

O(n^2) > O(n√n) > O(n log n) > O(n)

なんてのも求まります。

お礼

ありがとうございました。

回答No.2

php504

log(対数)について
コンピュータの話なので対数の底を2として
log 2 = log (2^1) = 1
log 4 = log (2^2) = 2
log 8 = log (2^3) = 3
log 16 = log (2^4) = 4
log 32 = log (2^5) = 5
log 64 = log (2^6) = 6
log 128 = log (2^7) = 7
log 256 = log (2^8) = 8
log 512 = log (2^9) = 9
log 1024 = log (2^10) = 10
のような計算になります

お礼

ありがとうございます。書き出していただき分かりやすかったです。