BSTで値を検索するときに、ノードを探している値と比較するたびにツリーの半分を残す方法がわかります。
しかし、なぜ時間計算量がO(log(n))
. だから、私の質問は:
N 要素のツリーがある場合、ツリーを調べて特定の値が存在するかどうかを確認する時間の複雑さが O(log(n)) になるのはなぜですか? どうすればそれを取得できますか?
BSTで値を検索するときに、ノードを探している値と比較するたびにツリーの半分を残す方法がわかります。
しかし、なぜ時間計算量がO(log(n))
. だから、私の質問は:
N 要素のツリーがある場合、ツリーを調べて特定の値が存在するかどうかを確認する時間の複雑さが O(log(n)) になるのはなぜですか? どうすればそれを取得できますか?
あなたの質問はここでよく答えられているようですが、あなたの特定の質問に関して要約すると、逆に考える方が良いかもしれません。「ノード数が増えると、BST ソリューション時間はどうなりますか」?
基本的に、BST では、ノードの数を 2 倍にするたびに、解決までのステップ数が 1 増えるだけです。これを拡張するために、ノードの 4 倍は 2 つの追加ステップを提供します。ノードの 8 回は、3 つの余分なステップを提供します。ノードが 16 回あると、さらに 4 つのステップが追加されます。等々。
これらのペアの最初の数の基数 2 の対数は、これらのペアの 2 番目の数です。これはバイナリ検索であるため、基数 2 のログです (各ステップで問題空間を半分にします)。
N 要素のツリーがある場合、ツリーを調べて特定の値が存在するかどうかを確認する時間の複雑さが O(log(n)) になるのはなぜですか? どうすればそれを取得できますか?
そうではありません。デフォルトでは、バイナリ サーチ ツリーのルックアップは ではありませんO(log(n))
。ここn
で、 はノードの数です。最悪の場合、 になってしまうこともありますO(n)
。たとえば、次のシーケンスの値をn, n - 1, ..., 1
(同じ順序で) 挿入すると、ツリーは次のように表されます。
n
/
n - 1
/
n - 2
/
...
1
1
値を持つノードのルックアップには、O(n)
時間の複雑さが伴います。
ルックアップをより効率的にするには、最大の高さが に比例するようにツリーのバランスlog(n)
を取る必要があります。このような場合、ルックアップの時間の複雑さはO(log(n))
、葉を見つけることが操作によって制限されるlog(n)
ためです。
しかし、繰り返しますが、すべての二分探索木が平衡二分探索木であるとは限りません。O(log(n))
時間の複雑さを保証するには、バランスを取る必要があります。