対数logについて

対数logについて
基本情報処理技術者試験の勉強をしているのですが、
オーダ記法のところで、よく使われる表現として
O(1) O(log n) O(n) O(n log n) O(n^2)
←計算時間小 計算時間大→
という五つの表現が紹介されているのですが、
このうち対数logを用いた物が理解できません。
例えば0(n)は、データ量nが2倍に増えれば計算時間も2倍になるということですよね。
しかしO(log n)だとどういう考え方になるのかわかりません。
対数についてもまだ理解できていないので、
対数のことから教えていただけないでしょうか。回答お待ちしてます。

No.2 ベストアンサー 回答者： jjon-com 回答日時： 2010/07/05 04:31

基本情報技術者試験で出題される対数であるなら，

常用対数（底が10である対数）ではなく，底が２である対数でしょう。
O(log n)，O(n log n) のように底を省略した表記は誤解を生みます。
O(log2Ｎ)，O(Ｎ×log2Ｎ) のように表記した方が良いです。
（nが底でないことを分かりやすくするため，大文字かつ全角文字でＮと書きました）

x＝log2Ｎ，とは，２のx乗＝Ｎ，と同じ意味です。
http://www.orcaland.gr.jp/kaleido/juken/taisu.html
http://www.shunzei.com/lecture/stepup/log.html

例えばO(log2Ｎ)とは，データ量Ｎが1024倍に増えても計算時間は10倍，データ量が100万倍に増えても計算時間は20倍，ということです。
（２の10乗＝1024，２の20乗≒１Ｍなので）

No.1 回答者： debukuro 回答日時： 2010/06/21 21:00

通常使うのは常用対数なのでそれでお答えします

１０を０乗すれば１になります
１０を１乗すれば１０
１０を２乗すれば１００
このようにある数ｎを表すのに１０を何乗すればいいかを１０を底としたｎの対数といいます
単にｎの対数といいます
たとえば２の対数は０．３０１０です
１０を０．３０１０乗すると２になります
実際には端数が沢山付くのですが実用上は０．３０１０
対数の良いところはかけ算を足し算に置き換えられることです
１０の対数は１です
１００の対数は２です
１０×１０は１＋１に置き換えることが出来ます
これは複雑な計算に威力を発揮します
計算尺の目盛りは対数目盛になっているのです

この回答へのお礼

丁寧な回答ありがとうございます。
O(log n)の考え方についてもよろしければ教えていただけないでしょうか。

お礼日時：2010/06/21 21:11