« Programmation algorithmique/Nombre d'opérations optimal » : différence entre les versions
Contenu supprimé Contenu ajouté
mAucun résumé des modifications |
mAucun résumé des modifications |
||
Ligne 1 :
La rapidité d'un algorithme est exprimée sous la forme du nombre d'opérations effectuées par celui-ci. En général, ce nombre dépend des données d'entrée.
Il existe différents nombres d'
* le nombre d'opérations minimal, qui se produit dans le meilleur des cas,
* le nombre d'opérations maximal, qui se produit dans le pire des cas,
* le nombre moyen d'opérations, qui est une moyenne de ce que l'on peut espérer d'un algorithme dans la plupart des cas.
Exemple :
* L'algorithme de tri à bulle s'effectue en ''O(n²)'' ;
* L'algorithme de tri rapide (appelé ''Quicksort'') s'effectue en moyenne en ''O(n*log(n))''.
|