Bases & algorithmique · 6 mondes · 18 étapes
Algorithmique
Apprendre à penser un problème, en Python, dans le navigateur.
Progression
0 %
0/18 étapes terminées
Intermédiaire · 10 min de lecture
La complexité
Mesurer un algorithme sans chronomètre
1Définition
La complexité compte les opérations en fonction de la taille de l'entrée n, et non les secondes. La notation O(...) garde la forme de la croissance et jette les constantes : 3n + 7 devient O(n).
2Principes fondamentaux
01
Compter, pas chronométrer
Une mesure en secondes dépend de la machine et de sa charge. Un nombre d'opérations est vrai partout.
02
Le pire cas décide
On dimensionne sur le pire cas, parce que c'est lui qui fait tomber les serveurs un mardi à 18 h.
03
Compter les boucles imbriquées
Chaque boucle dépendant de n ajoute un facteur n. Deux boucles imbriquées : O(n²).
04
Garder le terme dominant
O(n²) + O(n) vaut O(n²) : pour un grand n, le reste ne compte plus.
3Exemples pratiques
Les cinq classes utiles
1# O(1) accès direct valeurs[0]2# O(log n) diviser par deux dichotomie3# O(n) un parcours somme, maximum4# O(n log n) tri efficace sorted()5# O(n²) boucle dans boucle toutes les pairesPour n = 1 000 000 : 1 opération, 20, un million, vingt millions, mille milliards. La dernière ligne est hors de portée d'une machine.
Passer de O(n) à O(1)
1# Boucle : n opérations2total = 03for i in range(1, n + 1):4 total = total + i5 6# Formule de Gauss : 3 opérations7total = n * (n + 1) // 2Certaines optimisations ne sont pas du code mais des mathématiques. Elles sont les plus spectaculaires.
4Erreurs courantes
Optimiser sans mesurer
À éviter
# réécrire tout en une ligne illisible « pour la performance »À faire
# mesurer d'abord : compteur d'opérations, puis optimiser le vrai goulotPourquoi : La lisibilité se paie tout de suite, la performance gagnée est souvent nulle : le goulot était ailleurs.
Confondre coefficient et forme
À éviter
# « 3n est pire que n² parce que 3 > 1 »À faire
# n = 1000 : 3n = 3 000 et n² = 1 000 000Pourquoi : La forme de la croissance domine toujours le coefficient dès que n grandit.
Chercher dans une liste à l'intérieur d'une boucle
À éviter
for x in a: if x in b: # b est une liste : O(n) à chaque tour ...À faire
b_set = set(b)for x in a: if x in b_set: # O(1) ...Pourquoi : Une ligne change la complexité de O(n²) à O(n). C'est l'optimisation la plus fréquente du métier.
5Subtilités à connaître
- ◆
Odécrit une borne supérieure asymptotique : elle ne dit rien pour de petites entrées, où un O(n²) simple peut gagner. - ◆La complexité en mémoire compte autant que celle en temps : la mémoïsation échange l'une contre l'autre.
- ◆Aucun tri par comparaison ne peut faire mieux que n log n : c'est une limite mathématique, pas un manque d'ingéniosité.
6Vérifie ta compréhension
Question 1/3
Score 0
Complexité d'une double boucle sur n éléments ?
Envie d'essayer ? Ouvre le Labo et recopie les exemples pour les modifier.