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

**pseudocode** · 10/10/2007, 21h47

Allez, je fais le début et je laisse aux "matheux" le soin de terminer:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
T(n) = T( (n/2)+racine(n) ) + n
 
on pose: u1 = (n/2)+racine(n)
 
on réécrit T(n) comme:
 
T(n) = T(u1) + n
     = T(u1/2+racine(u1)) + u1 + n
 
on pose: u2 = (u1/2)+racine(u1) 
 
on réécrit T(n) comme:
 
T(n) = T(u2) + u1 + n
     = T(u2/2+racine(u2)) + u2 + u1 + n
 
on pose: u3 = ...

De maniere generale, on obtient:

Code :

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

1
2
3
4
5
6
7
 
u0=n
u(i+1) = (u(i)/2) + racine(u(i))
 
                    +oo
T(n) = T(u(+oo)) + Somme( U(i) )
                    i=0

**acx01b** · 10/10/2007, 23h02

salut

on te dit que pour calculer T(n) il faut connaitre T(n/2) et T(racine(n))

si N = 2^2^n
et si on ne regarde que le racine(N)
on dessine un arbre où à partir du noeud T(N) partent deux arrêtes vers T(racine(N)) et T(racine(N)) et ainsi de suite, d'où partent 4 noeuds T(racine(racine(N))) ...
à la fin on arrive à T(2)
on a un arbre binaire de profondeur n = log log N
donc qui contient 2^n = log N noeuds

si on ne regarde que le N/2
on dessine un arbre où à partir du noeud T(N) partent deux arrêtes vers
T(racine(N/2)) et T(racine(N/2)) et ainsi de suite, d'où partent 4 noeuds
T(N/4) ...
à la fin on arrive à T(1)
on a un arbre binaire de profondeur 2^n = log N
donc qui contient 2^2^n = N noeuds

avec notre arbre boiteux (d'un côté 2^N et de l'autre racine(N)) on a une complexité qui est comprise entre N et log N additions

donc la complexité de la fonction est pire que O(log N) et meilleure que O(N)

**pseudocode** · 11/10/2007, 09h45

je rappelle que le calcul de la complexité est un calcul mathematique rigoureux et pas une estimation pifometrique. La notation O(n) a une vraie definition mathématique:

si et seulement si

Pour continuer mon post précedant:

Code :

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

1
2
3
4
5
6
u0=n
u(i+1) = (u(i)/2) + racine(u(i))
 
                    +oo
T(n) = T(u(+oo)) + Somme( U(i) )
                    i=0

On montre facilement que limite i->+oo de u(i) = 4 (car decroissante, bornée, et en resolvant u(i+1)=u(i))
et que Somme( U(i) ) = n + n/2 + O(n) = O(n)
et donc que T(n) = T(4) + O(n) c'est a dire T(n) = constante + O(n) = O(n)

**paradize3** · 11/10/2007, 10h20

Bonjour,

On peut proceder de la sorte...

Si on peut ecrire:
Eq1: T(n) = a*n+c (avec 'a' et 'c' bornes lorsque n-> infini...).

cela implique: T(n) en O(n)

Eq1 =>
Eq2: T(n/2+sqrt(n)) = a*(n/2 + sqrt(n)) + c

si on reprend l'equation de depart T(n) = T(n/2 + sqrt(n)) + n et qu'on substitue avec Eq2, on obtient:

Eq3: T(n) = a*(n/2 + sqrt(n)) + c + n
Eq1: T(n) = a*n+c

Eq1 = Eq3
=> a*n+c = a*(n/2 + sqrt(n)) + c + n
=> a*n = a*(n/2 + sqrt(n)) + n
=> a = (sqrt(n) + n) / (n/2)
lorsque n->infini, a converge (a -> 2) donc a est borne pour n-> inf.

Maintenant on aimerai montrer que c est borne lorsque n->inf. Je fais l'hypothese que T(1) = constante = d (probablement oublie par l'auteur du post?).

dans ce cas T(1) = a*1+c = d => c borne.

on demontrant l'existance de a et c bornes, on a pu montrer que T(n) peut s'ecrire a*n+c, par consequent, la fonction est en O(n).

Ceci dit il y a peut-etre une bulle, je vous laisse relire!

Salutations,

Gregoire

**paradize3** · 11/10/2007, 10h23

D'autre part, je ne comprends pas l'interet de specifier:
pour tout n>=16

