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

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

最初のものでは、n、lognなどの置換方法を使用します。すべてが私に間違った答えを与えました。
漸化式：根が定数になるので、適用できるかどうかわかりません。

誰か助けてもらえますか？

4

6 に答える 6

11

最初のものを見てみましょう。まず、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を掛けて、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メソッドを使用することについて正しいですが、漸化式が何を言っているかを知っていることが重要です。質問するのは、各ステップでどのくらいの作業を行うか、サイズの入力のステップ数はいくつnですか？

于 2010-10-18T04:40:58.457 に答える
11

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. log b a <cの場合、T（n）=Θ（n c）、
  2. log b a = cの場合、T（n）=Θ（n c log n）、
  3. log b a> cの場合、T（n）=Θ（nlog b a）。

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

この場合

a = b = 2;
log b a = 1; c = 0（n c = 1 => c = 0であるため）

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

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

m = log2nとします。

=> T（2 m）= T（2 m / 2）+0(1)

ここで、名前をK（m）= T（2 m）=> K（m）= K（m / 2）+に変更します。0(1)

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

于 2010-10-18T03:19:05.033 に答える
7

パート1では、@PrasoonSauravが提案したようにマスター定理を使用できます。

パート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) <= 12^k = log nk = log log nT(n) = k * O(1) = O(log log n)

于 2010-10-18T04:10:32.260 に答える
1

最初の繰り返し、T（n）= 2T（n / 2）+1を見てみましょう。ここではn/ 2が手がかりです。ネストされた各用語のパラメーターは、その親のパラメーターの半分です。したがって、n = 2 ^ kで開始すると、拡張にk個の項があり、基本ケースT（0）に達する前に、それぞれが合計に1を加算します。したがって、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））でなければならず、したがってT（n） = log_2（log_2（n））+1。

于 2010-10-18T04:02:09.597 に答える
0

漸化式と再帰関数も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であり、logが基数2であることを確認するのに少し時間がかかります。明らかに、これはO（log（log（n））の関係です。

于 2010-10-18T07:00:56.817 に答える
0

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

ただし、ここでは、置換方法を使用して解決するためのヒントを少し示します。

再発の場合は最初に置換 n = 2^k を試行します再発の場合は2番目に置換を試行します n = 2^2^k

于 2014-09-15T22:56:41.903 に答える