Discussion :

[rvfranck]

Salut,

En relisant mon cours sur les techniques de démonstration je me suis rendu compte qu'on aurait pu utiliser l'induction mathématique généralisée.

je rappelle que la recurrence était

Code :

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

1
2
3
4
 
T(n) = T(n/2 + racine(n)) + n  (avec n > 16)
et que T(n) = constante sinon
et qu'il fallait demontrer que T(n) = O(n) pour tout n >= 0

base de l'induction:

Code :

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

1
2
3
4
5
 
pour n = 0, T(0) = O(0) qui est bien une constante
pour n = 1, T(1) = O(1) qui est bien une constante
.
pour n = 16, T(16) = O(16) qui est bien une constante

donc pour n de [0 à 16], T(n) = O(n) = constante

Hypothèse d'induction: pour tout n > 16, T(n/2 + racine(n)) = O(n/2 + racine(n))

Code :

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

1
2
3
4
5
6
 
on a donc: T(n/2 + racine(n)) <= c(n/2 + racine(n)) ( c > 0)
T(n/2 + racine(n)) <= (cn)/2 + c*racine(n)
T(n/2 + racine(n)) + n <= (cn)/2 + c*racine(n) + n
T(n) <= (cn)/2 + c*racine(n) + n
T(n) <= cn pour tout c > 0

donc T(n) = O(n) pour n > 16

T(n) = O(n) pour n<=16 et T(n) = O(n) pour n > 16
=> T(n) = O(n) pour tout n

[millie]

T'as montré que T(n) est en O(n), mais rien sur sa complexité.

La fonction suivante :

Code :

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

1
2
3
4
 
T : n =
 si n = 0 retourner 0
 sinon retourner T(n-1)

Sa complexité est en O(n) mais la fonction est nulle

[pseudocode]

Hypothèse d'induction:
pour tout n > 16, T(n/2 + racine(n)) = O(n/2 + racine(n))
(...)
donc T(n) = O(n) pour n > 16

y a comme un truc qui me chiffonne...

[rvfranck]

T'as montré que T(n) est en O(n), mais rien sur sa complexité.

La fonction suivante :

Code :

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

1
2
3
4
 
T : n =
 si n = 0 retourner 0
 sinon retourner T(n-1)

Sa complexité est en O(n) mais la fonction est nulle

Voici mon premier post sur le sujet,

Bonjour,

Dans un exo on me demande de démontrer que T(n)=O(n) avec:
T(n) = T((n/2) + racine(n)) + n pour tout n>16

J'ai tenté d'effectuer un changement de variable pour avoir une recurrence linéaire, mais je n'y arrive pas.
Pourriez vous m'indiquer les changements de variables à faire, ou alors une autre méthode pour resoudre mon problème?

Merci d'avance.

Je ne comprends pas ce que tu essais de me dire!!!

[millie]

Ok, j'ai toujours cru qu'on parlait de complexité, au temps pour moi.

[rvfranck]

y a comme un truc qui me chiffonne...

C'est quoi le truc, c'est pas correct mon hypothèse?

[pseudocode]

C'est quoi le truc?

bah le truc c'est que si tu poses:

pour tout n > 16, T(n/2 + racine(n)) = O(n/2 + racine(n))

ton probleme est déjà résolu. Meme pas besoin d'induction, il suffit d'un changement de variable: k=n/2+racine(n) pour montrer que: pour tout k > 12, T(k)=O(k)