【復活求む!】惜しくも解散してしまったバンド|J-ROCK編 >>

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

このQ&Aに関連する最新のQ&A

A 回答 (2件)

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


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

x=log2N,とは,2のx乗=N,と同じ意味です。
http://www.orcaland.gr.jp/kaleido/juken/taisu.html
http://www.shunzei.com/lecture/stepup/log.html

例えばO(log2N)とは,データ量Nが1024倍に増えても計算時間は10倍,データ量が100万倍に増えても計算時間は20倍,ということです。
(2の10乗=1024,2の20乗≒1Mなので)
    • good
    • 3

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


10を0乗すれば1になります
10を1乗すれば10
10を2乗すれば100
このようにある数nを表すのに10を何乗すればいいかを10を底としたnの対数といいます
単にnの対数といいます
たとえば2の対数は0.3010です
10を0.3010乗すると2になります
実際には端数が沢山付くのですが実用上は0.3010
対数の良いところはかけ算を足し算に置き換えられることです
10の対数は1です
100の対数は2です
10×10は1+1に置き換えることが出来ます
これは複雑な計算に威力を発揮します
計算尺の目盛りは対数目盛になっているのです
    • good
    • 0
この回答へのお礼

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

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

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

QO(n log n)について2

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

Aベストアンサー

> n log nはつまり10の(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倍以上小さいことが分かるだろう。

Qlog2nと(log n)2の違いは何ですか?

log2nと(log n)2の違いは何ですか?
前者の2は低ではなく、上付き文字です。
よろしくお願いします。

Aベストアンサー

#1です。

A#1の補足の質問の回答
>前者はlog(2n)ではなく、logの上付き文字に2があります。
log^2 n
という表現は一般的には使われていない表現と思います。

一般的でないので、その記述を使った文献等の中で何らかの定義をしているかと思いますので、確認してみてください。

可能性としては
log(log n)
の意味の表現である可能性が高いですね。

その場合は
n=1のとき
log^2 n =log(log(1))=未定義

n=eのとき
log^2 n =log(log(e))=log(1)=0

n=1/2のとき
log^2 n =log(-log(2))=未定義

となり、A#1に書いたように
(log(n))^2=0(n=1のとき)
=1(n=eのとき)
     =(log(2))^2(n=1/2のとき)
とは異なりますね。

Q基本情報試験の対数の問題について

基本情報の試験勉強をしていますが、対数でつまづいています。

以下の式において

LOG 2 100000000
= LOG 2 10 8
= 8 LOG 2 10
= 8 * 3.321928
= 26.57542

= 8 * 3.321928の式

がわかりません。
要は、2を何乗すると10になるかということだと理解していますが、この3.321928という値はどういう計算で出てくるのでしょうか?

Aベストアンサー

情報処理技術者試験(基本・応用)の試験勉強に限定するならば,

log2(10)「2を何乗すると10になるか」という数が,
log2(8) 「2を何乗すると 8になるか,答えは3」と
log2(16)「2を何乗すると16になるか,答えは4」の間に挟まれていること。

つまり 3<log2(10)<4 の関係にあることが分かれば解ける計算問題しか出題されていないはずです。

今回ご質問のあった問題は,正式に対数を求めなくても,試験対策としてもっと要領のいい簡便な解き方があるんじゃないでしょうか。

Q法(mod)の四則演算について

とても困ってます。
情報セキュリティの課題で

・整数は素数を法とする演算では、四則演算が実行できる。その例を示せ。
・整数は合成数を法とする演算では、四則演算の一部で、解が一意に定まる場合と定まらない場合がある。その例を示せ。

この2つの問題が分かりません。
答えを教えていただけませんか?お願いします。

Aベストアンサー

以下、剰余算の計算式を「13 mod 7 = 6」(13÷7の余りが6という意味)のように表します。suryaさんの読みやすいように適宜読み替えて下さい。

・法が素数の場合
2つの整数(5, 13)を7で割ったときの剰余の四則演算の例を以下に示します。

1. 加算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7) + (5 mod 7) = 11 mod 7 = 4 … (1)
また、(13 + 5) mod 7 = 18 mod 7 = 4 … (2)
(1)と(2)は同じ値になるので、(13 mod 7) + (5 mod 7) = (13 + 5) mod 7

