Discussion :

[phakso]

...

O (n log n)

ça me parle pas...
log = logique ?

O ?

[j.p.mignot]

Ce sont les notations de LANDAU
'Grand O' : f(x) = O(h(x)) signifie f est dominée par h au voisinage de l donc il existe m,A tel que si |x-l | < m alors |f(x)| < A * |h(x)|
'Petit o' : o(h(x)) signifie " infiniment petit devant" h(x)
au voisinage de l

Si une f fonction est en o(h(x)) au voisinage de l cela signifie que si x tends vers l alors f(x)/h(x) tends vers 0
par exemple au voisinage de 0 on peut écrire
e^x = 1 + x + x^2/2! + o(x^2)
ou bien
e^x = 1 + x + x^2/2! + O(x^3)



Si une fonction se comporte en O(xln(x)) quand x tend vers + l'infini cela veut dire f(x)/ (x.log(x)) est borné si x tends vers + l'infini donc
qu'il existe m, A tel que
| f(x) | < A * x.ln(x) pour tout x > m



voir par exemple les liens:

http://perso.wanadoo.fr/megamaths/oral1/cfon0006.pdf
http://perso.wanadoo.fr/megamaths/pac/cdev0002.pdf
http://fr.wikipedia.org/wiki/Notations_de_Landau




Pour rappel
log = Logarithme base 10,
ln = logarithme Néperien [en souvenir du baron Néper]
(de base e=2.732... )

[Jedai]

Pour rappel
log = Logarithme base 10,
ln = logarithme Néperien [en souvenir du baron Néper]
(de base e=2.732... )

log est en général employé pour désigner les logarithmes, pas toujours en base 10, d'ailleurs en informatique il désigne très souvent un logarithme en base 2.

--
Jedaï

[j.p.mignot]

Exact!
si j'ai toujours vu Ln pour log neperien suivant les languages log peut être base dependant! (2, e, 10)
Dans la + part de mes codes j'utilise une fonction du type
L(x) = log(x) / log(base) pour m'assurer de la base et de la portabilité du code entre compilateurs

[MisterTee]

c'est bien tout ça mais je me demande si l'interressé a compris.

bon pour résumer

La complexité d'un algorithme se mesure essentiellement en calculant le nombre d'opérations élémentaires pour traiter une donnée de taille n. Les opérations élémentaires considérées sont

le nombre de comparaisons (algorithmes de recherche)
le nombre d'affectations (algorithmes de tris)
Le nombre d'opérations (+,*) réalisées par l'algorithme (calculs sur les matrices ou les polynômes).

va voir ce cours ça t'aidera.
http://www.lri.fr/~chris/cours/Algo&complexite1.pdf

[ToTo13]

Bonjour,
donnons quelques petits exemples pour faire comprendre tout cela.
Retiens déjà que la complexité se calcule toujours en considérant le pire des cas.

Exemple 1 : On veut trouver le plus petit élément d'un tableau non trié de taille N. Pour cela il faut parcourir tout le tableau. Donc la complexité est en O(N).

Exemple 2 : Le tri que je t'ai expliqué dans ton précédent message, celui où l'on recherche chaque fois le plus petit élément. Dans ce cas, le pire des cas est que le tableau soit déjà trié par ordre décroissant, alors que nous le souhaitons en ordre croissant. Donc pour la première boucle, nous devons parcourrir les N éléments du tableau, puis pour le deuxième les N-1, pour la troisième N-2, .... Il y aura donc N+(N-1)+(N-2)+...2+1. Or la somme des N premiers élément vaut ∑(N) = N(N+1)/2. On garde alors l'élément de plus grande puissance, ici N^2, donc 0(N^2).
Idem pour le tri à bulle, le tri par fusion et par insertions.
Pour le QuickSort, la complexité dans le pire des cas est en O(N^2) mais en moyenne en O(Nlog(N)). Le tri par tas est moins rapide mais plus stable en O(N log(N)).

Exemple 3: Pour la recherche dichotomique, on divise l'espace de travail par deux à chaque itérations, donc ue complexité en O(Log2(N)).

Bonne continuation
[/b]

[HanLee]

Oublie pas de ne pas toujours te fier à ces notations, parce qu'elles ne font pas apparaître la constante devant.