[complexité algo] recurrence avec changement de variable

**rvfranck** · 10/10/2007, 10h30

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.

**Nemerle** · 10/10/2007, 11h22

Qu'appelles-tu récurrence linéaire? Et dans T(n) = T((n/2) + racine(n)) + n, le n/2 est bien la division entière? Dans ce cas, c'est explicite, tu as une profondeur n/2 pour atteindre T(1)...

**rvfranck** · 10/10/2007, 14h17

Merci,

J'entends par recurrence lineaire une recurrence où T(n) est exprimé en fonction de T(n-k) avec k entier naturel. quelque chose comme ça T(n) = T(n-1) + T(n-2). oui, n/2 est bien la division entière.

On me demande de démontrer... vous avez une idée?

**Nemerle** · 10/10/2007, 15h33

difficile de remplacer une division par une soustraction

**souviron34** · 10/10/2007, 16h17

facile !!!!!

C'est dans les ordres de grandeur....

srqt(n) < n/2 pour tout n >= 3

Donc des que l'on atteint 4, T(n/2+sqrt(n)) est deja calcule

Donc

Code :

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

1
2
3
 pour i = 4 a i = N
 
    Pour calculer T(i), il faut ajouter a i quelque chose qui est deja calcule.

Donc le calcul de T(N) sera proportionnel a N....

CQFD

**Nemerle** · 10/10/2007, 16h55

D'accord avec toi, mais tu n'as pas changé l'eau / en vin -

**rvfranck** · 11/10/2007, 22h10

Je voulais m'inspirer de ce qu'a dit Souviron

Envoyé par souviron34

facile !!!!!

C'est dans les ordres de grandeur....

srqt(n) < n/2 pour tout n >= 3

Donc des que l'on atteint 4, T(n/2+sqrt(n)) est deja calcule

Donc

Code :

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

1
2
3
 pour i = 4 a i = N
 
    Pour calculer T(i), il faut ajouter a i quelque chose qui est deja calcule.

Donc le calcul de T(N) sera proportionnel a N....

CQFD

Lorsqu'on dépasse une certaine valeur, pour moi 22, T(n/2 + sqrt(n)) est déjà calculé et il vaut O(n). ce qui fait que T(n) = T(n/2 + sqrt(n)) + n va donner O(n).

Mais comme je l'ai lu dans un post, il faut tout prouver mathématiquement.

**rvfranck** · 13/10/2007, 18h59

Envoyé par 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

Voici mon premier post sur le sujet,

Envoyé par rvfranck

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!!!