Boucles logarithmiques — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 10)

Boucles logarithmiques

Complexité des programmes · niveau 1 (application)

Énoncé

Donner le nombre exact de tours de chacune des boucles suivantes ( $n \geq 1$ ), puis sa complexité.


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

Corrigé

$i$ vaut $n$ , $⌊ n /2 ⌋$ , $⌊ n /4 ⌋$ , …, $1$ puis $0$ : la boucle fait $⌊ lo g_{2} n ⌋ + 1$ tours, complexité $Θ (lo g n)$ .
La boucle tourne tant que $i^{2} \leq n$ : $⌊ n ⌋$ tours, complexité $Θ (n)$ .
$j$ vaut $1, 3, 9, \dots$ tant que $j < n$ : $⌈ lo g_{3} n ⌉$ tours, complexité $Θ (lo g n)$ (la base du logarithme ne change pas l'ordre de grandeur).
$⌈ lo g_{2} n ⌉$ tours externes de $n$ tours internes chacun : $n ⌈ lo g_{2} n ⌉$ exécutions, complexité $Θ (n lo g n)$ .

Le programme Boucles.java confirme ces formules, par exemple pour $n = 1 0^{6}$ : $20$ , $1000$ , $13$ et $20000000$ tours.