バイナリ検索ツリーでBig Oのログのベースは何ですか

Question

この表のように平均時間の複雑さについて議論するとき。

O（ログn）は

は、私はそれが2であると仮定しますが確認したかったんです。また、これらのデータ構造では常に2ですか？ O記法で

http://bigocheatsheet.com/

Answer 1

定数問題ではありません。たとえば、log2（n）とlog10（n）は定数でしか異なるので、O表記ではlog（n）のみが表示されます。

Answer 2

ローマのCortesはもう一方の答えを得ました。 aとbが1より大きい整数のときには、log_a(n) = Theta(log_b(n))を示すのは簡単だから、漸近的複雑さの問題です。

しかし、logがどこから来るのかを検討することはまだ有益だと思います。まずは、その動機づけに関連する数字と理解があります。

バイナリ検索ツリーは、値の検索を高速化するように構成されています。すべてのノードには、最大で2つのサブツリーがあり、左側のサブツリーのすべての値は、親の値よりも小さく、右側のサブツリーのすべての値は、親の値よりも大きくなります。バランスのとれたバイナリ検索ツリーを検索するとき（バランスがとれていることが重要です）、ターゲット値を検索する残りのノードの数を実質的に半分にする（または半分にするのに十分に近づける）ことができます。これは、実行時の再帰関係T(n) = T(n/2) + cを使用して表現できます。これは言う：

平衡二分探索木における検索操作の実行時には、左または右のいずれかを検索し、現在のノードの値（ c）を加えた時間にターゲットを比較するから定数項で与えられる

サブツリーですが、決して両方（T(n/2)）。 T(0) = aは、いくつかの定数aのために、我々はTのいくつかの値を書き出すことができますことを合理的に仮定し

：

n T(n) 
- ---- 
0 a 
1 T(1/2) + c = a + c 
2 T(2/2) + c = a + c + c = a + 2c 
4 T(4/2) + c = a + 2c + c = a + 3c 
8 T(8/2) + c = a + 3c + c = a + 4c 
... 
2^k T(2^k/2) + c = a + kc + c = a + (k+1)c 

k = log_2(n)をしてみましょう。その後、T(n) =T(2^k) = a + (k+1)c = a + (1 + log_2(n))cとなります。したがって、T(n) = O(log_2(n)) = O(log n)。ターゲットの下限は、現在のノードの下限値未満である場合、ターゲットが左サブツリーである

1. ：

   は、我々は値の範囲であり、次の規則が適用平衡三元ツリーを持っていたと仮定する。

2. ターゲットの上限が現在のノードの上限より大きい場合、ターゲットは右のサブツリーにあります。
3. ターゲットは、それ以外の場合は中間のサブツリーにあります。

だから、これはバランスの取れた三元検索ツリーかもしれません：あなたは二つの条件ではなく、いずれかをチェックし、むしろ1よりも、三つの可能なサブツリーのいずれかを選択除い

  (10,20) 
      | 
    +----------+----------+ 
    |   |   | 
(5,11) (11,15) (21,24) 
         | 
        (22,23) 

検索は、バイナリ検索のように働くかもしれません2つの可能性がある。再帰関係はT(n) = T(n/3) + c'となり、解はT(n) = a' + (1 + log_3(n))c' = O(log_3(n)) = O(log n)となる。