Croissance d'un algorithme : nombre d'opérations

Pourquoi un programme qui marche pour 100 éléments s'effondre-t-il pour 100 000 ? Saisissez n et la vitesse de votre machine pour comparer les grandes familles de croissance.

Jimenez JulienPar , éditeur de Calepin Binaire · mis à jour le

Taille n
1 000
Vitesse supposée
1 000 000 000 opérations par seconde
ComplexitéOpérationsDurée
O(1)11 ns
O(log n)109,97 ns
O(n)1 0001 µs
O(n log n)9 9669,97 µs
O(n²)1 000 0001 ms
O(n³)1 000 000 0001 s
O(2^n)1,07 × 10³⁰¹3,4 × 10²⁸⁴ ans

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.

Questions fréquentes

Que signifie la notation O(n²) ?

Que le nombre d'opérations croît comme le carré de la taille : doubler les données multiplie le travail par quatre.

Pourquoi O(2^n) est-il inutilisable ?

Parce qu'il double à chaque élément ajouté. Dès quelques dizaines d'éléments, la durée dépasse tout ce qu'une machine peut calculer.

Cas fréquents

Des exemples déjà remplis, avec leur explication :

Intégrer cet outil sur votre site

Copiez ce code pour afficher l'outil sur votre site ou votre blog. L'outil s'exécute dans le navigateur du visiteur, sans cookie ni suivi, et affiche un lien « Propulsé par Calepin Binaire » vers cette page.

Aperçu de la version intégrable : https://mircode.org/embed/croissance-d-une-boucle-nombre-d-operations/

Les résultats sont fournis à titre indicatif. Pour aller plus loin, découvrez les sites de la catégorie Sandbox et casse-têtes de l'annuaire et lisez le guide de cette catégorie.

Autres outils

Voir les 35 outils