Six boucles, six ordres de grandeur

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 3 — Algorithmes, programmes et complexité

Énoncé

Pour chacun de ces fragments, donner le nombre exact d'exécutions de compte++ en fonction de $n$ , puis l'ordre de grandeur.


/* a */ for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) compte++;
/* b */ for (int i = 1; i < n; i = 2 * i) compte++;
/* c */ for (int i = 0; i < n; i++) compte++;
        for (int j = 0; j < n; j++) compte++;
/* d */ for (int i = 0; i < n; i++) for (int j = 0; j < 10; j++) compte++;
/* e */ for (int i = 1; i * i <= n; i++) compte++;
/* f */ for (int i = 1; i < n; i = 2 * i) for (int j = 0; j < n; j++) compte++;

Corrigé

	Nombre exact	Ordre	$n = 10$	$n = 100$	$n = 1000$	$n = 1 0^{4}$
a	$n (n - 1) /2$	$Θ (n^{2})$	$45$	$4950$	$499500$	$49995000$
b	$⌊ lo g_{2} (n - 1)⌋ + 1$	$Θ (lo g n)$	$4$	$7$	$10$	$14$
c	$2 n$	$Θ (n)$	$20$	$200$	$2000$	$20000$
d	$10 n$	$Θ (n)$	$100$	$1000$	$10000$	$100000$
e	$⌊ n ⌋$	$Θ (n)$	$3$	$10$	$31$	$100$
f	$n (⌊ lo g_{2} (n - 1)⌋ + 1)$	$Θ (n lo g n)$	$40$	$700$	$10000$	$140000$

Les quatre colonnes de droite sont mesurées : le compteur a été exécuté. C'est le seul moyen sûr de vérifier une formule qu'on vient d'écrire, et il coûte trois minutes.

Trois remarques qui valent pour tout le livre.

(a) contre (c) : deux boucles imbriquées multiplient, deux boucles successives additionnent. La confusion est la première faute de comptage, et elle se règle en regardant l'indentation.

(c) contre (d) : $2 n$ et $10 n$ sont tous deux $Θ (n)$ . La constante $5$ qui les sépare est parfaitement réelle — le programme (d) fait cinq fois plus de travail — et elle est pourtant absente de l'ordre de grandeur. C'est le prix du $Θ$ : il ne compare que des familles de courbes. L'exercice 3.9 montre ce que ce prix coûte quand on l'oublie.

(b) : la borne n'est pas incrémentée mais doublée. C'est la signature du logarithme, et on la reconnaît à l'{œ}il : si $i$ est multiplié par une constante $> 1$ à chaque tour, le nombre de tours est logarithmique. Symétriquement, en (e), $i$ croît linéairement mais la borne porte sur $i^{2}$ : le nombre de tours est en racine.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.