2

マスター メソッド - T(n) = 4*T(n/2) + (n^2)/logn を解けないのはなぜですか?

タイプ T(n) = aT(n/b) + f(n) の繰り返しを解決できることを認識しています

MIT OCW では、上記の再発は解決できないと述べています。誰かが理由について説明できますか?

4

4 に答える 4

2

T(n/2) + (n^2)/logn の答え:

Case 1 does not apply because f(n) != O(n^-e) for any positive e.

Case 2 does not apply because f(n) != Θ(log^k(n)) for any k >= 0

Case 3 does not apply,
    f(n) = Ω(n^e) for e = 1, BUT
    a*f(n/b) <= c*f(n) for no c<1 (works out that c >= 2)

したがって、どのケースにも適用できません。これを超えて、私は本当に良くありません-そして、私はこの答えに100％ではありません.

以下はこの編集前のものであり、質問が T(n) = T(n/2) + n^(2logn) に関するものであると仮定しました。これは定理のケース 3 であると確信しています。

Case 1 does not apply because f(n) != O(n^-e) for any positive e.

Case 2 does not apply because f(n) != Θ(log^k(n)) for any k >= 0

Case 3 does apply,
    a*f(n/b) <= c*f(n) for some c<1 (works out that c >= 0.5)
    and f(n) = Ω(n^e) for e = 1

間違っているかもしれないので、確認して教えてください！

于 2012-05-20T21:15:24.393 に答える
0

f(n)=(n^2)/logn および n^(log a/log b) . 上記の 2 つの関数の差を計算します。

比率= (n^2/log n)/(n^2)

比率は対数になります。この再帰関係は、ケース 2 とケース 3 の間のギャップに該当します。したがって、マスターの定理は、この再帰関係には適用されません。

マスターの定理は、上記の 2 つの関数の差が多項式の場合に適用できます。

于 2015-01-20T17:31:52.413 に答える
0

これは、前述の 3 つのケースすべてで、正の漸近的性質を正当化できないためです。これは、n->無限大 n^2/lg(n) -> 無限大の場合を意味し、単に n^e = w(lg(n)) を意味します。これは、「関数を含めることができない」と言い換えることができます 上限なし分割と征服の手順のために存在します。

于 2016-08-28T02:02:41.437 に答える