Compter les tours

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 3 — Boucles imbriquées et complexité quadratique

Énoncé

Déterminer le nombre exact d'itérations du corps de la boucle interne puis la complexité asymptotique pour les trois cas suivants :

# (a)
for i in range(n):
    for j in range(10):
        # O(1)

# (b)
for i in range(n):
    for j in range(i):
        # O(1)

# (c)
for i in range(n):
    for j in range(i, n):
        # O(1)

Corrigé

(a) : La boucle interne effectue toujours 10 passages. Le nombre d'itérations est $10 n$ . La complexité est linéaire $O (n)$ .
(b) : Le nombre d'itérations est $\sum_{i = 0}^{n - 1} i = \frac{n ( n - 1 )}{2}$ . La complexité est quadratique $O (n^{2})$ .
(c) : Le nombre d'itérations est $\sum_{i = 0}^{n - 1} (n - i) = n + (n - 1) + \dots + 1 = \frac{n ( n + 1 )}{2}$ . La complexité est également quadratique $O (n^{2})$ .

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.