Version imprimable
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.
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)...
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.:D
On me demande de démontrer... vous avez une idée?
difficile de remplacer une division par une soustraction ;)
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
Donc le calcul de T(N) sera proportionnel a N....Code:
2
3
CQFD:P
D'accord avec toi, mais tu n'as pas changé l'eau / en vin - :mouarf:
Allez, je fais le début et je laisse aux "matheux" le soin de terminer:
De maniere generale, on obtient:Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Code:
2
3
4
5
6
7
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)
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:
http://upload.wikimedia.org/math/d/7...c5790b7dc6.png
si et seulement si
http://upload.wikimedia.org/math/4/3...5795f48fd0.png
Pour continuer mon post précedant:
On montre facilement que limite i->+oo de u(i) = 4 (car decroissante, bornée, et en resolvant u(i+1)=u(i))Code:
2
3
4
5
6
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)
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
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.:DCitation:
Envoyé par paradize3
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)
8O
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é.Citation:
Envoyé par paradize3
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.
Citation:
Envoyé par paradize3
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
Ah bon ? Pour moi on a:Citation:
Envoyé par rvfranck
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.
ouais, t'as raison je me suis terriblement planté. :cry:
Je voulais m'inspirer de ce qu'a dit Souviron
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).Citation:
Envoyé par souviron34
Mais comme je l'ai lu dans un post, il faut tout prouver mathématiquement.
:lol:
Bah, j'ai l'impression de me répéter mais si tu calcules les premiers termes de T(n) tu obtiens:Citation:
Envoyé par rvfranck
on voit alors qu'on peut écrire:Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
il ne reste plus qu'a etudier la suite u(i).Code:
2
3
4
5
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
T(4) est une constante. Il ne nous reste qu'a etudier la somme infinie. Les premiers termes s'ecrivent:Code:
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
qu'on peut regrouper enCode:
2
3
4
la série ( 1 + 1/2 + 1/4 + 1/8 + ...) est bornée par 2 donc:Code:
2
3
4
pour un grand "n" les termes en "racine(...)" sont negligeables devant les termes en "n" doncCode:
2
Somme = O(n)
et donc
T(n) = O(n)
Merci!
J'espère qu'on est tous d'accord avec le raisonnement de pseudocode et qu'il n'ya rien à redire. :king:
Pour ma part c'est résolu, Merci encore. :lol: