C17.2 : Complexité d'un algorithme
Présentation
Préambule
Lorsqu'on écrit un algorithme, trois questions fondamentales se posent :
- • Est-ce qu'il se termine ? => C'est ce que l'on appelle la terminaison.
- • Est-ce qu'il donne le résultats attendu ? => C'est ce que l'on appelle la correction.
- • Est-ce qu'il donne le résultat en utilisant des ressources (temps, mémoire...) raisonnables ? => C'est ce que l'on appel la complexité ou le coût.
Dans cette activité, nous allons parler de la complexité (que l'on appelle aussi le coût) d'un algorithme.
Définition
La complexité (le coût) d'un algorithme est le nombre d'opérations élémentaires effectuées par un algorithme. Ce nombre s'exprime en fonction de la taille des données traitées par l'algorithme.
Application à quelques algorithmes classiques avec des listes
Somme des valeurs d'une liste
🖥️ 1) Écrire une fonction qui prend une liste d'entiers en paramètre et renvoie la somme des valeurs de la liste.
🖊️ 2) Déterminer la complexité (le coût) de cet algorithme, c'est-à-dire, ici, le nombre d'additions que l'algorithme effectue en fonction de la longueur \(n\) de la liste.
🖥️ 3) Ajouter un compteur à la fonction de façon à pouvoir afficher en fin de fonction le nombre de boucles effectué par le programme.
Recherche de la valeur minimale d'une liste
🖥️ 1) Écrire une fonction qui prend une liste d'entiers (non vide) en paramètre et renvoie la plus petite valeurs de la liste.
🖊️ 2) Déterminer la complexité (le coût) de cet algorithme, c'est-à-dire, ici, le nombre de comparaisons que l'algorithme effectue en fonction de la longueur \(n\) de la liste.
🖥️ 3) Ajouter un compteur à la fonction de façon à pouvoir afficher en fin de fonction le nombre de boucles effectué par le programme.
Vocabulaire
Lorsque la complexité (le coût) est proportionnelle à la taille des données, on dit que la complexité est linéaire.
Application aux algorithmes de recherche
Dans notre cas :
- - l'opération élémentaire sera l'ensemble des comparaisons dans la boucle,
- - la taille des données sera la longueur de la liste.
On souhaite donc savoir combien l'algorithme doit faire de comparaisons en fonction de la longueur de la liste dans laquelle on recherche l'élément.
Complexité pour la recherche séquentielle
🖊️ 1) Pour quelles valeurs recherchées le nombre de comparaisons est-il le plus petit ? Quel est, dans ce cas, le nombre de comparaisons faites pour une liste contenant \(n\) entiers ?
🖊️ 2) Pour quelles valeurs recherchées le nombre de comparaisons est-il le plus grand ? Quel est, dans ce cas, le nombre de comparaisons faites pour une liste contenant \(n\) entiers ?
Vocabulaire
La situation la plus défavorable est appelée le pire cas. Dans ce cas, la complexité en fonction de la longueur \(n\) des données est notée \(O(n)\).
La situation la plus favorable est appelée le meilleur cas. Dans ce cas, la complexité en fonction de la longueur \(n\) des données est notée \(o(n)\).
Coût pour la recherche par dichotomie
🖊️ 1) Quels sont le meilleur cas et le pire cas pour l'algorithme dichotomique ?
🖊️ 2) Quel est le nombre de comparaisons faites par l'algorithme dichotomique pour une liste contenant \(n\) entiers, dans le pire cas ?
Comparaison des deux algorithmes
🖊️ Compléter le tableau ci-dessous.
| Longueur de la liste | Complexité pour la recherche séquentielle dans le pire cas | Complexité pour la recherche par dichotomie dans le pire cas |
|---|---|---|
| 1000 | ||
| 10000 | ||
| 100000 | ||
| 1000000 |