Complexité algorithmique.
Un algorithme est implémenté dans un langage spécifique (Java, C, Python,...) et va s'exécuter sur une machine.
La durée d'execution du programme va dépendre du nombre d'instructions élémentaires mobilisées lors de son execution. On parle alors de compléxité temporelle.
Le programme va également mobiliser un certain nombre de ressources machines, en particulier la mémoire. On parle alors de compléxité spatiale.
Etre capable d'évaluer la complexité d'un algorithme est importante, tout particulièrement, dans le cadre du traitement de données importantes ( big data ). Cela va permettre de sélectionner l'algorithme le plus performant en fonction des données à traiter.
Il nous faut donc être capable de comparer la complexité d'algorithmes permettant de résoudre un même problème, pour choisir le plus efficient..
Soit l'algorithme ci-dessous, permettant de savoir si une valeur donnée se trouve dans un tableau de n éléments.
fonction recherche(val, tab)
ind <- 0
trouvé <- Faux
Tant que (ind < n) ET (trouvé = Faux)
Si (tab[ind] = val) Alors Trouvé <- Vrai
ind <- ind + 1
Fin Tant Que
Retouner trouvé
Tout d'abord, cet algorithme doit être traduit dans un langage de programmation pour pouvoir être executé par une machine.
On pourraît alors exécuter ce programme de nombreuses fois sur des jeux d'essai variés et chronométrer le temps d'execution.
Mais cette méthode n'est pas valide, car elle dépend des performances du processeur et surtout de la gestion du multi-tâche. En effet, lors de son execution le programme peut-être suspendu temporairement par le système d'exploitation si celui-ci à des tâches systèmes plus prioritaires à exécuter.
Cela dépend également si on utilise un langage compilé ou interprété, en code natif ou en pseudo code exécuté via une machine virtuelle.
Une autre approche est donc indispensable.
Nous pouvons étudier l'algorithme et définir un ordre de compléxité pour chacune des instructions algorithmiques de base.
Nous parlerons donc plutôt de complexité temporelle qui correspond aux nombres instructions élémentaires mobilisées lors de l'execution de l'algorithme.
Cette complexité en temps dépend assez naturellement de la taille n des données à traiter (plus le nombre de données est grand plus le temps d'exécution est long).
C'est le nombre de répétitions des traitements qui détermine en grande partie l'ordre de complexité d'un algorithme.
Reprenons notre exemple de recherche d'une valeur dans un tableau de n éléments :
fonction recherche(val, tab)
ind <- 0
trouvé <- Faux
Tant que (ind < n) ET (trouvé = Faux)
Si (tab[ind] = val) Alors Trouvé <- Vrai
ind <- ind + 1
Fin Tant Que
Retouner trouvé
Dans tous les cas, à chaque itération on réalise :
Soit 5 instructions. Nous pouvons estimer un temps t d'execution équivallent pour chacune d'entre elles, soit 5t au total.
Ensuite on peut considérer plusieurs cas possibles pour déterminer la complexité temporelle de cet algorithme.
Le plus souvent on se place dans le cas le moins favorable.
Dans notre exemple d'algoritme de recherche, dans le pire des cas, on parcourt tous les éléments du tableau (n valeurs).
On peut donc considérer qu'un ordre de grandeur pour le temps d'execution de cet algorithme est de l'ordre de n x 5t.
Quand n est très grand, on peut négliger 5t. On peut donc considérer que la complexité de cet algoritme est de l'ordre de n.
On dit que la compléxité de cet algoritme est de l'ordre de n, notée O(n).
L'étude des différents algorithmes proposés dans la suite des activités (Tris, Recherche, Knn,...) permettra de mettre en évidence les différents ordres de grandeur suivants :
| Ordre de compléxité | exemples | Type de compléxité |
|---|---|---|
| O(1) | Ici la complexité ne dépend pas des données. Accès à une cellule d'un tableau. | constante |
| O(logk(n)) | Algorithme divisant le problème par une constante k.
O(log2(n)) pour la recherche dichotomique (k=2). | logarithmique |
| O(n) | Parcours de liste. | linéaire |
| O(n.logk(n)) | Algorithme divisant le problème en nombre de
sous-problèmes constants (k), dont les résultats sont réutilisés par recombinaison(Ex Tri fusion). | quasi-linéaire |
| O(n2) | Algorithme traitant généralement de couples de
données (boucles imbriquées). Parcours d'une matrice de pixels. | quadratique |
Même si cela n'est pas rigoureux, chronométrer un programme peut-être utile et peut donner une idée de sa complexité.
Vous pouvez consulter à ce propos la fiche PythonChrono