2. 減算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7) - (5 mod 7) = 1 mod 7 = 1 … (1)
また、(13 - 5) mod 7 = 8 mod 7 = 1 … (2)
(1)と(2)は同じ値になるので、(13 mod 7) - (5 mod 7) = (13 - 5) mod 7

3. 乗算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7) × (5 mod 7) = 30 mod 7 = 2 … (1)
また、(13 × 5) mod 7 = 65 mod 7 = 2 … (2)
(1)と(2)は同じ値になるので、(13 mod 7) × (5 mod 7) = (13 × 5) mod 7

4. 除算
剰余の除算は整数や実数といった一般的な数値の除算と異なるので注意して下さい。
剰余での除算は「逆数を掛ける」ことで定義されます。「aをbで割る」はa×b^-1で表されます。

(3 mod 7) × (5 mod 7) = 1なので、(5 mod 7)^-1 = (3 mod 7)
また、3.乗算の結果から、(13 × 5^-1) mod 7 = (13 mod 7) × (5 mod 7)^-1が言える。これを計算すると、
(13 × 5^-1) mod 7 = (13 mod 7) × (5 mod 7)^-1 = (13 mod 7) × (3 mod 7) = 4


・法が合成数の場合
良い例かどうかは分かりませんが…。
法が8のときの除算を例に挙げてみます。

例えば、(5 mod 8) × (3 mod 8)^-1は(3 mod 8) × (3 mod 8) = 1だから、
(5 mod 8) × (3 mod 8)^-1 = (5 mod 8) × (3 mod 8) = 7のように計算できます。
しかし、(5 mod 8) × (4 mod 8)^-1は、4 mod 8の逆数を求めることができないため計算できません。

以下、剰余算の計算式を「13 mod 7 = 6」(13÷7の余りが6という意味)のように表します。suryaさんの読みやすいように適宜読み替えて下さい。

・法が素数の場合
2つの整数(5, 13)を7で割ったときの剰余の四則演算の例を以下に示します。

1. 加算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7) + (5 mod 7) = 11 mod 7 = 4 … (1)
また、(13 + 5) mod 7 = 18 mod 7 = 4 … (2)
(1)と(2)は同じ値になるので、(13 mod 7) + (5 mod 7) = (13 + 5) mod 7

2. 減算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7...続きを読む

Q整列の比較回数を表す数式でよく見るO(n log n)のOって何ですか

タイトルどおりなのですが、数式の(n log n)とO(n log n)では何がちがうのですか。
どなたか教えてください。

Aベストアンサー

 とりあえず、O()が計算量の増え方を表すための記号である、というところはOkなのでしょうか?


>それは1/2が微量だということです

 「微量」という書き方がまずかったですね。「定数」です。データ量に依存しないので、無視します。と、本にも書いてあると思います。


 計算量がどれくらいの勢いで増えていくかというのを見るためのものなので、実質的には

・O(1) … ハッシュなど データ数によらずに常に一定
・O(n^2) … バブルソートなど データ数により急激に増える
・O(nLog(n)) … クイックソートなど データ数による増え方が緩やか
・O(n) … リストへの挿入など データ数による増え方が単純にデータ数に依存

くらいしか、使いません。ここで、「1」や「n^2」などより、「データ数によらずに常に一定」や「データ数により急激に増える」の方が重要なのです。いわば、この言葉を表すための便宜上の記号といってもいいかもしれません。


 n^2も、n(n-1)/2も、結局nとn(に近い値)を掛け合わせているので、右肩上がり、しかも急激に増えていきます。この「急激に増える」というのが知りたい/示したいのです。確かに計算そのものの回数は半分ですが、この「O()」が表したいのは、1億回処理するか、5千万回処理するか、ではなく、
『データ量が増えたときに処理する回数がどのような増え方をするか』
ということです。エクセルでグラフを描いてみると、よくわかると思います。「増え方」を見るので、実際の計算回数が半分だろうが百万回少なかろうが、関係ないのです。くれぐれも、「何回増えたか」ではないですよ。

「回数」ではなく、「増え方」を見るのです。と、他の方も書かれているのですが、それが理解できませんか?そのことを説明するための文にたいしてつっこんでいますけど。
#2: 「回数がどのように変化するかを大まかにみる指標」
#3: 「計算負荷の増え方を示す事ができるOという擬似関数」
  「「増え方の度合い」とでも言う」
#4: 「計算の回数の“増え方”を表現するもの」


