Complexité pour un million d'éléments
Pour un million d'éléments, O(n²) demande mille milliards d'opérations : environ un quart d'heure.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
- Taille n
- 1 000 000
- Vitesse supposée
- 1 000 000 000 opérations par seconde
| Complexité | Opérations | Durée |
|---|---|---|
| O(1) | 1 | 1 ns |
| O(log n) | 20 | 19,93 ns |
| O(n) | 1 000 000 | 1 ms |
| O(n log n) | 19 931 569 | 19,93 ms |
| O(n²) | 1 000 000 000 000 | 16 min 40 s |
| O(n³) | 1 × 10¹⁸ | 31,7 ans |
| O(2^n) | 9,9 × 10³⁰¹⁰²⁹ | environ 10³⁰¹⁰¹³ ans |
Le cas en détail
n au carré vaut 10^12 pour n = 1 000 000. À un milliard d'opérations par seconde, cela fait 1 000 secondes. O(n log n), lui, ne demande que 20 millions d'opérations, soit 20 millisecondes. L'écart se compte en milliers de fois.
À retenir : Un algorithme quadratique devient un problème bien avant le million d'éléments : surveillez-le dès quelques dizaines de milliers.
L'exemple chiffré
Valeurs utilisées dans ce cas (des exemples, pas des mesures) :
- Taille des données (n) : 1000000
- Opérations par seconde : 1000000000
- Taille n
- 1 000 000
- Vitesse supposée
- 1 000 000 000 opérations par seconde
| Complexité | Opérations | Durée |
|---|---|---|
| O(1) | 1 | 1 ns |
| O(log n) | 20 | 19,93 ns |
| O(n) | 1 000 000 | 1 ms |
| O(n log n) | 19 931 569 | 19,93 ms |
| O(n²) | 1 000 000 000 000 | 16 min 40 s |
| O(n³) | 1 × 10¹⁸ | 31,7 ans |
| O(2^n) | 9,9 × 10³⁰¹⁰²⁹ | environ 10³⁰¹⁰¹³ ans |
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.