Complexité temporelle et spatiale des algorithmes itératifs

1. Modèle de calcul et coût des opérations

Pour analyser un algorithme, nous devons d'abord définir ce que nous comptons. Nous ne mesurons pas le temps en secondes, mais en nombre d'opérations élémentaires. Nous faisons l'hypothèse que notre algorithme s'exécute sur une machine idéalisée (souvent appelée modèle RAM - Random Access Machine) où certaines opérations de base ont un coût constant, que nous notons $O(1)$.

La question devient alors : quelles opérations sont considérées comme élémentaires ?

En résumé, vous pouvez considérer les opérations suivantes comme coûtant $O(1)$ :

• Affectation de variable (x = 5, c = c + 1)
• Opérations arithmétiques (+, -, *, /)
• Comparaisons (==, <, >)
• Instructions de contrôle (if, for, while - l'instruction elle-même, pas le bloc qu'elle exécute)
• Accès à un élément de liste par son indice (t[i])
• Appel à len(t) sur une liste.

Avec ce catalogue, nous pouvons définir plus formellement nos deux mesures de complexité :

• Complexité temporelle : C'est une fonction qui lie la taille de l'entrée, notée $n$, au nombre d'opérations élémentaires exécutées par l'algorithme dans le pire des cas.
• Complexité spatiale : C'est une fonction qui lie la taille de l'entrée $n$ à la quantité de mémoire supplémentaire (en plus de celle requise pour stocker l'entrée) utilisée par l'algorithme.

Par défaut, et c'est la convention à l'Agrégation, lorsque l'on demande "la complexité", il s'agit de la complexité temporelle asymptotique dans le pire des cas.

2. Une méthode systématique pour le calcul

Analyser la complexité d'un algorithme itératif n'est pas un art divinatoire ; c'est une procédure systématique qui repose sur quelques règles simples pour combiner les coûts des opérations de base.

La vidéo suivante expose ces règles de manière très claire et pédagogique.

Synthétisons ces règles fondamentales :

1. Séquence d'instructions : Si un bloc d'instructions A est suivi d'un bloc B, la complexité de la séquence est le maximum des deux.
   $\text{Complexiteˊ}(A;B)=\max (\text{Complexiteˊ}(A),\text{Complexiteˊ}(B))$
   En notation asymptotique, cela revient à une somme, car le terme dominant absorbe les autres : $O(f(n))+O(g(n))=O(\max (f(n),g(n)))$. Par exemple, $O(n^2)+O(n)=O(n^2)$.

2. Instruction conditionnelle : Pour un if-else, la complexité dans le pire des cas est celle du test, plus la complexité de la branche la plus coûteuse.
   $\text{Complexiteˊ}(\text{if C then A else B})=\text{Complexiteˊ}(C)+\max (\text{Complexiteˊ}(A),\text{Complexiteˊ}(B))$

3. Boucle : La complexité d'une boucle est (approximativement) le nombre d'itérations multiplié par la complexité (dans le pire des cas) du corps de la boucle. C'est la règle la plus importante.
   $\text{Complexiteˊ}(\text{for i=1 to N do A})=N\times \text{Complexiteˊ}(A)$

3. Exemples d'application

Appliquons cette méthode à des algorithmes Python concrets.

Exemple 1 : Complexité Linéaire O(n) et Spatiale O(1)

Considérons une fonction simple qui cherche le nombre d'occurrences d'un élément dans une liste. C'est l'exemple nbre_occurrences du document LINK.

def nbre_occurrences(x, t):



    # n = len(t) est la taille de l'entrée
    
    c = 0                   # 1. Coût O(1)
    
    for i in range(len(t)): # 2. Boucle exécutée n fois
        if t[i] == x:       # 3. Corps de la boucle, coût O(1)
            c = c + 1       # 4. (partie du corps)
            
    return c                # 5. Coût O(1)

Analyse de la complexité temporelle :

• Ligne 1 (c = 0): Une affectation, coût $O(1)$.
• Ligne 2 (for...): La boucle s'exécute $n$ fois, où $n=\text{len}(t)$.
• Ligne 3 (if...): À l'intérieur de la boucle, le test t[i] == x implique un accès (t[i]) et une comparaison (==), les deux sont $O(1)$. Si le test est vrai, la ligne 4 (c = c+1) coûte aussi $O(1)$. Le corps de la boucle a donc une complexité de $O(1)$ dans le pire des cas.
• Ligne 5 (return c): Coût $O(1)$.

La complexité totale est la somme des complexités séquentielles : $O(1)+(n\times O(1))+O(1)$.
Le terme dominant est $n\times O(1)=O(n)$.
Donc, la complexité temporelle de l'algorithme est $\Theta (n)$.

Analyse de la complexité spatiale :
Nous devons compter la mémoire supplémentaire allouée.

• L'entrée t et x ne compte pas.
• L'algorithme utilise deux variables : c (un entier) et i (l'index de la boucle).
  La taille de ces variables ne dépend pas de la taille n de la liste. La mémoire utilisée est constante.
  La complexité spatiale est donc $\Theta (1)$.

