Résolution de T (n) = 2T (n / 2) + log n avec la méthode de l'arbre de récurrence

9

Je résolvais des relations de récurrence. La première relation de récurrence était

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

La solution de celui-ci peut être trouvée par le théorème maître ou la méthode de l'arbre de récurrence. L'arbre de récurrence serait quelque chose comme ceci:

! [entrez la description de l'image ici

La solution serait:

T(n)=n+n+n+...+nJournal2n=k fois=Θ(nJournaln)

Ensuite, j'ai rencontré le problème suivant:

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

Mon livre montre que par le théorème maître ou même par une approche de substitution, cette récurrence a la solution . Il a la même structure que l'arborescence ci-dessus, à la seule différence qu'il effectue à chaque appel un travail . Cependant, je ne suis pas en mesure d'utiliser la même approche ci-dessus pour ce problème.Θ(n)Journaln

anir
la source

Réponses:

5

Le terme non récursif de la relation de récurrence est le travail de fusion de solutions de sous-problèmes. Le niveauk de votre arbre de récurrence (binaire) contient 2k sous-problèmes avec taille n2k, vous devez donc d'abord trouver le travail total au niveau k puis de résumer ce travail sur tous les niveaux d'arbre.

Par exemple, si le travail est constant C, puis le travail total au niveau k sera 2kCet le temps total T(n) sera donnée par la somme suivante:

T(n)=k=1Journal2n2kC=C(2Journal2n+1-2)=Θ(n)

Cependant, si le travail augmente logarithmiquement avec la taille du problème, vous devrez calculer avec précision la solution. La série serait la suivante:

T(n)=Journal2n+2Journal2(n2)+4Journal2(n4)+8Journal2(n8)+....Journal2n fois

Ce sera une somme assez complexe:

T(n)=Journal2n+k=1Journal2n2kJournal2(n2k)

Je dénote temporairement m=Journal2n et simplifiez la sommation ci-dessus:

k=1m2kJournal2(n2k)==k=1m2k(Journal2n-k)==Journal2nk=1m2k-k=1mk2k==Journal2n(2m+1-2)-(m2m+1-2m+1+2)

Ici, j'ai utilisé une formule pour le k=1mk2ksomme du calculateur d'algèbre symbolique en ligne Wolfram | Alpha . Ensuite, nous devons remplacerm de retour par Journal2n:

T(n)=Journal2n+2nJournal2n-2Journal2n-2nJournal2n+2n-2
=2n-Journal2n-2=Θ(n)

QED

HEKTO
la source
1
putain j'ai fait une erreur super stupide en posant une question. Maintenant corrigé. Cependant, je ne peux pas maintenant savoir comment les choses s'annulent dans la série:20Journal2n20+21Journal2n21+22Journal2n22+...+2Journal2nJournal2n2Journal2n=Journal2n+2Journal2n2+4Journal2n4+...+nJournal21.. C'est la série que vous proposez, non? Essayer avecn=8, J'ai eu Journal28+2Journal24+4Journal22+8Journal21=3+4+4=11. Qu'est-ce qui ne va pas ici?
anir
@anir - Utiliser l'égalité Journal2(n2k)=Journal2n-k
HEKTO
1
Je ne sais toujours pas comment cette série s'effondre Θ(n) : '¬ (Math-noob-here ...
anir
@anir - Je vais développer ma réponse
HEKTO
@HEKTO Si vous résolvez l'équation de commentaire ci-dessus, vous obtenez toujours nlog (n) ?? J'ai beaucoup essayé. pourriez-vous m'aider ici?
roottraveller