Théorème maître non applicable?

11

Étant donné l'équation récursive suivante

T(n)=2T(n2)+nlogn
nous voulons appliquer le théorème maître et noter que

nlog2(2)=n.

Maintenant, nous vérifions les deux premiers cas pour ε>0 , c'est-à-dire si

  • nlognO(n1ε) ou
  • nlognΘ(n) .

Les deux cas ne sont pas satisfaits. Nous devons donc vérifier le troisième cas, qui est de savoir si

  • nlognΩ(n1+ε) .

Je pense que la troisième condition n'est pas remplie non plus. Mais pourquoi? Et quelle serait une bonne explication pour expliquer pourquoi le théorème maître ne peut pas être appliqué dans ce cas?

Joachim
la source
4
Le troisième cas n'est pas satisfait car n'est pas Ω ( n ϵ ) pour tout ϵ > 0 . Utiliser la règle de l'Hôpital sur le journal de limite nlognΩ(nϵ)ϵ>0lognnϵ
sdcvvc
1
Une fois que vous montrez qu'aucun des deux cas ne s'applique, c'est la preuve que vous ne pouvez pas appliquer le théorème maître comme indiqué.
Raphael
Qui a besoin du théorème maître? Utilisez des arbres de récursivité.
JeffE

Réponses:

7

Les trois cas du théorème maître auxquels vous faites référence sont prouvés dans l' introduction aux algorithmes par Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein (2e édition, 2001).

Il est correctement observé que la récurrence en question se situe entre le cas 2 et le cas 3. C'est-à-dire que croît plus vite que n mais plus lentement que n 1 + ε pour tout ε > 0 .f(n)=nlognnn1+εε>0

Cependant, le théorème peut être généralisé pour couvrir cette récurrence. Considérer

Cas 2A: Considérons pour certains k 0 .f(n)=Θ(nlogbalogbkn)k0

Ce cas se réduit au cas 2 lorsque . Il est intuitivement clair que le long de chaque branche de l'arbre de récurrence f ( x ) est ajouté Θ ( log b n ) fois. Un croquis d'une preuve plus formelle peut être trouvé ci-dessous. Le résultat final est quek=0f(x)Θ(logbn)

.

T(n)=Θ(nlogbalogbk+1n)

Dans l' introduction aux algorithmes, cette déclaration est laissée en exercice.

Applying this statement to the recurrence in question we finally get

T(n)=Θ(nlog2n).

More details on the Master Theorem can be found in the excellent (imho) Wikipedia page.

As @sdcvvc points in the comments to prove that Case 3 does not apply here one can invoke L'Hospital's rule that says that

limxcf(x)g(x)=limxcf(x)g(x)
for any functions f(x) and g(x) differentiable in the vicinity of c. Applying this to f(n)=nlogn and g(n)=n1+ε one can show that lognΘ(n1+ε).

Sketch of the Proof of the Master Theorem for Case 2A.

Il s'agit d'une reproduction de parties de la preuve d' Introduction aux algorithmes avec les modifications nécessaires .

Nous prouvons d'abord le lemme suivant.

Lemme A:

g(n)=j=0logbn1ajh(n/bj)
where h(n)=nlogbalogbkn. Then g(n)=nlogbalogbk+1n.

Proof: Substituting the h(n) into the expression for g(n) one can get

g(n)=nlogbalogbknj=0logbn1(ablogba)j=nlogbalogbk+1n.

QED

If n is an exact power of b given a recurrence

T(n)=aT(n/b)+f(n),T(1)=Θ(1)
one can rewrite it as
T(n)=Θ(nlogba)+j=0logbn1ajT(n/bj).
Substituting f(n) with Θ(nlogbalogbkn), moving Θ outside and applying Lemma A we get

T(n)=Θ(nlogbalogbk+1n).

Generalizing this to an arbitrary integer n that is not a power of b is beyond the scope of this post.

Dmitri Chubarov
la source
1

The Akra-Bazzi theorem is a strict generalization of the master theorem. As a bonus its proof is a blizzard of integrals that will make your head spin ;-)

In any case, Sedgewick in his "Introduction to the analysis of algorithms" argues convincingly that one should strive to prove T(n)g(n) type asymptotics.

vonbrand
la source