- ベストアンサー
対数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)だとどういう考え方になるのかわかりません。 対数についてもまだ理解できていないので、 対数のことから教えていただけないでしょうか。回答お待ちしてます。
- cat0123
- お礼率40% (36/90)
- 情報処理技術者
- 回答数2
- ありがとう数57
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
基本情報技術者試験で出題される対数であるなら， 常用対数（底が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乗≒１Ｍなので）
その他の回答 (1)
- debukuro
- ベストアンサー率19% (3635/18948)
通常使うのは常用対数なのでそれでお答えします １０を０乗すれば１になります １０を１乗すれば１０ １０を２乗すれば１００ このようにある数ｎを表すのに１０を何乗すればいいかを１０を底としたｎの対数といいます 単にｎの対数といいます たとえば２の対数は０．３０１０です １０を０．３０１０乗すると２になります 実際には端数が沢山付くのですが実用上は０．３０１０ 対数の良いところはかけ算を足し算に置き換えられることです １０の対数は１です １００の対数は２です １０×１０は１＋１に置き換えることが出来ます これは複雑な計算に威力を発揮します 計算尺の目盛りは対数目盛になっているのです
関連するQ&A
- 漸化的計算量のオーダー記法O表記について
漸化的計算量のオーダー記法O表記について オーダー記法Oでの表記の仕方って、ようするにnをn→∞とした時に、一番大きくなる項を抜き出しきて、n→∞の時、増加量が微少な係数は無視をする。という考え方でいいんでしょうか？ 例えば 1000*(2^n)+0.5(n^n)=O(n^n) nlogn+n√n=O(n√n) n^2.01+(n^2)log(n^2)=O((n^2)log(n^2)) であってますか？
- ベストアンサー
- その他([技術者向] コンピューター)
- ソフトウェア開発技術者～対数logについて
ソフトウェア開発技術者の参考書に、計算量の大小関係と称して次のような式が掲載されていました。「1＜log n＜n＜n log n＜n^2＜…」 恥ずかしながら、どうしてこうなるのかがわかりません。そもそも、対数logには「底」というものが必要ではないのでしょうか？ 3＝log28(2は底)というように。
- ベストアンサー
- 情報処理技術者
- 対数（log）について教えて下さい。
対数（log）の基本的な概念は理解したのですが、（基本的な概念→2=log[3]9）たまに以下のような記述をみかけます。 ・log n ・n log n logの右に値が一つしかありませんが、これらはどのような値なのでしょうか？logの右にあるnは底でなく真数でしょうか？ 調べていると常用対数という言葉を知りましたが、底を１０とする対数を常用対数といい、底の記述を省略することが出来るとありました。 上記二点はどちらも底１０を省略した書き方なのでしょうか？そうだとすると、nが１００だった場合、例えばlog 100=log[10]100=2、100 log[10]100=100*2=200ということでしょうか？
- ベストアンサー
- 数学・算数
- 対数の変形の仕方を教えてください
お世話になります、対数が元々苦手だったのですがもう一度覚えるため質問させて頂きます。 [問] 14けたの16進数の最大値は,10進数で表すと何けたか。ここで,log[10]2=0.301とする。 ア 15 イ 16 ウ 17 エ 18 [解説] 14けたの16進数の最大値は16^14-1であり、これが10進数でnけたとすると (1)10^n-1≦16^14-1<10^n 常用対数をとってこのようになる (2)n-1<14log[10]16≦n (3)14log[10]16≦n<14log[10]16+1 (4)56log[10]2≦n<56log[10]2+1 (5)56×0.301≦n<56×0.301+1 (6)16.856≦n<17.856 したがってn=17 10進数で17けたで表せる。 [質問] (1)～(2)の変換で 常用対数をとってこのようになる、との解説があるのですが 「常用対数をとって」の意味が理解できません、手前勝手な解釈で各辺に log[10]掛けるという意味なら (2)は 10^n-1→10log[10]n-1 16^14-1→14log[10]16 10^n→10log[10]n となり、このようになると思うのですが (2)10log[10]n-1<14log[10]16≦10log[10]n 恐らく基本的な対数の変形式が理解できていないためだとおもいます (1)～(2)の変形の理由を馬鹿でも分かるようにご教授お願いいたします。
- ベストアンサー
- 数学・算数
- 対数の計算
Ω=(1/N!)*(V^N/h^3N)*{π(2π^2*mE)^[(3/2)N-(1/2)]}/Γ[(3/2)N+1] として Ωの対数をとって計算していくと Γ(n+1)!=n! logN!=NlogN-N を用いて logΩ=log1-logN!+logV^N-logh^3N+[(3/2)N-(1/2)]logπ(2π^2*mE)-logΓ[(3/2)N+1] =log1-NlogN+N+NlogV-3Nlogh+[(3/2)N-(1/2)]logπ(2π^2*mE)-logΓ[(3/2)N+1] =・・・・・と計算していけるんですが どうしてもlogΩ=NlogV+(3/2)Nlog(2E/3N)+・・・・・・ （・・・はVとEを含まない項) 教科書によれば最終的にはlogΩ=NlogV+(3/2)Nlog(2E/3N)+・・・・・・ （・・・はVとEを含まない項)という式なるはずで、この式をを導きたいんですが、計算でうまくいかないんです。 なかなかlogΩ=NlogV+(3/2)Nlog(2E/3N)+・・・・・・ （・・・はVとEを含まない項)に もっていけないんで、それの計算過程を教えていただきたいです。
- ベストアンサー
- 数学・算数
- 常用対数の応用？(数学II)
常用対数の応用での基本問題からです。 問 「不等式(1/2)^n＜0.001を満たす整数nの最小値を求めろ。但しlog[10]2=0.3010とする。」 さっぱり分らないので、常用対数の応用というのを足掛りに適当にアプローチしてみました。突っ込み願います。 与式は、2^-n＜10^-3と変形出来る。 両辺の常用対数をとると、 log[10]2^-n＜log[10]10^-3 より、-n・log[10]2＜log[10]10^-3 だから、 -n・0.3010＜-3より、n・0.3010＞3。 ここで、不等式を満たす整数は1、2、3、4……と無数にあるが、求めるのは最小値であるから、n=1 投げやりでお恥ずかしい限りではありますが、何卒ご協力お願いします。
- ベストアンサー
- 数学・算数
- 再：log計算につきまして
問題集の例題の解説で、 A≒log[2]N の 対数の底を10に変換すると、 A≒log[2]N = log[10]N/log[10]2 とされているのですが、「対数の底を10に変換する」の意味・方法が分かりません。 どなたか教えていただけますでしょうか？ よろしくお願いいたします。 ＊[]内の数字は右下に小さい数字とお考えください。
- ベストアンサー
- 数学・算数
お礼
丁寧な回答ありがとうございます。 O(log n)の考え方についてもよろしければ教えていただけないでしょうか。