Version imprimable
Bonjour,
je bloque sur une question très mathématique d'un livre bien connu d'algorithmie et j'aurais bien besoin de vos lumières.
Même en ayant trouvé la solution sur le net, je ne comprends pas.Citation:
Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence : formule
Je sais qu'un raisonnement par récurrence procède en deux étapes : l'initialisation puis l'héritage mais comment procéder ici ?
Merci d'avance.
pas "héritage", mais "hérédité". ;)Citation:
Envoyé par NiamorH
Je trouve les termes anglais plus pragmatiques :
initialisation -> "base"
hérédité -> "induction step"
Bref...
Base : (Est-ce que ca marche au départ ?)
On a T(2) = 2
et 2*Log2(2)= 2 * 1 =2
Bon, ca marche. :D
induction step : (si ca marche a un moment, est-ce que ca marche après).
- Hypothèse : T(n) = n*Log2(n)
- Suivant : T(2*n) = ?
T(2*n) = 2*T((2*n)/2)+(2*n) // par définition de la fonction T()
= 2*T(n)+2*n
= 2*n*Log2(n)+2*n // par hypothèse
= 2*n*(Log2(n)+1)
= 2*n*(Log2(n)+Log2(2)) // par définition du Log base2
= 2*n*(Log2(2*n)) // par propriété du Log
d'où, si T(n) = n*Log2(n) alors on a T(2*n) = (2*n)*(Log2(2*n))
base + induction => la formule est démontrée
Joli :)
Je comprends mieux la méthode, merci !