つまり、(n log n)は、nが決まったときの特定の数値(もしくは計算の方法)を表し、O(n log n)は、「データ数による計算回数の増え方が緩やか」であることを表します。

 とりあえず、O()が計算量の増え方を表すための記号である、というところはOkなのでしょうか?


>それは1/2が微量だということです

 「微量」という書き方がまずかったですね。「定数」です。データ量に依存しないので、無視します。と、本にも書いてあると思います。


 計算量がどれくらいの勢いで増えていくかというのを見るためのものなので、実質的には

・O(1) … ハッシュなど データ数によらずに常に一定
・O(n^2) … バブルソートなど データ数により急激に増える
・O(nLog(n)) …...続きを読む

Qべき乗

べき乗とは一体なんですか?
ウィキを見ても理解できませんでした。
2の2乗は2×2ですが、
2のマイナス2乗は一体どのような式なのですか?

Aベストアンサー

算数の延長線上だけの概念だけだといまいち理解出来ないですよね。
べき乗って要は指数なんですけど、
そういう難しい話を出来るだけ捨てて、算数の世界で説明出来る位まで掘り下げて説明します。

例えば 10の2乗は100、10の3乗は1000となります。
これを数字の動きに目を合わせてもう一度、書いてみます。
00010.00000 ←これを2乗すると↓
00100.00000 //10という値が左に1つずれた結果が答え

00010.00000 ←これを3乗すると↓
01000.00000 //10という値が左に2つずれた結果が答え

こういう風に表す事が出来ます。
じゃあ、10のマイナス2乗ってなった場合はどうなるのかというと、
00010.00000 ←これを-2乗する↓
00000.01000 //10という値が右に3つずれた結果が答え

という答えになります。
1を基準点として、右や左にいくつずれるか。
これがべき乗なのです。


で、2のべき乗を考えた時は、
全部2進数で考える必要があります。
00010.00000 ←2進数で表した数値の2
00100.00000 ←2乗した結果。数値で言うと4
00010.01000 //-2乗した結果。数値で言うと0.25


これで何となく分かっていただけたでしょうか?
ちなみに37のx乗を計算するみたいな時があったとしたら、
それは37進数で考えるという計算が必要になるのです。

算数の延長線上だけの概念だけだといまいち理解出来ないですよね。
べき乗って要は指数なんですけど、
そういう難しい話を出来るだけ捨てて、算数の世界で説明出来る位まで掘り下げて説明します。

例えば 10の2乗は100、10の3乗は1000となります。
これを数字の動きに目を合わせてもう一度、書いてみます。
00010.00000 ←これを2乗すると↓
00100.00000 //10という値が左に1つずれた結果が答え

00010.00000 ←これを3乗すると↓
01000.00000 //10という値が左に2つずれた結果が答え

こういう風...続きを読む

Q「すいません」と「すみません」どちらが正しい?

 タイトルにあるとおり、素朴な疑問になりますが、「すいません」と「すみません」ではどちらが日本語として正しいのでしょうか。分かる方ぜひ教えてください。

Aベストアンサー

もともとは「すみません」ですが、「すいません」と発音しやすく変えたものもたくさん使います。
話す時はどちらでもいいですよ。

ただ、私個人の語感で言うと、公式的な場では「すみません」の方がいいような気もします。「すいません」はちょっとくだけた感じかな。でも、これはあくまで私個人の語感。人によって、あるいは地方によっても感じ方は違うだろうと思います。

書くときはもちろん「すみません」にしましょう。

発音しやすく変化した発音の他の例としては
手術(しゅじゅつ→しじつ)
洗濯機(せんたくき→せんたっき)
などがあります。これも、話す時にはどちらでもいいです。「しじつ」「せんたっき」と書いてはいけませんが。

Qマージソートの計算量について-O(n*logn)

マージソートの計算量はO(n*logn)ですが、なぜそうなのかが理解出来ません。要素数が2, 4, 8, 16, 32, 64...と増加すると二分割するのにかかる時間は1, 2, 3, 4, 5, 6..となり、n=2^x, x=lognとなるところまでは理解出来ました。しかし更にnをかける必要があるのはどうしてでしょうか。要素数が1になるまで分割した後に、小さい順番に比較しながら統合して行く作業があり、これにも当然ランニングタイムがかかるのはわかりますがなぜこの要素の比較コスト?が*nなのでしょうか。
またウェブで調べると、他にもT(n)=2T(2/n)+O(n)という別の説明もあり、こちらも理解出来ません。この説明は上の説明とはまた別の角度から説明しているものなのでしょうか。わかる人がいたら教えて下さい。

