La résolution d'une récurrence T(n) = 2T(n/2) + n^4

Je suis étudiant à l'aide du MIT, de Didacticiels et de la CLR livre Introduction aux Algorithmes.

Je suis en train d'essayer de résoudre la récurrence (à partir de la page 107)

T(n) = 2T(n/2) + n4

Si je fais une récidive de l'arbre, j'obtiens:

Niveau 0: n4

Niveau 1 2(n/2)4

Niveau 2 4(n/4)4

Niveau 3 8(n/8)4

L'arbre a lg(n) niveaux. Par conséquent, je pense que la récidive doit être

T(n) = Θ(n4 lg n)

Mais, Si j'utilise le maître théorème, j'obtiens que

T(n) = Θ(n4)

À l'évidence, de ces ne peut pas être de droite. Laquelle est la bonne? Et où ai-je fait de mal avec mon raisonnement?

OriginalL'auteur huherto | 2011-01-05

  1. 6

    Le second semble correct. Notez que votre récurrence arbre ressemble

    n4 + 2(n/2)4 + 4(n/4)4 + ... + 2me (n /2me)4

    Mais 2(n/2)4 ≠ n4, parce que (n/2)4 = n4 /16, et donc 2(n/2)4 = n4/8. En fait, si vous faites le calcul, vous obtenez ce que le travail effectué au niveau i est donné par

    n4 /(2-3i)

    Nous obtenons donc (1 + 1/8 + 1/64 + 1/512 + ... ) n4, qui peut être montré à moins de 2n4. Si votre fonction est Θ(n4).

    ah oui, je vois mon erreur. Belle explication sur pourquoi il est inférieur à 2n^4. Merci

    OriginalL'auteur templatetypedef

  2. 2

    Avec la récursivité c'est en Θ(n^4)

    T(n) = 2*T(n/2) + n^4 
T(n) = 2( 2*T(n/4) + (n/2)^4) + n^4 = 4*T(n/4) + 2*(n/2)^4 + n^4
T(n) = 4(2*T(n/8) + (n/4)^4) + 2*(n/2)^4 + n^4 = 8*T(n/8) + 4*(n/4)^4 + 2(n/2)^4 + n^4

T(n) = 8*T(n/8) + n^4*(1 + 1/(2^3) + 1/(2^6))
...

T(n) = 2^k*T(n/(2^k)) + n^4*(1+ 1/(2^3) + 1/(2^6) + 1/(2^9)...+ 1/((2^(k-1))^3)

We know T(1) = 1

n = 2^k so k = log2(n) Then

T(n) = n*T(1) + n^4*( 1 - (1/(2^3))^k)/(1-1/8)

T(n) = n + (8/7)*n^4*(1 - n^(-3))

T(n) = n + (8/7)*(n^4 - n)

T(n) = (8/7)*n^4 - (1/7)*n


Θ(T(n)) = Θ((8/7)*n^4 - (1/7)*n)
Θ(T(n)) = Θ(n^4)

    il est Θ(n^4)

    OriginalL'auteur

  3. 1

    Vous pouvez utiliser le maître théorème ici directement.

    Cette équation s'intègre dans le cas 1 de maître théorème où log (a) base b < f( n)

    a : le Nombre de récidives
    b : Nombre de sous-parties

    log a base b = log 2 base 2 = 1 < n^4

    Donc par des maîtres théorème, T(n) = theta(f(n)) = theta(n^4)

    OriginalL'auteur CyprUS