コンピュータサイエンスのアルゴリズムを理解するのは初めてです。二分探索のプロセスは理解していますが、その効率について少し誤解しています。
$ s = 2 ^ n $要素のサイズでは、平均して$ n $かかります。特定の要素を見つけるための手順。両側の2を底とする対数を取ると、$ \ log_2（s）= n $になります。では、二分探索アルゴリズムの平均ステップ数は$ \ log_2（s）$ではないでしょうか？
このWikipediaの記事二分探索アルゴリズムによると、平均パフォーマンスは$ O（\ log n）$です。これはなぜですか？なぜこの数値は$ \ log_2（n）$ではないのですか？
コメント
- SOで複製- Big O（logn）ログベースはeですか？
回答
対数の底を変更すると、結果の式は定数係数のみが異なり、 Big-O表記の定義は、両方の関数がその漸近的振る舞いに関して同じクラスに属していることを意味します。
たとえば、$$ \ log_ {10} n = \ frac {\ log_ {2} n} {\ log_ {2} 10} = C \ log_ {2} {n} $$ここで、$ C = \ frac {1} {\ log_ {2} 10} $。
したがって、$ \ log_ {10} n $と$ \ log_ {2} n $は定数$ C $だけ異なるため、両方とも真になります。$$ \ log_ {10} n \ text {is} O （\ log_ {2} n）$$ $$ \ log_ {2} n \ text {は} O（\ log_ {10} n）$$一般に、$ \ log_ {a} {n} $は、正の整数$ a $および$ b $が1より大きい場合は$ O（\ log_ {b} {n}）$です。
対数関数のもう1つの興味深い事実は、定数$ k > 1 $の場合、$ n ^ k $は$ O（n）$ではなく、$ \であるということです。 log {n ^ k} $は$ O（\ log {n}）$です。これは、$ \ log {n ^ k} = k \ log {n} $であり、$ \ log {n} $と定数係数$だけが異なるためです。 k $。
コメント
- 正の整数だけでなく：すべての実数$ a、b > 1 $、例： $ e $。
- これが、big-O表記では、対数の底が一般的に指定されていない理由であると付け加えます。また、$ O（\ log n）$が使用するベースについて混乱がないことも意味します。違いがないため、一般的に使用されるベースのいずれでもかまいません。'
回答
fade2blackの回答（完全に正しい）に加えて、注目に値します。 「$ \ log（n）$」という表記があいまいであること。基数は実際には指定されておらず、デフォルトの基数はコンテキストに基づいて変更されます。純粋数学では、基数はほとんどの場合$ e $と見なされますが（指定されていない場合）、特定の工学コンテキストでは10になる場合があります。 、ベース2は非常にユビキタスであるため、$ \ log $はベース2であると見なされることがよくあります。そのウィキペディアの記事では、ベースについて何も述べられていません。
しかし、すでに示したように、この場合はそうではありません。 ”
コメント
- " logの場合は、さらに注目に値します。 （n）"は" O（log（n））"とあいまいな場合がありますどちらのベースを考えていても、後者の意味が1つしかないからではありません。