次のコードの時間複雑さがなぜO（n^2）になるのですか？

Question

void level_order_recursive(struct node *t , int h) //'h' is height of my binary tree 
{             //'t' is address of root node 
    for(int i = 0 ; i <= h ; i++) 
    { 
     print_level(t , i); 
    } 
} 

print_level（）が毎回呼び出された後、再帰関数は（2^i）回呼び出されたと思います。したがって、2^0 + 2^1 + 2^2 ... 2^hは時間の複雑さをO（2^n）に与えるはずです。どこが間違っていますか？時間計算量はO（N^2）となるが、各レベルの時間複雑度（n）は> O BE- + O（N-1れるように、2^Nすることができない最悪の場合

void print_level(struct node * t , int i) 
{ 
    if(i == 0) 
     cout << t -> data <<" "; 
    else 
     { 
      if(t -> left != NULL) 
       print_level(t -> left , i - 1); //recursive call 
      if(t -> right != NULL) 
       print_level(t -> right , i - 1); //recursive call 
     } 
} 

Answer 1

tのツリーのルートから常に始まり、ツリーの高さに達するまで、レベルに達するまで、レベルを1ずつ増やします（i）。

あなたはバイナリツリーだと言っていますが、あなたは何のプロパティも言及していませんでした。バランスのとれたものです。だから、私はそれが不均衡な二分木であると仮定し、最悪の場合のツリーの高さはh = nになることができます。nはノードの数です（実際にはリストのように完全に不均衡なツリーです）。

これは、level_order_recursive回のループn回を意味します。私。最悪の場合、ツリーにはnレベルがあります。

print_levelは、印刷するルートノードとレベルを受け取ります。そしてそれはレベルに達するまで再帰的にと呼ばれ、そのレベルを出力します。
I. it ループi回（再帰呼び出しは毎回1回ずつiを減らします）。

だから、あなたは1 + 2 + 3 + ... + h回の反復を持っています。 h = n以降、1 + 2 + 3 ... + n歩になります。これは(n * (n+1))/2（ガウス和式）です。これはO(n^2)です。

あなたは最悪のシナリオを改善するよりも高さがLDはバイナリ対数を表しh = ld(n)になるので、あなたが、木がバランスしていることを保証することができた場合

。

Answer 2

）+ O（n-2）+ ... + O（1）である。

Answer 3

あなたはhとnを混同しています。 hは木の高さです。 nは明らかにツリー内の要素の数です。 print_levelは最悪の場合O（$ 2^i）ですが、これもちょうどnです。

縮退したツリーがあると、最悪のケースが発生します。各ノードには1つの後継ノードしかありません。その場合、ノードはn個ありますが、ツリーの高さもh = nです。 print_levelを呼び出すたびにiのステップを実行し、iを1からh = nまで合計​​すると、O（$ n^2）となります。

Answer 4

thisまたはthat（3および4ページ）に基づいて、私たちの場合に似ているバイナリ検索アルゴリズムは、T(n) = T(n/2) + cの時間複雑さを持ちます。 それ以外の場合、左右のサブツリーはブラウズされるため、以下の式の2T（n/2）は探索アルゴリズムではなくトラバーサルアルゴリズムであるためです。

ここでは、質問に従い、「n」の代わりに「h」を使用します。あなたはここに印刷されている "データ" とは何