informatique (tronc commun des prépas scientifiques) · Chapitre 3 · Application directe du cours

Compter les tours

Boucles imbriquées et complexité quadratique · niveau 1 (application)

É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})$ .

Exercices semblables

Compter les inversions corrigé
Le pire cas de la recherche de facteur, exactement corrigé
Le tri à bulles ne déplace qu'à petits pas corrigé
Tous distincts ? corrigé
Toutes les occurrences d'un facteur corrigé

Le cours du chapitre · Tous les exercices du chapitre