Boucle triangulaire pour n égal 1 000
Une boucle intérieure qui s'arrête à i exécute son corps 499 500 fois pour n = 1 000.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
- Nombre d'exécutions de action()
- 499 500
- Ordre de grandeur
- O(n²)
pour i de 0 à n-1
pour j de 0 à i-1
action()Le cas en détail
La somme 0 + 1 + 2 + ... + 999 vaut 999 × 1000 / 2 = 499 500. C'est presque la moitié de 1 000 × 1 000. On parle encore de complexité quadratique, car le nombre de tours croît comme le carré de n.
À retenir : Ce schéma apparaît quand on compare chaque paire d'éléments d'une liste : n (n - 1) / 2 paires.
L'exemple chiffré
Valeurs utilisées dans ce cas (des exemples, pas des mesures) :
- Schéma de boucles : Boucle intérieure limitée par i (triangle)
- Valeur de n : 1000
- Nombre d'exécutions de action()
- 499 500
- Ordre de grandeur
- O(n²)
pour i de 0 à n-1
pour j de 0 à i-1
action()Modifiez les champs ci-dessus pour adapter le calcul à votre situation : le résultat se met à jour tout de suite.
Comment ça se calcule
Une boucle double exécute n × m fois son corps. Si la boucle intérieure s'arrête à i, on additionne 0 + 1 + ... + (n - 1) = n (n - 1) / 2. Une boucle dont la variable double à chaque tour s'exécute plafond(log2 n) fois. Le pseudo-code affiché correspond exactement au schéma choisi.
Les résultats sont fournis à titre indicatif, sans valeur de conseil juridique, fiscal ou financier.