« Programmation algorithmique/Nombre d'opérations optimal » : différence entre les versions

Contenu supprimé Contenu ajouté
Fogg (discussion | contributions)
mAucun résumé des modifications
Fogg (discussion | contributions)
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'opérationopérations :
* 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 : Unun algorithme de tri d'un tableau de ''n'' éléments effectuera un nombre moyen d'opérations dépendant de ''n'' (la taille du tableau) :
* 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))''.