Deux boucles imbriquées : 100 fois 50
Une boucle de 100 tours contenant une boucle de 50 tours exécute son corps 5 000 fois.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
- Nombre d'exécutions de action()
- 5 000
- Ordre de grandeur
- O(n × m)
pour i de 0 à n-1
pour j de 0 à m-1
action()Le cas en détail
Les boucles sont indépendantes : pour chacun des 100 tours extérieurs, la boucle intérieure fait 50 tours. Le total est la multiplication, 100 × 50 = 5 000. Si les deux valent n, on obtient n au carré.
À retenir : Pour estimer, multipliez simplement les nombres de tours des boucles emboîtées.
L'exemple chiffré
Valeurs utilisées dans ce cas (des exemples, pas des mesures) :
- Schéma de boucles : Deux boucles indépendantes (n × m)
- Valeur de n : 100
- Valeur de m : 50
- Nombre d'exécutions de action()
- 5 000
- Ordre de grandeur
- O(n × m)
pour i de 0 à n-1
pour j de 0 à m-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.