Exemple 2 : Complexité Quadratique O(n²)

Analysons deux cas de boucles imbriquées (inspirés de f1 et f2 dans LINK).

Cas A : Boucles carrées

def f1(n):
    x = 0
    for i in range(n):      # Boucle externe: n itérations
        for j in range(n):  # Boucle interne: n itérations
            x += 1          # Coût O(1)
    return x

La boucle interne exécute une opération $O(1)$, $n$ fois. Son coût est donc $O(n)$.
La boucle externe exécute cette boucle interne (de coût $O(n)$), $n$ fois.
La complexité totale est $n\times O(n)=O(n^2)$.

Cas B : Boucles triangulaires

def f2(n):
    x = 0
    for i in range(n):      # Boucle externe: n itérations
        for j in range(i):  # Boucle interne: i itérations
            x += 1          # Coût O(1)
    return x

Ici, le nombre d'itérations de la boucle interne dépend de la variable i de la boucle externe.

• Quand i = 0, la boucle interne fait 0 tour.
• Quand i = 1, la boucle interne fait 1 tour.
• ...
• Quand i = n-1, la boucle interne fait n-1 tours.

Le nombre total d'exécutions de x += 1 est la somme $0+1+2+\cdots +(n-1)$. C'est la somme d'une série arithmétique :

Cette fonction est bien $\Theta (n^2)$. La complexité est quadratique, même si le nombre d'opérations est environ la moitié du cas précédent.

Exemple 3 : Complexité Logarithmique O(log n)

Considérons une boucle où la variable de contrôle est divisée à chaque étape (inspiré de f3 dans LINK).

def f3(n):
    x, i = 0, n
    while i > 1:    # Combien d'itérations?
        x += 1      # Coût O(1)
        i //= 2     # Division entière par 2
    return x

La question est : combien de fois peut-on diviser n par 2 avant d'atteindre 1 ?
Soit $k$ le nombre d'itérations. Les valeurs successives de i sont approximativement $n,n/2,n/4,\dots ,n/2^k$.
La boucle s'arrête lorsque $i\le 1$, c'est-à-dire $n/2^k\le 1$.

Le nombre d'itérations $k$ est donc de l'ordre de ${\log }_2(n)$. Comme le corps de la boucle est en $O(1)$, la complexité temporelle est $\Theta (\log n)$.

Exercice

Mettez en pratique la méthode sur cet algorithme (inspiré de f4 dans LINK). Quelle est sa complexité temporelle dans le pire des cas ?

def f4(n):
    x, i = 0, n
    while i > 1:
        for j in range(n):
            x += 1
        i //= 2
    return x

Analysez-le pas à pas :

1. Identifiez la boucle externe (while) et la boucle interne (for).
2. Calculez la complexité de la boucle interne.
3. Déterminez combien de fois la boucle externe s'exécute.
4. Combinez les deux pour trouver la complexité totale.

Conclusion

Aujourd'hui, nous avons franchi une étape cruciale en appliquant nos outils mathématiques à du code. Vous avez appris une méthode systématique pour analyser la performance d'algorithmes itératifs.

Points clés à retenir :

• Le calcul de complexité repose sur un modèle d'opérations élémentaires coûtant $O(1)$.
• La complexité temporelle est le nombre de ces opérations en fonction de la taille de l'entrée $n$, dans le pire des cas.
• La complexité spatiale mesure la mémoire additionnelle requise.
• L'analyse se fait systématiquement en combinant les coûts des séquences (max), conditions (max des branches) et boucles (produit).

Dans notre prochaine leçon, nous changerons de perspective. Après avoir analysé la performance d'un algorithme ("à quelle vitesse s'exécute-t-il ?"), nous nous demanderons s'il produit le bon résultat ("fonctionne-t-il ?"). Pour cela, vous découvrirez un outil formel puissant pour prouver la correction d'un algorithme itératif : l'invariant de boucle.