Discussion :

[zakuza]

Bonjour,

j'essaie de déterminer une borne supérieur asymptotique à l'aide d'un arbre récursif.

L'exercice se trouve dans le livre introduction à l'algorithmique 2eme édition chapitre 4 exercice 4.2.1.
Pour trouver un conjecture à partir de l'arbre je comprend la résolution, mais à partir du développement avec la méthode de substitution j'ai du mal à suivre.

L'arbre récursif donne comme borne supérieure O(n^log3)

Je ne comprend pas cette partie ci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Nous pouvons prouver ceci en supposant que T(n/2) <= cn/2^lg 3 − cn/2

d' ou vient le - c(n/2) qui sort de nulle part

Je me permet de mettre en lien un pdf reprenant la résolution de l'exercice.

4.2.1.pdf

Merci d'avance pour votre temps et votre aide.

[kolodz]

N'oublie pas les parenthèses dans ta citation :

Nous pouvons prouver ceci en supposant que T(n/2) <= c(n/2)^lg 3 − c(n/2)

Ce qui change les choses... Car cela implique que la personne à remplacer n par n/2 dans l'ensemble de sa supposition. Logiquement, cela revient à dire :

Nous pouvons prouver ceci en supposant que T(n) <= c(n)^lg 3 − c(n)

Mais, il fait l'utilisation de n/2, car cela lui permet de faire des simplification judicieuse de calcule. Pour le reste, il nous manque du contexte pour expliquer l'ensemble.

Cordialement,
Patrick Kolodziejczyk.

[zakuza]

Bonjour, je vous remercie pour votre réponse.

Si j'ai bien compris le résonnement ils prouvent que la conjecture T(n) = O(n^log3) ou T(n) <= c(n^log3), est correcte si elle l'est également pour T(n/2).

Ça devrait donc donner pour T(n) = 3T(n/2) + n : T(n) <= 3c(n^log3) + n.

Est non pas : T(n) <= 3c(n^log3) - c(n/2) + n

C'est la soustraction du c(n/2) que je ne comprend pas.

Pour le contexte si vous avez besoin d'autre information, je n'ai que l’énoncé de l'exercice et la résolution qui se trouve dans le PDF en pièce jointe. ( j’espère que personne ne se méfie de cette pièce jointe )