反復関係から再帰ツリーの高さを決定する方法は？

Question

繰り返し実行時間を扱うときに構築される再帰ツリーの高さを決定するにはどうすればよいですか？普通の木の高さを決定するのとどのように違いますか？

alt text http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/ch4-9.gif

編集：申し訳ありませんが、私は漸化式から再帰木の高さを取得する方法を追加することを意味しました。

Answer 1

再帰ツリーの高さは、問題の再帰アルゴリズムによって異なります。すべてのツリー構造が均一な高さを持つわけではないので、すべての分割アルゴリズムと征服アルゴリズムが高さツリーを統一しているわけではありません。アルゴリズムの可能な最大高さを決定できない場合、または実行時にツリーの実際の高さを計算する必要がある場合は、再帰関数にグローバル変数を使用し、関数への入力時に変数をインクリメントし、それは関数の終了時に。この変数は、再帰的プロシージャの現在のレベルを示します。必要に応じて、この変数の最大値を2番目の変数に保持することができます。

Answer 2

まず、これが宿題に関する質問であれば、そのようにマークしてください。あなたがリンクしている画像は、あなたがCS 455にいることを暗示しています。 :)

主なヒントは次のとおりです。ツリーの高さは、「葉」に到達したときに明らかに決定されます。関数の反復関係をモデル化した木の葉が基本ケースです。したがって、私は、Nがどのようにしてベースケースに「迅速に」縮小できるかを見ることに目を向けるだろう。

Answer 3

再帰がT（n）= aT（n/b）+ f（n）の形である場合、ツリーの深さはnのログベースbです。

たとえば、2T（n/2）+ n回の再帰は深さlg（n）（nのログベース2）のツリーを持ちます。