Exercices — La complexité algorithmique

Pr. EL HADIQ Zouhair

6 exercices Python progressifs sur le calcul de complexité. Une solution modèle et la complexité sont données pour chaque exercice.

Conseil. Cherchez d'abord la solution seul(e), puis comparez. Pour chaque fonction, demandez-vous : combien d'opérations en fonction de n ? Quelle est la complexité dans le pire des cas ?

Écrire une fonction somme(n) qui renvoie la somme des entiers de 1 à n à l'aide d'une boucle.

somme(5)   → 15
somme(100) → 5050
somme(0)   → 0

Solution :

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

Complexité : la boucle effectue n tours → O(n) (temps), O(1) (espace).

Écrire recherche(liste, x) qui renvoie l'indice de la première occurrence de x, ou −1 si x est absent.

recherche([4, 8, 15, 16], 15) → 2
recherche([4, 8, 15], 99)     → -1
recherche([7, 7, 7], 7)       → 0

Solution :

def recherche(liste, x):
    for i in range(len(liste)):
        if liste[i] == x:
            return i
    return -1

Complexité : meilleur cas O(1) (1ʳᵉ position), pire cas O(n) (absent).

Écrire nb_operations(n) qui renvoie, sans boucle, le nombre de fois où le corps de la double boucle for i in range(n): for j in range(n): est exécuté.

nb_operations(3)  → 9
nb_operations(10) → 100
nb_operations(0)  → 0

Solution :

def nb_operations(n):
    return n * n

Complexité : le corps s'exécute n × n = n² fois → O(n²).

Pour une liste triée par ordre croissant, écrire dichotomie(liste, x) qui renvoie un indice de x, ou −1 si absent.

dichotomie([1, 3, 5, 7, 9], 7) → 3
dichotomie([1, 3, 5, 7, 9], 4) → -1
dichotomie([2, 4, 6], 2)       → 0

Solution :

def dichotomie(liste, x):
    g, d = 0, len(liste) - 1
    while g <= d:
        m = (g + d) // 2
        if liste[m] == x:
            return m
        elif liste[m] < x:
            g = m + 1
        else:
            d = m - 1
    return -1

Complexité : l'intervalle est divisé par 2 à chaque étape → O(log n).

Écrire une fonction récursive fact(n) qui renvoie la factorielle de n (avec fact(0) = 1).

fact(0) → 1
fact(5) → 120
fact(6) → 720

Solution :

def fact(n):
    if n <= 1:
        return 1
    return n * fact(n - 1)

Complexité : T(n) = T(n−1) + O(1) → O(n) en temps et en espace (pile d'appels).

La version récursive naïve de Fibonacci est en O(2ⁿ). Écrire une fonction itérative fibo(n) en O(n), avec fibo(0) = 0 et fibo(1) = 1.

fibo(0)  → 0
fibo(1)  → 1
fibo(10) → 55

Solution :

def fibo(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Complexité : une seule boucle de n tours → O(n), contre O(2ⁿ) pour la version récursive naïve.