Compter des tours de boucle — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 10)

Compter des tours de boucle

Complexité des programmes · niveau 2

Énoncé

Donner, en fonction de $n$ , le nombre exact d'exécutions de l'instruction c++ dans chacun des deux fragments, puis leur complexité.


for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)
        for (int k = i; k < j; k++) c++;

for (int i = 1; i < n; i = 2 * i)
    for (int j = 0; j < i; j++) c++;

Vérifier les réponses en programmant ces boucles avec un compteur.

Corrigé

Premier fragment. Pour $i$ et $j$ fixés, la boucle sur $k$ fait $j - i$ tours. Posons $d = j - i$ : pour chaque $d \in [1 : n]$ , il y a $n - d$ couples $(i, j)$ tels que $j - i = d$ . Le nombre total est donc

$d = 1 \sum n - 1 d (n - d) = n \frac{( n - 1 ) n}{2} - \frac{( n - 1 ) n ( 2 n - 1 )}{6} = \frac{n ( n ^{2} - 1 )}{6} \in Θ (n^{3}) .$

Second fragment. La variable $i$ prend les valeurs $1, 2, 4, \dots, 2^{m - 1}$ , où $m = ⌈ lo g_{2} n ⌉$ est le nombre de tours de la boucle externe ( $n \geq 2$ ). La boucle interne fait $i$ tours, d'où $1 + 2 + \dots + 2^{m - 1} = 2^{m} - 1$ exécutions. Comme $n \leq 2^{m} < 2 n$ , on a $n - 1 \leq 2^{m} - 1 < 2 n$ : la complexité est $Θ (n)$ , et non $Θ (n lo g n)$ comme on pourrait le croire en multipliant « $lo g n$ tours externes » par « au plus $n$ tours internes ».

Vérification (programme Boucles.java) :


     n   triple  n(n²-1)/6  doubl.  2^ceil(log2 n)-1
     1        0          0       0       0
     2        1          1       1       1
     5       20         20       7       7
    10      165        165      15      15
   100   166650     166650     127     127
  1000 166666500  166666500    1023    1023