Aベストアンサー

ソートの計算量を議論するときは、通常「比較回数」を考えます。

(正確には、全ての計算の手間を数えあげる必要がありますが、通常
・計算処理の中で「比較回数」が最も多くなる
・計算量(オーダー)では次数の低い項は無視できる
ので、比較回数以外は考える必要がなくなります)

ですので、マージソートの計算量を考える場合、「分割にかかる時間」ではなく、「(比較しながら行う)分割した部分列を統合していくのにかかる時間」だけを考えます。


で、マージソートにおいて分割した部分列を統合するのにかかる時間ですが、
たとえば、16の要素をマージソートする場合を例にあげると、

・要素数が1の部分列を要素数が2の部分列に統合する時の比較回数は1回です。要素数が2の部分列は全部で8個あるので、比較回数は8回。

・要素数が2の部分列を要素数が4の部分列に統合する時の比較回数は3回です。要素数が4の部分列は全部で4個あるので、比較回数は12回。

・要素数が4の部分列を要素数が8の部分列に統合する時の比較回数は7回です。要素数が8の部分列は全部で2個あるので、比較回数は14回。

・要素数が8の部分列を要素数が16の列に統合する時の比較回数は15回です。要素数が16の列は全部で1個あるので、比較回数は15回。

以上合計すると、比較回数8+12+14+15=49回で64要素のマージソートができるわけです。

この「比較回数」を「要素数n」の式で表現するわけですが、
個々の部分列の統合時の比較回数は、要素数n、分割数kとすると、n-k回になりますから、n=2^x (x = log n) とすると、
総比較回数=Σ(k=0~x-1) (n-2^k) = n x - n + 1 = n log n - n + 1
になります。

計算量(オーダー)の議論では、次数の低い項は無視しますから、
O(n log n - n + 1) = O(n log n) になります。

ソートの計算量を議論するときは、通常「比較回数」を考えます。

(正確には、全ての計算の手間を数えあげる必要がありますが、通常
・計算処理の中で「比較回数」が最も多くなる
・計算量(オーダー)では次数の低い項は無視できる
ので、比較回数以外は考える必要がなくなります)

ですので、マージソートの計算量を考える場合、「分割にかかる時間」ではなく、「(比較しながら行う)分割した部分列を統合していくのにかかる時間」だけを考えます。


で、マージソートにおいて分割した部分列を統合する...続きを読む

Q16進数から10進数への変換

16進数の77が16×14+7だということはわかるのですが、少し複雑になるとわからなくなります。
例えば以下のような場合です。

「16進数で5D2Cは
16の三乗×5+16の二乗×13+16×2+12
とあらわされます。」

なぜ、16の三乗や、16の二乗をする必要があるのでしょうか?

5桁になるとおそらく16の4乗をする必要がありそうですが、
宜しくお願いします。

Aベストアンサー

5桁で16の4乗、というのは正しいです。
この説明は下でされているので省きます。

16進数は数が大きいので、扱いが面倒、と思われるかもしれないので、
簡単な2進数への変換法を書いておきます。

16進数で5D2Cの場合
 1、各桁を2進数に変換する
 ⇒5D2C = 0101 | 1101 | 0010 | 1100
 2、変換したものをそのまま結合する
 ⇒ 0101 | 1101 | 0010 | 1100 ⇒  0101110100101100

 これで、2進数になります。
2のN乗の方が計算が楽だと思いますので、10進数にする場合は
使ってみてはいかがでしょうか?
(8進数の場合も同様にできます)

Qその日程で大丈夫!と取引先に返事したい

急いでます。宜しくお願いいたします。

取引先(お客様)からいただいた
打ち合わせ日時の案内メールに対して
「その日、その時間で大丈夫です。」と返事をしたいのですが
どうやって書いていいのかわからなくて困ってます。

不在の上司のかわりにメールをするので
ちゃんとした、失礼のない文面にしたいのですが・・・

どなたか教えてください。

Aベストアンサー

メール返信の形で、

ご連絡を誠に有難うございます。
下記承知いたしました。
それでは○月○日○時にお伺いさせて頂きます。

で良いのでは?


人気Q&Aランキング