La résolution de T(n) = 4T(n/2)+n2

Je suis en train d'essayer de résoudre un des récidives à l'aide de méthode de substitution. La relation de récurrence est:

T(n) = 4T(n/2)+n2

Ma conjecture est T(n) est Θ(nlogn) (et je suis sûr à ce sujet en raison de master théorème), et de trouver une limite supérieure, j'utilise l'induction. J'ai essayé de montrer que
T(n)<=cn2logn, mais cela ne fonctionne pas.

J'ai T(n)<=cn2logn+n2. Ensuite, j'ai essayé de montrer que, si T(n)<=c1n2logn-c2n2, il est également en O(n2logn), mais qui n'a pas fonctionné et j'ai T(n)<=c1n2log(n/2)-c2n2+n2`.

Comment puis-je résoudre cette récurrence?

  • Devrait probablement être sur cs.stackexchange.com.
  • Si vous êtes sûr de la solution en raison de master theorem, quel est le problème exactement? Maître théorème est suffisante (astuce: votre utilisation de maître théorème est faux)
  • j'ai besoin de le résoudre à l'aide de méthode de substitution à cause de mes devoirs question
InformationsquelleAutor yrazlik | 2013-03-03
  1. 6
    T(n) = 4T(n/2) + n2 
= n2 + 4[4T(n/4) + n2/4] 
= 2n2 + 16T(n/4) 
= ... 
= k⋅n2 + 4kT(n/2k) 
= ...

    Le processus s'arrête lorsque 2k atteint n.

    ⇒ k = log2n

    ⇒ T(n) = O(n2logn)

    InformationsquelleAutor SomeWittyUsername
  2. 4

    La résolution de T(n) = 4T(n/2)+n2

    Vous pouvez réécrire votre équation dans un non-récursive forme

    La résolution de T(n) = 4T(n/2)+n2

    Votre récursive équation est assez simple: à chaque fois que vous développez T(n/2) seulement un nouveau terme apparaît. Ainsi, dans le non-récursive formulaire, vous aurez une somme de termes quadratiques. Vous n'avez qu'à montrer que A(n) est log(n) (je vous laisse comme un exercice facile).

    InformationsquelleAutor Artem Sobolev