7

二分木レベルの順序トラバーサルの時間計算量は? O(n) ですか、それとも O(log n) ですか?

void levelorder(Node *n)
{    queue < Node * >q;
     q.enqueue(n);

     while(!q.empty())
      {
         Node * node = q.front();
         DoSmthwith node;
         q.dequeue();          
         if(node->left != NULL)
         q.enqueue(node->left);
         if (node->right != NULL)
         q.enqueue(node->right);
      }

}
4

3 に答える 3

7

O(n)、または正確にはTheta(n)。

ツリー内の各ノードを見てください-各ノードは最大で3回、少なくとも1回は「訪問」されます）-発見されたとき（すべてのノード）、左の息子から戻ってきたとき（葉以外）、そして来たとき右の息子（葉以外）から戻ってきたので、合計で最大3 * n回の訪問、少なくともノードごとにn回の訪問があります。各訪問はO(1)（キュープッシュ/ポップ）で、合計は-Theta(n)です。

于 2012-12-29T14:48:04.253 に答える
3

この問題に取り組むもう 1 つの方法は、レベル順トラバーサルがグラフの幅優先探索に非常に似ていることを特定することです。幅優先トラバーサルには、が頂点の数で、 がエッジの数でO(|V| + |E|)ある時間複雑性があります。|V||E|

ツリーでは、エッジの数は頂点の数とほぼ同じです。これにより、ノード数が全体的に線形になります。

于 2014-09-19T23:01:41.913 に答える
0

時間と空間の複雑さは O(n) です。n =いいえ。ノードの。

スペースの複雑さ - キューのサイズはノード数 O(n) に比例します

時間の複雑さ - 各ノードが 2 回訪問されるため、O(n)。エンキュー操作中に 1 回、デキュー操作中に 1 回。

これは BFS の特殊なケースです。BFS (幅優先検索) http://en.wikipedia.org/wiki/Breadth-first_searchについて読むことができます。

于 2012-12-29T15:24:17.543 に答える