Une machine dix fois plus rapide change-t-elle tout ?
Comparez les durées pour n = 10 000 à 10 milliards d'opérations par seconde : O(n²) reste notable.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
- Taille n
- 10 000
- Vitesse supposée
- 10 000 000 000 opérations par seconde
| Complexité | Opérations | Durée |
|---|---|---|
| O(1) | 1 | 0,1 ns |
| O(log n) | 13 | 1,33 ns |
| O(n) | 10 000 | 1 µs |
| O(n log n) | 132 877 | 13,29 µs |
| O(n²) | 100 000 000 | 10 ms |
| O(n³) | 1 000 000 000 000 | 1 min 40 s |
| O(2^n) | 2 × 10³⁰¹⁰ | environ 10²⁹⁹³ ans |
Le cas en détail
Un processeur plus rapide divise toutes les durées par le même facteur, mais ne change pas leur croissance. Un algorithme en n² reste quadratique : doubler les données quadruple toujours le travail. Améliorer l'algorithme rapporte plus que changer de machine.
À retenir : Avant d'acheter du matériel, cherchez d'abord à améliorer l'algorithme.
L'exemple chiffré
Valeurs utilisées dans ce cas (des exemples, pas des mesures) :
- Taille des données (n) : 10000
- Opérations par seconde : 10000000000
- Taille n
- 10 000
- Vitesse supposée
- 10 000 000 000 opérations par seconde
| Complexité | Opérations | Durée |
|---|---|---|
| O(1) | 1 | 0,1 ns |
| O(log n) | 13 | 1,33 ns |
| O(n) | 10 000 | 1 µs |
| O(n log n) | 132 877 | 13,29 µs |
| O(n²) | 100 000 000 | 10 ms |
| O(n³) | 1 000 000 000 000 | 1 min 40 s |
| O(2^n) | 2 × 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.