Explosion exponentielle pour n égal 50
Pour n = 50, O(2^n) demande environ 10^15 opérations : plus de dix jours à un milliard d'opérations par seconde.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
- Taille n
- 50
- Vitesse supposée
- 1 000 000 000 opérations par seconde
| Complexité | Opérations | Durée |
|---|---|---|
| O(1) | 1 | 1 ns |
| O(log n) | 6 | 5,64 ns |
| O(n) | 50 | 50 ns |
| O(n log n) | 282 | 282,19 ns |
| O(n²) | 2 500 | 2,5 µs |
| O(n³) | 125 000 | 125 µs |
| O(2^n) | 1,13 × 10¹⁵ | 13 jours |
Le cas en détail
Un algorithme exponentiel double sa durée à chaque élément ajouté. Avec 50 éléments, il faut plus d'un million de milliards d'opérations. À 60 éléments, on dépasse trente ans. Aucun matériel n'y change grand-chose.
À retenir : Quand un problème paraît exiger une énumération de toutes les possibilités, cherchez une autre approche.
L'exemple chiffré
Valeurs utilisées dans ce cas (des exemples, pas des mesures) :
- Taille des données (n) : 50
- Opérations par seconde : 1000000000
- Taille n
- 50
- Vitesse supposée
- 1 000 000 000 opérations par seconde
| Complexité | Opérations | Durée |
|---|---|---|
| O(1) | 1 | 1 ns |
| O(log n) | 6 | 5,64 ns |
| O(n) | 50 | 50 ns |
| O(n log n) | 282 | 282,19 ns |
| O(n²) | 2 500 | 2,5 µs |
| O(n³) | 125 000 | 125 µs |
| O(2^n) | 1,13 × 10¹⁵ | 13 jours |
Modifiez les champs ci-dessus pour adapter le calcul à votre situation : le résultat se met à jour tout de suite.
Comment ça se calcule
Pour chaque classe de complexité, l'outil évalue la formule pour votre n (log n en base 2, n log n, n au carré, au cube, 2 puissance n) puis divise par le nombre d'opérations par seconde que vous indiquez. Ce sont des ordres de grandeur : les constantes réelles d'un programme ne sont pas prises en compte.
Les résultats sont fournis à titre indicatif, sans valeur de conseil juridique, fiscal ou financier.