Complexité algorithmique et notation grand O

Informatique de gestion · Bachelor 2

Mesurer l'efficacité d'un algorithme : notation grand O, classes de complexité, temps et mémoire.

Introduction

La complexité algorithmique permet de comparer des algorithmes indépendamment de la machine qui les exécute, en observant comment leur coût (nombre d'opérations élémentaires ou quantité de mémoire) évolue avec la taille n des données. La notation grand O décrit une borne supérieure du comportement asymptotique et ignore les constantes et les termes d'ordre inférieur.

Les classes usuelles, de la plus rapide à la plus coûteuse, sont O(1) constant, O(log n) logarithmique, O(n) linéaire, O(n log n) quasi-linéaire, O(n²) quadratique et O(2ⁿ) exponentiel. La recherche dichotomique dans un tableau trié est en O(log n), alors qu'une recherche séquentielle est en O(n) ; un tri par insertion est en O(n²) dans le pire cas, tandis que le tri fusion garantit O(n log n).

Dans un contexte de gestion, ces notions déterminent si un traitement de fin de mois sur des millions d'écritures restera exécutable en quelques minutes ou deviendra inutilisable lorsque le volume croît. On distingue aussi le meilleur cas, le cas moyen et le pire cas, ainsi que le compromis fréquent entre temps de calcul et mémoire utilisée.

Objectifs d'apprentissage

Déterminer la complexité temporelle d'une boucle simple ou imbriquée
Classer les ordres de grandeur usuels du plus rapide au plus lent
Comparer recherche séquentielle et dichotomique
Distinguer meilleur cas, cas moyen et pire cas
Expliquer un compromis entre temps et mémoire

Concepts clés

Notation grand O: O(f(n)) borne supérieure asymptotique du coût : on retient le terme dominant et on supprime les constantes multiplicatives.
Classes de complexité usuelles: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) : plus on descend, plus un accroissement de n est pénalisant.
Recherche séquentielle et dichotomique: Séquentielle : O(n) sur n'importe quelle liste. Dichotomique : O(log n), mais exige des données triées.
Pire cas, cas moyen, meilleur cas: Le pire cas donne une garantie de performance ; le cas moyen dépend de la distribution des données.
Compromis temps-mémoire: On peut accélérer un calcul en stockant des résultats intermédiaires (index, cache, table de hachage) au prix d'une mémoire supplémentaire.

Conclusion

La notation grand O fournit un langage commun pour discuter de la performance et de la capacité d'un algorithme à tenir la charge lorsque les volumes augmentent. Elle ne remplace pas la mesure expérimentale, mais oriente les choix de conception.

Pour un futur informaticien de gestion, savoir estimer l'ordre de grandeur d'un traitement évite des architectures qui ne passent pas à l'échelle.

Cartes

Que mesure la complexité algorithmique ?: L'évolution du nombre d'opérations (complexité temporelle) ou de la mémoire (complexité spatiale) en fonction de la taille n des données.
Que signifie O(n²) ?: Le coût croît au plus proportionnellement au carré de n : doubler n multiplie le temps environ par quatre.
Quelle est la complexité d'une boucle simple de 1 à n ?: O(n), linéaire.
Quelle est la complexité de deux boucles imbriquées de 1 à n ?: O(n²), car le corps interne s'exécute n × n fois.
Pourquoi ignore-t-on les constantes en grand O ?: Parce qu'on s'intéresse au comportement pour de grandes valeurs de n, où le terme dominant l'emporte sur les constantes.
Quelle est la complexité de la recherche dichotomique et son prérequis ?: O(log n), à condition que le tableau soit trié et accessible par indice.
Quelle est la complexité du tri fusion dans tous les cas ?: O(n log n).
Quelle est la complexité du tri par insertion dans le pire cas ?: O(n²), lorsque les données sont triées à l'envers.
Qu'est-ce que O(1) ?: Un temps constant, indépendant de n, par exemple lire un élément d'un tableau par son indice.
Donnez un exemple de compromis temps-mémoire.: Un index ou une table de hachage accélère les recherches mais consomme de la mémoire supplémentaire et doit être maintenu.

Glossaire

Complexité temporelle: Évolution du nombre d'opérations d'un algorithme en fonction de la taille des données.
Complexité spatiale: Quantité de mémoire supplémentaire requise en fonction de la taille des données.
Grand O: Notation exprimant une borne supérieure asymptotique du coût.
Recherche dichotomique: Recherche qui divise par deux l'intervalle d'un tableau trié à chaque étape.
Pire cas: Entrée qui maximise le coût d'un algorithme.
Table de hachage: Structure permettant un accès en temps moyen constant via une fonction de hachage.