過去ログ
No．１０７８ O(log(2)n)とO(logn)の間の関係
[戻る] [ホームページ]No.14142 |
計算量 投稿者---シバケン(2004/05/22 00:01:43) |
||
アルゴリズムの時間複雑度O(p(n))についてお聞きします。 一般に O(logn)<O(n) が成り立つと思いますが O(logn)の底が異なるもの、 例えば、底が２のO(log(2)n) と 底がeのO(logn) を 考えると、 O(log(2)n)とO(logn)の間には、等号、不等号、いずれの関係が成り立つのでしょうか。 よろしくお願いします。 |
|||
| No.14144 |
Re:計算量 投稿者---ぽこ(2004/05/22 00:15:43) |
||
>O(log(2)n)とO(logn)の間には、等号、不等号、いずれの関係が成り立つのでしょうか。 ネピア数eの値は2<e<3です。 |
|||
| No.14145 |
Re:計算量 投稿者---シバケン(2004/05/22 00:24:09) |
||
ぽこさん、ありがとうございます。 さらに、お聞きしたいのですが、 先ほどのことを一般化すると O(logn)において、底が大きくなれば、O(logn)の値は小さくなると考えてもよろしいでしょうか。 例えば、O(log(2)n) > O(logn) > O(log(10)n) でよろしいでしょうか？ |
|||
| No.14147 |
Re:計算量 投稿者---ぽこ(2004/05/22 00:35:14) |
||
>先ほどのことを一般化すると >O(logn)において、底が大きくなれば、O(logn)の値は小さくなると考えてもよろしいでしょうか。 >例えば、O(log(2)n) > O(logn) > O(log(10)n) >でよろしいでしょうか？ 底の変換公式から考えましょう。 aを底とする対数をbを底とする対数に変換する場合は、以下の公式で変換します。 log(a)X = log(b)X/log(b)a a=2とすると log(2)X = log(b)X/log(b)2 移項して、 log(b)2*log(2)X = log(b)X log(2)X > log(b)Xが成り立とき、0<log(b)2<1が成り立つ。 これより、 b>2の場合、log(2)X > log(b)X 0<b<2の場合、log(2)X < log(b)X |
|||
| No.14146 |
Re:計算量 投稿者---ぽこ(2004/05/22 00:26:34) |
||
>O(log(2)n)とO(logn)の間には、等号、不等号、いずれの関係が成り立つのでしょうか。 素朴な疑問なんですが、logオーダーの計算量を論じるときに、 底が2以外を取るアルゴリズムってどのようなものでしょうか? |
|||
| No.14148 |
Re:計算量 投稿者---シバケン(2004/05/22 00:37:50) |
||
すいません。 そこまで、考えておりません。 単に底の変化に応じて、logオーダーが どのように振舞うかを考えていただけで、実際に どのようなアルゴリズムがあるかは考えておりません。 |
|||
| No.14152 |
Re:計算量 投稿者---NykR(2004/05/22 05:42:18) |
||
>単に底の変化に応じて、logオーダーが >どのように振舞うかを考えていただけで、 底はぽこさんの示した変換式で変換できますから「底の変化に応じて」logオーダーの振る舞いが変わることはありません。 O(log_2(n))のアルゴリズムは同時に O(log_1000(n))のアルゴリズムでもあります。 |
|||
| No.14160 |
Re:計算量 投稿者---シバケン(2004/05/22 18:11:40) |
||
NykRさん、レスありがとうございました。 |
|||