108

二分探索木タイプのデータ構造の場合、Big O表記は通常O（logn）と表記されます。ログに小文字の「l」がある場合、これは自然対数で表される対数基数e（n）を意味しますか？簡単な質問で申し訳ありませんが、私は常に異なる暗黙の対数を区別するのに苦労していました。

4

7 に答える 7

85

Big O表記は、対数ベースの影響を受けません。これは、異なるベースのすべての対数が定数係数で関連付けられているため、はとO(ln n)同等であるためO(log n)です。

ここに画像の説明を入力してください

于 2009-10-15T00:31:38.287 に答える
84

big-O（）表記で表現すると、どちらも正しいです。ただし、O（）多項式の導出中、二分探索の場合、log2のみが正しいです。この区別は、最初にあなたの質問の直感的なインスピレーションだったと思います。

また、私の意見では、O（log 2 N）と書く方が、アルゴリズムの実行時の導出をより適切に伝達するため、例として適しています。

big-O（）表記では、定数係数が削除されます。ある対数ベースから別の対数ベースへの変換には、定数係数の乗算が含まれます。

したがって、O（log N）は、一定の係数によりO（log 2 N）と同等です。

ただし、回答にlog 2 Nを簡単に植字できる場合は、より教育的です。二分木検索の場合、big-O（）ランタイムの導出中にlog2Nが導入されるの は正しいことです。

結果をbig-O（）表記として表現する前に、違いは非常に重要です。big-O表記を介して伝達される多項式を導出する場合、この例では、O（）表記を適用する前にlog2N以外の対数を使用することは正しくありません。多項式がbig-O（）表記を介してワーストケースのランタイムを通信するために使用されるとすぐに、どの対数が使用されるかは重要ではありません。

于 2009-10-15T00:32:40.370 に答える
10

どちらも正しいです。これについて考えます

log2(n)=log(n)/log(2)=O(log(n))
log10(n)=log(n)/log(10)=O(log(n))
logE(n)=log(n)/log(E)=O(log(n))
于 2010-05-27T14:22:03.667 に答える
9

big-O表記は通常、漸近的に最も高い次数のみを示すように記述されるため、それがどのベースであるかは実際には重要ではありませんn。したがって、定数係数は失われます。異なる対数ベースは一定の係数に相当するため、不要です。

そうは言っても、おそらく対数ベース2を想定します。

于 2009-10-15T00:31:23.180 に答える
3

はい、big-O表記について話すとき、ベースは重要ではありません。ただし、実際の検索問題に直面した場合、計算上は重要です。

ツリー構造についての直感を開発する場合、バイナリ検索ツリーはツリーの高さであるため、O（n log n）時間で検索できることを理解しておくと役立ちます。つまり、nノードのバイナリツリーでは、ツリーです。深さはO（n log n）（ベース2）です。各ノードに3つの子がある場合でも、ツリーはO（n log n）時間で検索できますが、底は3の対数です。計算上、各ノードの子の数はパフォーマンスに大きな影響を与える可能性があります（例：リンクテキストを参照） 。

楽しみ！

ポール

于 2009-10-15T06:06:49.413 に答える
3

まず、関数f（n）がO（g（n））であるとはどういう意味かを理解する必要があります。

正式な定義は次のとおりです。*関数f（n）は、| f（n）|の場合、O（g（n））と呼ばれます。<= C * | g（n）| n> kの場合は常に、Cとkは定数です。*

したがって、f（n）= nの対数基数a（a> 1）およびg（n）= nの対数基数b（b> 1）とします。

注：これは、値aとbが1より大きい任意の値になる可能性があることを意味します。たとえば、a=100とb=3

ここで、次のようになります。nの対数基数aはO（nの対数基数b）であると言われます。<= C *|nの対数b| n>kのときはいつでも

k = 0を選択し、C=bの対数基数aを選択します。

これで、方程式は次のようになります。 |nのログベースa| <=bの対数基数a*|nの対数基数b| n>0のときはいつでも

右辺に注目してください。次の方程式を操作できます。=bの対数基数a*|nの対数基数b| =|nの対数ベースb| *bの対数基数a=| b ^の対数基数a（nの対数基数b）| =|nのログベースa|

これで、方程式は次のようになります。 |nのログベースa| <=|ログベースaofn | n>0のときはいつでも

制限a、b>1およびn>0を除いて、値n、b、またはaが何であっても、方程式は常に真です。したがって、nの対数基数aはO（nの対数基数b）であり、a、bは重要ではないため、単純に省略できます。

ここでYouTubeビデオを見ることができます：https ：//www.youtube.com/watch？v = MY-VCrQCaVw

ここでそれに関する記事を読むことができます：https ：//medium.com/@randerson112358/omitting-bases-in-logs-in-big-o-a619a46740ca

于 2018-04-07T14:30:41.030 に答える
1

技術的にはベースは重要ではありませんが、一般的にはベース2と考えることができます。

于 2009-10-15T00:31:06.627 に答える