Trois boucles imbriquées de 20 tours
Trois boucles de 20 tours chacune exécutent le corps 8 000 fois.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
- Nombre d'exécutions de action()
- 8 000
- Ordre de grandeur
- O(n × m × p)
pour i de 0 à n-1
pour j de 0 à m-1
pour k de 0 à p-1
action()Le cas en détail
Chaque boucle supplémentaire multiplie le travail par sa taille : 20 × 20 × 20 = 8 000. Avec 1 000 à chaque niveau, on atteindrait un milliard. Les boucles triples demandent donc une attention particulière.
À retenir : Si une triple boucle ralentit, cherchez si une des trois peut être remplacée par une recherche plus directe.
L'exemple chiffré
Valeurs utilisées dans ce cas (des exemples, pas des mesures) :
- Schéma de boucles : Trois boucles indépendantes (n × m × p)
- Valeur de n : 20
- Valeur de m : 20
- Valeur de p : 20
- Nombre d'exécutions de action()
- 8 000
- Ordre de grandeur
- O(n × m × p)
pour i de 0 à n-1
pour j de 0 à m-1
pour k de 0 à p-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.