再発を解決する方法t（n）。= T（N-1）+ T（N / 2）+ N？

Question

再帰ツリー方式で実行時間を取得するには、ツリーを描画して見つける必要があります。

a）木のレベル数。

木のサイズが1だけ減少するので、根からの最長の経路です。レベルIのサブ問題サイズはn-iです。 n - i= 1の設定1のサイズに当たると、レベル数i= n - 1。

b）木の中のコスト：cn

c）レベルI のノードの数：これは私が立ち往生しているところです。左側が1、右側の半分に減少するため、レベルIでノードを見つけることができません。当然のことながら、木は左側に向かってより高密度です。すべてのノードに2人の子供がいるわけではありません。

Cに回答を得ることができれば、T（n）=レベル0 +レベルのレベル1 +費用2 + ...レベルN-1のコストを計算できます。 Y1がレベル1のノード数1、レベル2のY2、ETC ...それから
=> t（n）= Cn + Y1 * Cn + Y2 * Cn + Y3 * Cn + .... yn - 1 * cnの総コストを得る。

誰かが私を撮るアプローチに私を導くことができますか？それが正しいか ？ 十分に大きいnであると仮定することができます、私たちはT（n / 2）を無視してから続行することができますか？ 。

オンライン検索は私を混乱させる。問題はCLRから4.4-5です。

この解決策は、t（n）= o（2 ^ n）およびt（n）=ω（n ^ 2）であり、どのようにして説明しない。

こちら

この解決策は、t（n）= o（n ^ 2）と言います。しかし、上記の解決策と矛盾する

Answer 1

$ s（n）= t（n） - 2n - 2 $ 。 $ s（n）= s（n-1）+ s（n / 2）$ （ $ n / 2 $ は整数である必要はありません。これは、addive $ n $ termが大きな違いを生じないことを示しています。

大 $ n $ の場合、roundly $ s（n） - s（n-1）\約S '（n）$ 、そして我々は微分方程式を解くために導かれる $$ s '（n）= s（n / 2）。 $$ $ f（n）=exp（\ tfrac {1} {2} \ log_2 ^ 2 n）$ を考慮してください。それから $$ f '（n）=exp（\ tfrac {1} {2} \ log_2 ^ 2 n）\ cdot \ frac {\ ln n} {（\ ln 4）n} $$ 一方 $$ f（n / 2）=exp（\ tfrac {1} {2}（\ log_2 n - 1）^ 2）\ \ exp（\ tfrac {1} {2} \ log ^ 2 n）\ exp（ - \ log n）=exp（\ tfrac {1} {2} \ log ^ 2 n）\ cdot \ frac {1} {n}。 $$ これは、少なくとも、 $ \ \ ln s（n）=theta（\ log ^ 2 n）$ です。

これはどこから来ましたか？ から行く方法の数として、 $ s（n）$ （適切な基本ケース！）を考えることができます。 2つの操作を適用することによって$ n $ をゼロにします。 2番目のタイプの、 $ \ theta（n）$ 操作のうち、非常に粗い推定値につながる $ \ binom {\ theta（n）} {\ log_2 n} $ は、 $ \ exp \ theta（\ log ^ 2 n）$ 。

---

具体性を考慮すると、 $ s（n）$ の以下の正確な定義が $ s（0 ）= 1 $ 、および $ n> 0 $ の場合は、 $$ S（N）= S（N-1）+ S（\ LFLOOR n / 2 \ rforoor）。 $$ これはシーケンス A000123 です。 ほぼ線形再発 $$ \ log_4 s（n）\ sim \ log_4 ^ 2 n、 $$ すなわち、2つの項の比率は $ n \ to \ infty $ として1になります。 OEISエントリにはさらに正確な漸近感が含まれています。

Answer 2

フィボナッチ催眠術に同意しないが、私は私の答えの100パーセントではありません

あなたは見ます $ t（n）= t（n-1）+ c * n= O（n ^ 2）$

$ t（n）= t（n / 2）+ c * n= O（n log n）$

しかし、uはur t（n）を簡単に追加して取得しません。

再帰の中で1つのレベルになると（uはツリーを描くことができます）

t（n）= t（n - 2）+ t（（n - 1）/ 2）+ t（n / 2-1）+ t（n / 4） + [N +（N-1）+（N-1）/ 2 +（N / 2-1）+ N / 4]

これを示すためにそれは単にそれだけではありません $ O（n ^ 2）$

完成させなければなりませんが、私は $ o（（n ^ 2）* log n）$ のどちらかを疑っています。 または $ O（（n ^ 2）* n ^ {log n}）= O（n ^ 3）$

{log nステップで崩壊するTERM N（1 + 1/2 + 1/4 + 1 / n）があります。}