La complexité d'un algorithme est la mesure du nombre d'opérations fondamentales qu'il effectue sur un jeu de données. Elle est exprimée comme une fonction de la taille du jeu de données.
| classe | Nom courant | Si on double n |
|---|---|---|
| O(1) | constant | prend le même temps |
| O(log(n)) | logarithmique | prend un tout petit peu plus de temps |
| O(n) | linéaire | prend 2x plus de temps |
| O(nlog(n)) | linéarithmique | prend 2x plus de temps + un tout petit peu plus |
| O(n²) | quadratique | prend 4x plus de temps |
| O(n3) | cubique | prend 8x plus de temps |
| O(2n) | linéaire | temps précédent au carré : beaucoup plus long |
En utilisant la recherche naive, on parcours l'ensemble du tableau jusqu'à tomber sur l'élément.
Si on double la taille du tableau, On double le temps de recherche : La complexité de l'algorithme de recherche est donc de classe linéaire
En utilisant la recherche dichotomique, on séléctionne l'élément du milieu du tableau et on le compare à l'élément recherché. S'il est supérieur à ce dernier, on répéte l'opération avec la première moitié du tableau, sinon, avec la deuxième moitié. On réitère l'opération avec le deuxième tableau obtenu jusqu'à tomber sur l'élément recherché.
La complexité de l'algorithme de recherche est logarithmique
Le tri à bulle consiste à selectionner un élément du tablau et le comparer à son voisin de droite. S'il est plus grand que ce dernier, on permute les deux éléments.
Le tri à bulle consiste à selectionner un élément du tablau et le comparer à son voisin de droite. S'il est plus grand que ce dernier, on permute les deux éléments.
Le tri à bulle consiste à selectionner un élément du tablau et le comparer à son voisin de droite. S'il est plus grand que ce dernier, on permute les deux éléments.
Le tri à bulle consiste à selectionner un élément du tablau et le comparer à son voisin de droite. S'il est plus grand que ce dernier, on permute les deux éléments.