23

二分探索アルゴリズムは、(n 個のノードを持つ) ツリーの高さが log(n) になるため、log(n) 時間かかります。

これをどのように証明しますか？

4

4 に答える 4

30

ここで、私は数学的な証明をしていません。2を底とする log を使用して問題を理解してください。log 2は、コンピュータ サイエンスにおける log の通常の意味です。

まず、2 進対数 (log 2 n) (2 を底とする対数) であることを理解します。例えば、

  • 1 の 2 進対数は 0 です
  • 2 の 2 進対数は 1 です
  • 3 の 2 進対数は 1 です
  • 4 の 2 進対数は 2 です
  • 5、6、7 の二値対数は 2
  • 8-15 の 2 進対数は 3 です
  • 16-31 の 2 進対数は 4 などです。

高さごとに、完全にバランスの取れたツリーのノード数は次のとおりです。

    高さ ノード ログの計算
      0 1 ログ2 1 = 0
      1 3 ログ2 3 = 1
      2 7 ログ2 7 = 2
      3 15 ログ2 15 = 3

8 ～ 15 個のノード (任意の数、たとえば 10 個) を持つバランスのとれたツリーを考えてみましょう。8 から 15 までの任意の数のlog 2は 3 であるため、常に高さ 3 になります。

バランスの取れた二分木では、解決する問題のサイズは反復ごとに半分になります。したがって、サイズ 1 の問題を取得するには、おおよそ log 2 n 回の反復が必要です。

これが役立つことを願っています。

于 2013-12-21T06:15:04.167 に答える
11

最初に、ツリーが完全であると仮定しましょう - 2^N 個の葉ノードがあります。二分探索には N 回の再帰ステップが必要であることを証明しようとします。

各再帰ステップで、候補の葉ノードの数を正確に半分に減らします (ツリーが完成しているため)。これは、N 回の半減操作の後、候補ノードが 1 つだけ残ることを意味します。

二分探索アルゴリズムの各再帰ステップは正確に 1 つの高さレベルに対応するため、高さは正確に N です。

すべてのバランスの取れたバイナリ ツリーへの一般化: ツリーのノード数が 2^N 未満の場合、それ以上半分にする必要はありません。必要な量は同じでも少なくてもかまいませんが、それ以上は必要ありません。

于 2013-01-26T17:50:32.237 に答える
8

作業する完全なツリーがあると仮定すると、深さ k には 2 k 個のノードがあると言えます。これは、単純な帰納法を使用して証明できます。これは、ツリーにレベルを追加すると、ツリー全体のノード数が前のレベルのノード数の 2 倍だけ増えるという直感に基づいています。

木の高さ k は log(N) です。ここで、N はノードの数です。これは次のように言えます。

log 2 (N) = k、

そしてそれはと同等です

N = 2k

これを理解するために、以下に例を示します。

16 = 2 4 => ログ2 (16) = 4

木の高さと節の数は指数関数的に関係しています。ノード数のログを取ると、逆方向に作業して高さを見つけることができます。

于 2015-09-23T02:21:20.830 に答える
0

Knuth、Volume 3-Searching and Sorting Algorithmsで厳密な証明を調べてください...彼は、私が考えることができる他の誰よりもはるかに厳密にそれを行っています。

http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming

優れたコンピュータサイエンスライブラリや、多くの（非常に）古いオタクの本棚で見つけることができます。

于 2013-01-26T16:54:53.160 に答える