Complexité algorithmique

6.1 Introduction et Motivation

Déterminer la complexité d'un algorithme (aussi appelée son coût) consiste à évaluer les ressources nécessaires à son exécution : essentiellement le temps de calcul et, dans une moindre mesure, la quantité de mémoire requise. Ces besoins dépendent de nombreux paramètres matériels (puissance du processeur, vitesse d'accès à la mémoire) qui sortent du domaine théorique de l'informatique.

Il est donc impossible d'attribuer une valeur absolue (en secondes ou en octets) à un algorithme. En revanche, nous pouvons évaluer son ordre de grandeur de croissance en fonction de la taille de l'entrée. Cela permet d'identifier l'algorithme le plus efficace parmi plusieurs résolvant le même problème.

Considérons un exemple concret : la recherche du nombre de diviseurs d'un entier naturel $n$.

def diviseurs1(n):
    d = 0
    k = 1
    while k <= n:
        if n % k == 0:
            d += 1
        k += 1
    return d

def diviseurs2(n):
    d = 0
    k = 1
    while k * k < n:
        if n % k == 0:
            d += 2
        k += 1
    if k * k == n:
        d += 1
    return d

Dans diviseurs1, la boucle s'exécute $n$ fois. Le temps d'exécution est proportionnel à $n$. Si on multiplie $n$ par 100, le temps de calcul est multiplié par 100 (complexité linéaire).

Dans diviseurs2, on exploite le fait que si $d$ divise $n$, alors $d^{\prime }=n/d$ divise aussi $n$. L'un de ces deux diviseurs est inférieur ou égal à $\sqrt{n}$. Il suffit donc de chercher les diviseurs inférieurs ou égaux à $\sqrt{n}$, la boucle s'exécutant $\lfloor \sqrt{n}\rfloor -1$ fois. Le temps d'exécution est proportionnel à $\sqrt{n}$. Si on multiplie $n$ par 100, le temps n'est multiplié que par 10 (complexité en racine carrée).

6.2 Modèle de Calcul et Instructions Élémentaires

Pour évaluer la complexité d'un algorithme de manière uniforme, on définit un modèle de calcul (généralement la machine RAM à processeur unique) où certaines opérations de base, dites instructions élémentaires, ont un coût constant (noté $\Theta (1)$) indépendant de leurs opérandes. Parmi elles :

• Les opérations arithmétiques basiques (+, -, *, /, %, //).
• Les comparaisons (==, !=, <, >, <=, >=).
• Les opérations logiques (and, or, not).
• Les transferts de données (lecture/écriture dans une case mémoire ou une variable).
• Les instructions de contrôle (branchements conditionnels, retours de fonctions).

L = list(range(1000))
x = L[500]           # O(1) : accès indexé (tableau dynamique)
x = L.index(500)     # O(n) : parcourt la liste jusqu'à trouver 500
print(500 in L)      # O(n) : parcourt toute la liste dans le pire cas
copie = L[100:200]   # O(k) : crée une nouvelle liste de taille k (copie!)
L.sort()             # O(n log n) : tri en place

6.3 Notations de Landau ($O$, $\Omega$, $\Theta$, $o$)

Soit $f(n)$ le nombre d'instructions élémentaires exécutées par un algorithme pour une entrée de taille $n$. Pour exprimer son comportement asymptotique (quand $n$ devient grand), on utilise les notations suivantes :

6.3.1 Échelles de Complexité

Le tableau suivant illustre la différence d'échelle colossale du temps de calcul théorique requis pour différents types de complexité, sur une base matérielle de $10^9$ opérations par seconde (1 GHz) :

On qualifie classiquement les complexités de la façon suivante :

6.3.2 Complexités des Structures de Données Python

Le tableau suivant récapitule les complexités temporelles des opérations courantes sur les structures de données natives de Python :