Une boucle qui double sa variable : 1 000 000

Une boucle dont la variable double à chaque tour s'exécute 20 fois pour n = 1 000 000.

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

Nombre d'exécutions de action()
20
Ordre de grandeur
O(log n)
i = 1
tant que i < n
  action()
  i = i × 2

Le cas en détail

La variable passe de 1 à 2, 4, 8... jusqu'à dépasser n. Il faut 20 doublements pour atteindre un million. C'est la signature d'une complexité logarithmique, très économe.

À retenir : Dès que vous divisez ou multipliez la variable de boucle par un facteur constant, pensez logarithme.

L'exemple chiffré

Valeurs utilisées dans ce cas (des exemples, pas des mesures) :

  • Schéma de boucles : Une boucle qui double sa variable
  • Valeur de n : 1000000
Nombre d'exécutions de action()
20
Ordre de grandeur
O(log n)
i = 1
tant que i < n
  action()
  i = i × 2

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.

Pour aller plus loin