La complexité algorithmique fait partie des points qui séparent une réponse intuitive d'une réponse vraiment justifiée. En prépa, on ne te demande pas seulement de dire qu'un algorithme est rapide ou lent. On attend que tu identifies la taille de l'entrée, que tu comptes les opérations importantes et que tu expliques pourquoi le coût obtenu correspond bien au programme ou au pseudo-code étudié.
L'objectif n'est pas de surtechniciser la copie. Une bonne justification de complexité peut être courte, à condition d'être précise. Elle doit dire ce qui varie, ce qui est compté, dans quel cas on raisonne et quelle conclusion on tire. Cette méthode sert autant en spécialité informatique MPI que dans les exercices d'algorithmique plus classiques.
1. Commencer par le bon paramètre
Avant de compter quoi que ce soit, il faut annoncer le paramètre. Le plus souvent, on note n la taille de l'entrée : longueur d'une liste, nombre d'éléments d'un tableau, nombre de sommets, nombre d'arêtes ou taille d'un mot. Mais le bon paramètre dépend du problème.
Pour un algorithme sur un graphe, dire seulement O(n) peut être ambigu. n désigne-t-il les sommets, les arêtes, ou les deux ? Une analyse claire écrira plutôt O(|V| + |E|) pour un parcours de graphe représenté par listes d'adjacence, ou précisera la représentation utilisée si elle change le coût d'accès aux voisins.
Cette première phrase évite beaucoup d'erreurs. Elle montre que la complexité n'est pas une étiquette attachée à un algorithme dans l'absolu, mais une estimation du coût en fonction d'une taille d'entrée et d'un modèle raisonnable d'exécution.
- Annonce toujours le paramètre avant la notation asymptotique.
- Sur un graphe, distingue le nombre de sommets et le nombre d'arêtes.
- La représentation des données peut changer le coût d'une opération.
2. Compter les répétitions, pas les lignes
Une erreur fréquente consiste à compter les lignes du programme. Or une ligne dans une boucle peut être exécutée des milliers de fois, tandis qu'une ligne hors boucle peut ne compter qu'une fois. Il faut donc repérer les blocs répétés et leur nombre d'exécutions.
Pour une boucle simple de 0 à n - 1, si le corps coûte un temps constant, le coût est linéaire. Pour deux boucles imbriquées qui parcourent chacune n valeurs, on obtient souvent un coût quadratique. Mais il faut regarder les bornes réelles : si la boucle interne parcourt seulement les indices inférieurs à l'indice courant, la somme 1 + 2 + ... + n reste de l'ordre de n².
Les appels récursifs demandent le même réflexe. On ne devine pas la complexité à partir du mot récursif. On écrit la relation de récurrence adaptée, même simplement : un appel sur une taille n - 1 avec un travail constant mène à un coût linéaire, deux appels sur des moitiés avec un travail linéaire mènent à un coût de l'ordre de n log n dans les cas classiques.
3. Préciser le pire cas, le meilleur cas ou le cas moyen
La plupart des analyses en prépa se font dans le pire cas, car il donne une garantie robuste : quel que soit l'entrée de taille n, le coût ne dépasse pas l'ordre annoncé. C'est souvent le choix le plus simple et le plus attendu en devoir.
Mais certains algorithmes ont des comportements très différents selon les données. Une recherche séquentielle trouve parfois l'élément au début, parfois à la fin, parfois pas du tout. Dans ce cas, il faut dire explicitement si l'on parle du meilleur cas, du pire cas ou d'un cas moyen sous une hypothèse de distribution. Sans cette précision, la comparaison peut devenir trompeuse.
Le cas moyen n'est pas une moyenne vague. Il suppose un modèle probabiliste sur les entrées. Si le sujet ne le donne pas, reste prudent. En copie, une phrase comme "dans le pire cas, la boucle examine tous les éléments" vaut mieux qu'une affirmation générale qui mélange plusieurs situations.
4. Comparer deux algorithmes avec le bon niveau de détail
Comparer deux algorithmes commence par les ordres de grandeur. Pour de grandes tailles d'entrée, un algorithme en O(n log n) devient généralement plus intéressant qu'un algorithme en O(n²). De même, un parcours linéaire est souvent préférable à une méthode qui répète une recherche complète à chaque étape.
Mais l'ordre asymptotique ne suffit pas toujours à décider dans un contexte concret. Pour de petites entrées, une méthode plus simple peut être plus rapide en pratique. Les constantes cachées, le coût mémoire, la facilité de preuve, la stabilité, la représentation des données et les contraintes du sujet peuvent changer le choix raisonnable.
En prépa, l'enjeu est de hiérarchiser. Tu peux écrire : "asymptotiquement, le second algorithme est meilleur, car n log n croît plus lentement que n². Le premier reste toutefois plus simple et peut être acceptable pour de petites tailles." Cette réponse compare sans perdre le cadre scientifique.
5. Comprendre le coût amorti sans le rendre mystérieux
Le coût amorti apparaît quand une opération isolée peut être coûteuse, mais que cette opération coûteuse ne peut pas se produire trop souvent dans une longue séquence. L'idée n'est pas de nier le pire cas ponctuel. L'idée est de répartir le coût total sur plusieurs opérations pour obtenir un coût moyen garanti par opération.
Un exemple classique est l'agrandissement d'un tableau dynamique. Ajouter un élément coûte souvent un temps constant, mais lorsque le tableau doit être recopié dans une zone plus grande, l'opération coûte plus cher. Si la capacité est multipliée de façon contrôlée, ces recopies restent assez rares pour que le coût amorti d'un ajout demeure constant.
En copie, le mot "amorti" doit donc être utilisé avec discipline. Il faut parler d'une séquence d'opérations, pas d'une seule opération. Il faut aussi expliquer pourquoi les opérations coûteuses sont suffisamment espacées. Cette précision suffit souvent à montrer que tu as compris l'idée sans entrer dans une analyse trop avancée.
6. Garder les ordres de grandeur en tête
Les notations O, Ω et Θ servent à raisonner sur la croissance quand la taille augmente. En pratique, les devoirs utilisent surtout O pour donner une borne supérieure. Cela ne signifie pas "environ égal à", mais "majoré à une constante près à partir d'un certain rang".
Pour comparer, retiens l'échelle suivante : constant, logarithmique, linéaire, quasi linéaire, quadratique, cubique, exponentiel. Cette échelle ne remplace pas une preuve, mais elle aide à détecter les réponses absurdes. Une solution exponentielle peut être impossible pour des tailles modestes, tandis qu'une solution linéaire reste souvent exploitable sur des données beaucoup plus grandes.
Les flashcards d'informatique prépa peuvent aider à stabiliser ces repères : définitions, complexités usuelles, structures de données et schémas de justification. Elles doivent rester un support de rappel, complété par des exercices où tu recomptes vraiment le coût.
7. Rédiger une justification propre en copie
Une justification efficace tient souvent en quatre phrases. Première phrase : on fixe le paramètre. Deuxième phrase : on identifie les opérations significatives. Troisième phrase : on compte les répétitions principales ou on donne la récurrence. Quatrième phrase : on conclut avec l'ordre de grandeur et le cas étudié.
Par exemple, au lieu d'écrire seulement "la complexité est O(n²)", écris : "On note n la longueur du tableau. La boucle externe est exécutée n fois et, pour chaque itération, la boucle interne parcourt au plus n éléments. Le coût de chaque comparaison est supposé constant. La complexité temporelle dans le pire cas est donc O(n²)."
Cette rédaction n'est pas longue, mais elle ferme les ambiguïtés. Elle montre aussi que tu sais relier le résultat au code. Le même réflexe s'applique aux automates et aux langages, par exemple lorsqu'un algorithme parcourt les états, les transitions ou les lettres d'un mot. Pour cet angle, l'article sur les automates en MPI, langages et déterminisation complète utilement le travail.
Travaille les repères d'algorithmique régulièrement
PSD aide à revoir les définitions, complexités et structures de données avec des flashcards adaptées à la prépa scientifique.
Conclusion
La complexité algorithmique devient beaucoup plus simple quand tu la présentes comme une justification, pas comme une formule à deviner. Fixe le paramètre, compte les répétitions, précise le cas étudié et conclus avec un ordre de grandeur. Pour comparer deux algorithmes, commence par l'asymptotique, puis ajoute les contraintes concrètes : mémoire, constantes, simplicité et forme des données.
En prépa, cette rigueur suffit souvent à transformer une réponse fragile en raisonnement solide. Elle rend aussi les exercices plus lisibles : tu ne cherches plus seulement "la bonne complexité", tu expliques pourquoi elle correspond au comportement de l'algorithme.
Questions fréquentes
Sources et références
- Ministère de l'Éducation nationale, Bulletin officiel, programmes de la filière MP2I et MPI.
- Ministère de l'Enseignement supérieur et de la Recherche, Classes préparatoires aux grandes écoles.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L. et Stein, C., Introduction to Algorithms, MIT Press, 4e édition, 2022.
- Roughgarden, T., Algorithms Illuminated lecture notes, Stanford University.
- MIT OpenCourseWare, 6.006 Introduction to Algorithms, Massachusetts Institute of Technology.