Bonjour,  
j'ai regardé plusieurs cours d'algo, mais j'ai jamais compris le principe.
Pour la complexité
En théta(n) c'est le mailleur des cas et 0 (n) c'est le pire des cas c'est ça?
pouvez-vous me donner un exemple concret d'un algo en théta(n) et O(n).?
Merci

Ca n'a rien a voir avec le pire pour le meilleur des cas. Si je me souviens bien, etant donnees deux suites f et g :
 
f = O(g) signifie qu'il existe a et m strictement positifs tels que pour tout n > m, f(m) <= a*g(n) (on dit que f est dominee par g).
 
f = Theta(g) signifie qu'il existe a, b et m strictement positifs tels que pour tout n > m, a*g(n) <= f(n) <= b*g(n)
 
Donc Theta() est "plus fort" que O : si f = Theta(g) alors forcement f = O(g).
 
Dans ton cas, f est la complexite de l'algorithme. Ca peut etre le complexite dans le meilleur des cas, dans le pire des cas, ou en moyenne... Les notations restent les memes. Et il faut preciser "complexite en O(n^2) dans le pire des cas" ou "complexite en O(n*log(n)) en moyenne", par exemple. Note quand meme que si la complexite est en O(g) dans le pire des cas, alors elle est aussi en O(g) dans le meilleurs cas. Par contre si elle est en Theta(g) dans le pire cas, elle n'est pas forcement en Theta(g) dans le meilleurs cas (elle peut etre meilleur). En quelque sorte O est un "majorant" de la complexite. Souvant en algorithmique on dit O, mais en fait on pourrait dire Theta.

Tu pourrais pas nous donner des exemples?
ça a l'air incompréhensible.

O(n) est une borne maximale alors que Théta(n) est à la fois une borne maximale et minimale.

Si tu veux un exemple, prend le trie de n entiers en creant une liste chainee ordonnee : pour chaque element, tu parcous la liste jusqu'a trouver un entier plus grand, et tu places le nouvel element juste avant. Dans le pire des cas, il te faut n*(n-1)/2 operations (si les elements sont deja tries, en fait).
 
Existe-t-il a > 0 tel qu'a partir d'un certain rang, n*(n-1)/2 <= a*n^2 ? Oui, pour a = 1 par exemple (en fait pour tout a > 1/2). Donc la complexite dans le pire des cas est en O(n^2). Une autre facon equivalente de le monter et de montrer que la limite de (n*(n-1)/2) / (n^2) est finie (c'est le cas puisque c'est 1/2).
 
Existe-t-il b > 0 tel qu'a partir d'un certain rang, n*(n-1)/2 >= b*n^2 ? Oui, pour a = 1/4 par exemple, c'est vrai a partir du rang 2 (et de meme pour tout a < 1/2 on peut trouver un rang a partir duquel l'inegalite est verifiee). Donc la complexite dans le pire des cas est en Theta(n^2).
 
Note que pour cet exemple, on pourrait aussi dire que la complexite dans le pire des cas est en O(n^3), en O(n^4), en O(2^n) ou en O de tout ce qui grandit plus vite que n^2. Par contre elle n'est PAS en Theta(n^3) car n^3 / (n*(n-1)/2) tend vers l'infini.

ok merci