performance - 時間計算量、二分（検索）ツリー

Question

特定の深さdまでの完全な二分木があると仮定します。このツリーをトラバース（プレオーダートラバーサル）するのにかかる時間計算量はどれくらいですか。

ツリー内のノードの数が2^dであることがわかっているため、混乱しています。したがって、時間計算量はどうなるでしょうBigO(2^d)か。木が指数関数的に成長しているからです。

しかし、インターネットで調査したBigO(n)ところ、トラバーサルとは、nが要素の数（2^dこの場合は）でありBigO(2^d)、何が欠けているのかではないと誰もが述べています。

ありがとう

score 3 · Accepted Answer

nはノードの数として定義されます。

2 ^ dは、その深さで可能なすべてのノードがいっぱいになったときのノードの数のみです

すなわち。

     o
   /   \
  o     o
 / \   
o   o

2 ^ dが8の場合、ノードは5つだけです。

完全な二分木では、最後の行を除いてすべてのノードが埋められ、すべてのノードが左側に埋められます。あなたはウィキペディアで定義を見つけることができます

score 0 · Accepted Answer

時間計算量をO（2 ^ d）として表現できたとしても、他のコレクションの時間計算量と比較するために使用できるものではないため、これはかなり役に立ちません。

一方、時間計算量をO（n）として表すことは非常に便利です。コレクションがどのように実装されているかを正確に知る必要なしに、アイテムの数を増やしたときにコレクションがどのように反応するかを正確に示し、他のコレクションの時間計算量と比較できます。

2 に答える 2