Une boucle linéaire contenant une boucle qui double

Pour n = 1 024, une boucle de n tours contenant une boucle qui double s'exécute 10 240 fois.

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

Nombre d'exécutions de action()
10 240
Ordre de grandeur
O(n log n)
pour i de 0 à n-1
  j = 1
  tant que j < n
    action()
    j = j × 2

Le cas en détail

La boucle intérieure fait 10 tours (2^10 = 1 024) pour chacun des 1 024 tours extérieurs : 10 240 au total. C'est une complexité en n log n, la même que celle des meilleurs tris.

À retenir : n log n est le seuil de ce qu'on peut raisonnablement faire sur de très gros volumes.

L'exemple chiffré

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

  • Schéma de boucles : Boucle linéaire contenant une boucle qui double
  • Valeur de n : 1024
Nombre d'exécutions de action()
10 240
Ordre de grandeur
O(n log n)
pour i de 0 à n-1
  j = 1
  tant que j < n
    action()
    j = j × 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