誰かがこの再発関係を解決するのを手伝うことができますか？ [閉まっている

Question

T(n) = 2T(n/2) + 0(1)

T(n) = T(sqrt(n)) + 0(1)

最初のものでは、n、lognなどの代替方法を使用します。すべてが私に間違った答えを与えました。
再発木：ルートが定数になるので、適用できるかどうかはわかりません。

誰かが助けることができますか？

Answer 1

最初のものを見てみましょう。まず、T（ベースケース）を知る必要があります。あなたはそれが定数であると述べましたが、あなたが問題をするとき、あなたはそれを書き留めることが重要です。通常、それはt（1）= 1のようなものです。私はそれを使用しますが、それが何であれ、一般化することができます。

次に、再発する回数（つまり、再帰ツリーの高さ）を見つけます。 n あなたの問題のサイズはありますか？それで、何回nを2で除算できますか？数学的に言えば、私はいつですか n/(2^i) = 1？それを理解し、後でそれを保持します。

次に、パターンに気付くまで、いくつかの置換を行います。

T(n) = 2(2(2T(n/2*2*2) + θ(1)) + θ(1)) + θ(1)

さて、パターンは、t（）を2回2回増やし、nを2回除算することです。何回？ i 時代。

T(n) = (2^i)*T(n/(2^i)) + ...

最後のBig-θ用語には、かわいいトリックを使用します。いくつかの置換がある場所では、t（）部分を無視してください。 θ用語の合計が必要です。彼らが加算することに注意してください (1 + 2 + 4 + ... + 2^i) * θ(1). 。閉じたフォームを見つけることができますか 1 + 2 + 4 + ... + 2^i？私はあなたにそれをあげます。これは (2^i - 1). 。ただ覚えておくのは良いものですが これがあなたがそれを理解する方法です.

とにかく、全体として私たちは得る

T(n) = (2^i) * T(n/(2^i)) + (2^i - 1) * θ(1)

あなたが解決した場合 i 以前、あなたはそれを知っています i = log_2(n). 。プラグインし、代数を実行すると、

T(n) = n*T(1) + (n - 1)*θ(1). T(1) = 1. 。それで T(n) = n + (n - 1)*θ(1). 。これはn倍の定数であり、定数とnです。低次の項と定数をドロップするので、θ（n）です。

Prasoon SauravはMaster Methodを使用することについて正しいですが、再発関係が何を言っているかを知っていることが重要です。尋ねるべきことは、各ステップでどれだけの仕事をするのか、サイズの入力のステップ数は何ですか n?

Answer 2

使用する Master Theorem そのような再発関係を解決するため。

させて a 1以上の整数になり、 b 1より大きい実数になります c ポジティブな実数になりましょう d 非陰性実数。フォームの再発が与えられた

• t（n）= a t（n/b） + n^c .. n> 1の場合

• t（n）= d .. n = 1の場合

次に、bのnaパワーのために、

1. ログの場合_b a <c、t（n）=θ（n^c),
2. ログの場合_b a = c、t（n）=θ（n^c log n）、
3. ログの場合_b a> c、t（n）=θ（n^{ログ_b a}).

1) T(n) = 2T(n/2) + 0(1)

この場合

a = b = 2;
ログ_b a = 1; c = 0（n以降^c = 1 => c = 0）

したがって、ケース（3）が適用されます。それで T(n) = Θ(n) :)

---

2) T(n) = T(sqrt(n)) + 0(1)

m = log₂ n;

=> t（2^m）= T（2^{m / 2} ) + 0(1)

次にK（M）= T（2の名前の変更^m）=> k（m）= k（m/2） + 0(1)

ケース（2）を適用します。

---

Answer 3

パート1の場合、@Prasoon Sauravが提案したように、Master Theoremを使用できます。

パート2の場合、再発を拡大するだけです。

T(n) = T(n ^ 1/2) + O(1)         // sqrt(n) = n ^ 1/2
     = T(n ^ 1/4) + O(1) + O(1)  // sqrt(sqrt(n)) = n ^ 1/4
     etc.

シリーズは続きます k 条件まで n ^ 1/(2^k) <= 1, 、すなわち 2^k = log n また k = log log n. 。それは与えます T(n) = k * O(1) = O(log log n).

Answer 4

最初の再発、t（n）= 2t（n/2） + 1を見てみましょう。n/2はここでの手がかりです。各ネストされた用語のパラメーターは親の半分です。したがって、n = 2^kから始めると、拡張にk用語があり、それぞれが合計に1を追加し、ベースケースt（0）を押す前に。したがって、t（0）= 1を想定すると、t（2^k）= k + 1と言うことができます。今、n = 2^kはk = log_2（n）が必要です。したがって、t（n）= log_2（n） + 1。

2回目の再発、t（n）= t（n^0.5） + 1に同じトリックを適用できます。n= 2^2^kで開始すると、拡張にk用語があり、それぞれが1を追加します。合計。 t（0）= 1を仮定すると、t（2^2^k）= k + 1が必要です。n= 2^2^kであるため、k = log_2（log_2（n））が必要です。 = log_2（log_2（n）） + 1。

Answer 5

再発関係と再帰関数も、F（1）から始めることで解決する必要があります。ケース1、t（1）= 1; t（2）= 3; t（4）= 7; t（8）= 15; t（n）= 2 * n -1であることは明らかです。これはo表記でo（n）です。
2番目のケースでは、t（1）= 1; t（2）= 2; t（4）= 3; t（16）= 4; t（256）= 5; t（256 * 256）= 6; t（n）= log（log（n）） + 1で、ログがベース2にあることを知るのに少し時間がかかります。明らかにこれはo（log（n））関係です。

Answer 6

ほとんどの場合、再発に対処する最良の方法は、再発ツリーを描き、ベースケースを慎重に処理することです。

ただし、ここでは、代替方法を使用して解決するためのわずかなヒントを提供します。

再発では、最初に代替を試してください n = 2^k再発では、2番目の試行代替を試します n = 2^2^k