Discussion :

[NiamorH]

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.

Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence : formule

Même en ayant trouvé la solution sur le net, je ne comprends pas.
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.

[pseudocode]

Je sais qu'un raisonnement par récurrence procède en deux étapes : l'initialisation puis l'héritage mais comment procéder ici ?

pas "héritage", mais "hérédité".

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.

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

[NiamorH]

Joli
Je comprends mieux la méthode, merci !