Croissance en grand O : ce que coûte vraiment chaque classe de complexité
Vos données
Deux algorithmes face à face
La constante, c'est tout ce que la notation jette : allocations, défauts de cache, le travail à l'intérieur de chaque étape. Donnez à l'un des algorithmes une constante plus lourde et regardez où elle cesse de compter.
Cette page ne lit pas votre boucle. Deviner une complexité à partir du code serait une conjecture déguisée en mesure : une boucle peut s'interrompre, un seul appel à l'intérieur peut cacher le vrai coût, et la récursion se lit rarement pour ce qu'elle fait. Vous choisissez la classe ; ce que la page calcule ensuite est exact.
Résultats
| Où l'un dépasse l'autre, en éléments | — |
| Opérations de chacun, à la taille ci-dessus | — |
Avec les chiffres par lesquels cette page commence, le croisement se situe à 439 éléments. Celui qui adopte la meilleure classe sur une liste de deux cents a rendu le programme plus lent et le code plus difficile, sans que la notation l'avertisse : la notation parle de ce qui arrive à la fin, pas de ce qui vous arrive.
Chaque classe à cette taille
| Classe | Opérations | Temps | Multiplié par, si l'entrée double |
|---|
La dernière colonne mérite qu'on la fixe, car c'est celle que personne ne porte en tête. Le travail linéaire double. Le quadratique quadruple. L'exponentiel est élevé au carré : avec mille éléments déjà en jeu, doubler l'entrée multiplie le coût par deux puissance mille, un nombre de trois cent deux chiffres.
La factorielle est pire d'une manière qui n'a rien à voir avec le doublement. Ajouter un seul élément multiplie le coût par le nouveau compte : le vingt et unième élément coûte vingt et une fois tout le problème à vingt. C'est pourquoi un voyageur de commerce exact sur vingt villes fait 2,4 millions de millions de millions d'étapes, soit soixante-dix-sept ans à un milliard par seconde, alors que ces mêmes vingt villes en deux puissance n se terminent en un millième de seconde.
Cela explique aussi pourquoi l'écart entre classes est ennuyeux aux petites tailles et brutal aux grandes. À dix éléments, n log n et n au carré sont à trois fois l'un de l'autre, ce qu'aucun utilisateur ne remarquerait. À mille éléments, ils sont à cent fois, et à un million, à cinquante mille fois. Les deux mêmes algorithmes, le même code, rien de changé sinon l'entrée.
Autrement dit, la lecture honnête d'une classe de complexité est une promesse sur la forme de la courbe, pas sur la vitesse. Elle dit comment le coût réagit quand l'entrée grandit, et ne dit strictement rien sur le fait que ce soit rapide aujourd'hui, sur votre machine, à la taille que vous avez vraiment.
Une meilleure classe de complexité veut-elle dire un programme plus rapide ?
Pas à votre taille, pas nécessairement. La classe décrit comment le coût réagit quand l'entrée grandit ; elle ne dit rien du travail à l'intérieur de chaque étape, et c'est précisément ce travail que la notation jette.
Avec les chiffres par lesquels cette page commence, l'algorithme quadratique à constante légère bat celui en n log n à constante cinquante pour toute entrée sous 439 éléments. Au-dessus, la meilleure classe prend le large et ne rend plus jamais la tête.
Pourquoi cette page ne lit-elle pas mon code ?
Parce que deviner une complexité à partir du source est une conjecture déguisée en mesure. Une boucle peut s'interrompre, un appel à l'intérieur peut cacher le vrai coût, et la récursion se lit rarement pour ce qu'elle fait.
Ici, la classe est donc votre saisie, pas l'avis de la page. Tout ce qui en découle est de l'arithmétique exacte, et rien sur cette page ne prétend savoir ce que fait votre boucle.
Que se passe-t-il réellement quand l'entrée double ?
Le travail linéaire double et le quadratique quadruple, ce que la plupart des gens ont en tête. L'exponentiel est élevé au carré, ce que presque personne n'a en tête : à mille éléments, doubler l'entrée multiplie le coût par deux puissance mille.
La factorielle ne fonctionne même pas ainsi. Ajouter un seul élément multiplie le coût par le nouveau compte : le vingt et unième élément coûte vingt et une fois tout le problème à vingt.
| Classe | Multiplié par quand l'entrée double, à mille éléments |
|---|---|
| O(n) | 2 |
| O(n log n) | 2,2 |
| O(n²) | 4 |
| O(n³) | 8 |
| O(2ⁿ) | 1,07 x 10^301 |
Pourquoi un voyageur de commerce exact est-il impossible à vingt villes ?
Parce que factorielle vingt fait 2,4 millions de millions de millions d'étapes, soit soixante-dix-sept ans à un milliard d'opérations par seconde. Ces mêmes vingt éléments en deux puissance n prennent environ un millième de seconde.
C'est la différence pratique entre exponentiel et factoriel, et c'est pourquoi il vaut la peine de les distinguer plutôt que de les classer tous deux comme impossibles.
Réactions
0
0 commentaires
Soyez le premier à commenter