Après avoir acquis les bases de l'algorithmique dans la première UE, cette partie du cours vous permettra d'aller plus loin.
Nous apprendrons d'abord à évaluer la performance d'un algorithme, en analysant sa complexité en temps et en espace mémoire.
Nous mettrons ensuite en pratique ces notions en implémentant des algorithmes classiques de recherche et de tri.
Il est en effet important de comprendre que l'efficacité d'un algorithme ne se limite pas à vérifier qu'il "fonctionne". Deux algorithmes peuvent donner le même résultat mais l'un sera bien plus rapide ou utilisera moins de mémoire que l'autre. Pour évaluer cette efficacité, on utilise la notation Grand O, qui décrit comment le temps d'exécution ou la mémoire consommée croissent en fonction de la taille des données.
1. Pourquoi mesurer la complexité ?
Lorsque la quantité de données augmente, le temps de calcul peut exploser.
Un tri efficace sur 100 éléments peut devenir inutilisable sur un million.
Plutôt que de mesurer en secondes (qui dépendent du matériel ou du langage), on préfère une mesure abstraite : combien d'opérations l'algorithme effectue en fonction du nombre d'entrées n. Cette mesure permet de comparer des algorithmes indépendamment de la machine.
2. La notation Grand O
La notation O(f(n)) exprime un ordre de grandeur : elle donne une borne supérieure du nombre d'opérations pour des données de taille n.
Dire qu'un algorithme est en O(n) signifie que le nombre d'étapes croît au plus linéairement avec n.
On ignore les constantes et les termes moins significatifs, car pour de grands n seul le comportement dominant compte.
Exemple : si un algorithme effectue 3n + 5 comparaisons, on écrit O(n) : les constantes 3 et 5 deviennent négligeables lorsque n devient grand.
3. Complexité en temps
La complexité en temps mesure la durée théorique d'exécution.
O(1) : temps constant, quelle que soit la taille de l'entrée.
Accéder à l'élément d'un tableau par son index est typiquement O(1).
O(log n) : temps logarithmique.
Une recherche binaire dans un tableau trié divise l'espace de recherche par deux à chaque étape.
O(n) : temps linéaire.
Parcourir une liste pour trouver une valeur, ou additionner ses éléments.
O(n log n) : temps quasi-linéaire.
Beaucoup d'algorithmes de tri efficaces (quicksort, mergesort) ont ce comportement.
O(n²) et au-delà : temps quadratique ou pire.
Un tri naïf par insertion sur une grande liste en est un exemple.
Exemple comparatif
Supposons deux fonctions :
f1 parcourt un tableau pour chercher une valeur : O(n).
f2 utilise la recherche binaire : O(log n).
Pour n = 1 000 000, f1 effectue en moyenne un million de comparaisons, f2 seulement une vingtaine.
4. Complexité en espace
L'espace mémoire est tout aussi important.
On évalue combien de mémoire supplémentaire l'algorithme requiert au-delà des données initiales.
Un tri en place comme quicksort consomme O(log n) mémoire pour la récursion.
Un algorithme qui duplique entièrement ses données (ex. merge sort classique) peut nécessiter O(n) espace supplémentaire.
Minimiser l'espace est essentiel sur les systèmes embarqués ou quand les données sont volumineuses.
5. Le Cas moyen, le meilleur cas et pire
La complexité peut varier :
Pire cas : nombre maximal d'opérations (important pour garantir un temps maximum).
Meilleur cas : scénario le plus favorable.
Cas moyen : comportement typique sur des données aléatoires.
Pour quicksort par exemple, le cas moyen est O(n log n), mais un pivot mal choisi peut mener à O(n²) dans le pire cas.
Exercice
Problème du Maximum Subarray (version naïve)
1. Complexité en temps (Grand-O)
Analysez les deux boucles imbriquées pour déterminer le nombre total d'opérations en fonction de n, la taille du tableau.
Exprimez la complexité temporelle dans le pire des cas.
2. Complexité en espace (mémoire)
Listez les variables supplémentaires utilisées.
Déterminez l'espace additionnel requis en fonction de n.
Que se passe-t-il si le tableau contient un million d'éléments ?
Proposez une idée d'optimisation pour améliorer la complexité en temps.
