ツリートラバーサルの時間の複雑さはどのくらいですか？

ツリートラバーサルの時間の複雑さは何ですか、私はそれが明らかでなければならないと確信していますが、私の貧弱な脳はすぐにそれを動作させることはできません。ツリートラバーサルの時間の複雑さはどのくらいですか？

2011-02-10 new299

プログラミングの第1巻のページ326 – new299

Knuthのコンピュータプログラミングの技術ですか？私は友人に良い例を与えるためにこれを見つけようとしています。 – Nicholas

はいKnuthの "The Art of Computer Programming" – new299

実行しているトラバーサルの種類とアルゴリズムによって異なりますが、通常はO（n）となります。ここで、nはツリー内のノードの総数です。深度最初のトラバーサルの標準的な再帰的実装では、（スタック上の）メモリを最も深いレベルの順に消費します。バランスの取れたツリーではlog（n）になります。

2011-02-10 11:20:33 Uri

これはn-aryツリーに当てはまりますか？私は最大深度4の木であるデータ構造を持ち、友人が3つのforループを使用していて、そのアルゴリズムが 'O（n^3）'時間で実行されていると言いますが、 '' n時間、 'n'はツリー内のノードの総数になります – Nicholas

@Nocholas、あなたは正しいですし、あなたの友人は間違っています。それはO（n）です。 – Uri

そうではないでしょうかnのノードを持つツリーの場合、nとなりますか？

あなたはそれぞれのツリーを訪れます。一度離れるでしょうか？だから私はそれが線形だと言うだろう。

2011-02-10 11:18:28 Nanne

"nノード"ではなく "n leaves"でツリーにする必要があります。 – aamadmi

あなたは間違ったterminoligyです： – Nanne

@Nanne正しいアルゴリズムでは、実際には時間的に線形の複雑さです（各ノードを1回訪れています）が、まだ空間的に線形の複雑さはありません。スタックを使うのと同じです。 – Tim

答えて