puisque O(n) n'a de sens que lorsque n tend vers l'inifini (borne superieure de l'asympthote).

Salutations,

Gregoire

**rvfranck** · 11/10/2007, 15h32

Envoyé par paradize3

D'autre part, je ne comprends pas l'interet de specifier:
pour tout n>=16

puisque O(n) n'a de sens que lorsque n tend vers l'inifini (borne superieure de l'asympthote).

Salutations,

Gregoire

Parce que lorsque n<=16 T(n) vaut une constante. J'aurai peu être du le préciser aussi, excusez moi.

On ne pourrait pas tout simplement raisonner ainsi?

- T(n) = constante pour tout n de [0, 16]
- En remarquant que pour tout n de [16, 22], n/2 + sqrt(n) <= 16
donc T1(n)=T(n) = une constante + O(n) = O(n) pour n de [0, 22]
- et pour finir, pour tout n de [23, infini],
T2(n) = T1(n) + O(n) = O(n) + O(n) = O(n), pour tout n

donc T(n) = O(n)

**paradize3** · 11/10/2007, 16h24

désolé mais je n'ai pas très bien compris le raisonnement, qu'est ce que T1,T2?

encore une fois dire que T(n) est en O(n) pour "certains n < 22" n'a pas de sens selon moi..

Grég

**rvfranck** · 11/10/2007, 16h34

Envoyé par paradize3

désolé mais je n'ai pas très bien compris le raisonnement, qu'est ce que T1,T2?

encore une fois dire que T(n) est en O(n) pour "certains n < 22" n'a pas de sens selon moi..

Grég

Je cherche les n (*) tel que, n/2+sqrt(n) soit <=16 ainsi T(n/2 + sqrt(n)) sera dans l'ordre de O(1). donc T(n) = O(1) + n = O(n) pour les n de 17 au maximum des n(*) que j'ai trouvé.
En fait, le n < 22 est tel que n/2 + sqrt(n) <= 16.

T1 et T2 c'est en fait T(n). C'était pour préciser que T(n) dans 22...infini vaut un certain T(dans 16..22) + n.

**millie** · 11/10/2007, 19h36

Envoyé par paradize3

Ceci dit il y a peut-etre une bulle, je vous laisse relire!

Tu n'as pas correctement montré que c était borné. De plus, je suggère d'utiliser des notations qui ne prête pas à confusion, du genre : c(n) et a(n).

Une première arnaque se situe à la ligne :
"=> a*n+c = a*(n/2 + sqrt(n)) + c + n
=> a*n = a*(n/2 + sqrt(n)) + n"

Où le c(n) disparait et ne permet en fait pas conclure grand chose.

Et la grosse arnaque se situe : "dans ce cas T(1) = a*1+c = d => c borne. " qui avec ma notation donne : "dans ce cas, T(1) = a(1) * 1 + c(1) " qui ne permet pas de savoir quelque chose sur c (sur N)

Certain travaille avec T alors que l'on pourrait raisonner sur la complexité de T (que l'on pourrait noter C) et qui s'écrit simplement :
C(n) = C(n/2+sqrt(n))+1
Il faut simplement montrer qu'il existe a (constant) et n0 tel que pour tout n>n0, C(n)<= alpha.n

**pseudocode** · 11/10/2007, 21h03

Envoyé par rvfranck

et pour finir, pour tout n de [23, infini],
T2(n) = T1(n) + O(n)

Ah bon ? Pour moi on a:

T2(n) = T(n) lorsque n>=23

donc

T2(n) = T(n) = T((n/2) + racine(n)) + n (avec n>=23)

Comment apparait le terme T1(), c'est a dire avec 16<n<=22 ?
Par exemple:

T2(100) = T(100) = T(50 + 10) + 100 = T(60) + 100

pourtant le "60" dans T(60) n'est pas entre 16 et 22.

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

ouais, t'as raison je me suis terriblement planté.

**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.

**pseudocode** · 11/10/2007, 22h59

Envoyé par rvfranck

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

Bah, j'ai l'impression de me répéter mais si tu calcules les premiers termes de T(n) tu obtiens:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
T(n) = T( (n/2)+racine(n) ) + n
 
on pose: u1 = (n/2)+racine(n)
 
T(n) = T(u1) + n
 
on développe T(u1) en utilisant la formule de recursion
 
T(n) = T(u1/2+racine(u1)) + u1 + n
 
on pose: u2 = (u1/2)+racine(u1) 
 
T(n) = T(u2) + u1 + n
 
on développe T(u2) en utilisant la formule de recursion
 
T(n) = T(u2/2+racine(u2)) + u2 + u1 + n
 
on pose: u3 = (u2/2)+racine(u2) 
 
T(n) = T(u3) + u2 + u1 + n
 
...

on voit alors qu'on peut écrire:

Code :

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

1
2
3
4
5
T(n) = T(u(i)) + u(i-1) + u(i-2) + ... + u(2) + u(1) + u(0)
 
avec:
u(0)=n
u(i+1)=u(i)/2+racine(u(i))

il ne reste plus qu'a etudier la suite u(i).
pour n>4, elle est strictement décroissante et toujours positive => donc convergente. En posant u(i+1)=u(i) on trouve que sa limite vaut 4.

En faisant croite "i" vers l'infini on obtient

Code :

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

1
2
3
4
5
6
7
8
9
 
                        +oo 
T(n) = T( lim u(i) ) + Somme u(i)
          +oo           i=0
 
c'est a dire
                 +oo
T(n) = T( 4 ) + Somme u(i)
                 i=0

T(4) est une constante. Il ne nous reste qu'a etudier la somme infinie. Les premiers termes s'ecrivent:

Code :

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

1
2
3
4
 
Somme = u0 + { u1 } + { u2 } + ...
 
Somme = n + { n/2 + racine(n) } + { (n/2+racine(n))/2 + racine(n/2+racine(n)) } + ...

qu'on peut regrouper en

Code :

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

1
2
3
4
 
Somme = ( n + n/2 + n/4 + ... ) + des termes en racine(...) 
 
Somme = n * (1 + 1/2 + 1/4 + ... } + des termes en racine(...)

la série ( 1 + 1/2 + 1/4 + 1/8 + ...) est bornée par 2 donc:

Code :

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

1
2
 
Somme <= 2*n + des termes en racine(...)

pour un grand "n" les termes en "racine(...)" sont negligeables devant les termes en "n" donc

Somme = O(n)

et donc

T(n) = O(n)

**rvfranck** · 12/10/2007, 07h08

Merci!
J'espère qu'on est tous d'accord avec le raisonnement de pseudocode et qu'il n'ya rien à redire.

Pour ma part c'est résolu, Merci encore.

[complexité algo] recurrence avec changement de variable

Algorithmes et structures de données

Discussions similaires

Partager

Partager