Comptage d'opérations élémentaires — exercice corrigé de Python (école d'ingénieur) (chapitre 6)

Comptage d'opérations élémentaires

Complexité algorithmique

Énoncé

Pour chacune des fonctions suivantes, déterminer le nombre exact d'opérations élémentaires (additions, comparaisons, affectations) en fonction de $n$ , puis donner la complexité asymptotique $Θ$ .

def max_liste(L):
    max_val = L[0]
    for x in L:
        if x > max_val:
            max_val = x
    return max_val

def somme_pairs(n):
    s = 0
    for i in range(2, n+1, 2):
        s += i
    return s

def mystere(n):
    i, j = 1, 1
    while i <= n:
        j = 1
        while j <= n:
            j += 1
        i += 1

Corrigé

Analysons chaque fonction :

Fonction max_liste(L) avec $n = len (L)$ :

Initialisation : max_val = L[0] (1 accès, 1 affectation).

Boucle for : $n$ itérations.

À chaque itération : 1 accès à x, 1 comparaison x > max_val.

Si la condition est vraie : 1 affectation max_val = x.

Retour : return max_val (1 opération).

Dans le pire des cas (liste triée par ordre strictement croissant), la condition du test est vraie à chaque itération. Le nombre total d'opérations est linéaire en $n$ . La complexité asymptotique est : $Θ (n)$ .

Fonction somme_pairs(n) :

Initialisation : s = 0 (1 affectation).

Boucle for i in range(2, n+1, 2) : $⌊ n /2 ⌋$ itérations.

À chaque itération : 1 addition/affectation s += i.

Retour : return s (1 opération).

Le nombre total d'itérations est $\frac{n}{2} + O (1)$ . La complexité asymptotique est : $Θ (n)$ .

Fonction mystere(n) :

Initialisation : i, j = 1, 1 (2 affectations).

Boucle externe while i <= n : $n$ itérations.

À chaque itération de la boucle externe, la variable j est réinitialisée à 1 (j = 1).

Boucle interne while j <= n : effectue $n$ itérations par passage externe.

Le nombre total d'itérations de la boucle interne est $n \times n = n^{2}$ . La complexité asymptotique est : $Θ (n^{2})$ .