Lorsqu'on analyse un algorithme, on s'intéresse à deux ressources fondamentales : le temps et l'espace mémoire. Ces deux mesures permettent d'évaluer l'efficacité d'un algorithme et de comparer différentes solutions pour un même problème.

Définition

Complexité temporelle : mesure du temps d'exécution d'un algorithme en fonction de la taille de l'entrée.
Complexité spatiale : mesure de l'espace mémoire (ou mémoire) utilisé par un algorithme en fonction de la taille de l'entrée.

Complexité temporelle

La complexité temporelle quantifie le nombre d'opérations élémentaires effectuées par un algorithme en fonction de la taille \(n\) de l'entrée.

Opérations élémentaires

Les opérations généralement comptées sont :

Les comparaisons
Les affectations
Les opérations arithmétiques
Les accès mémoire

Exemple 1 : Recherche linéaire

Recherche linéaire Python

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

Analyse :

Meilleur cas : l'élément est en première position → 1 comparaison → \(O(1)\)
Pire cas : l'élément n'est pas présent → \(n\) comparaisons → \(O(n)\)
Cas moyen : en moyenne, \(n/2\) comparaisons → \(O(n)\)

Exemple 2 : Recherche dichotomique

Recherche dichotomique Python

def recherche_dichotomique(tab, x):
    debut, fin = 0, len(tab) - 1
    while debut <= fin:
        milieu = (debut + fin) // 2
        if tab[milieu] == x:
            return milieu
        elif tab[milieu] < x:
            debut = milieu + 1
        else:
            fin = milieu - 1
    return -1

Analyse :

À chaque étape, la taille de l'intervalle est divisée par 2
Nombre d'étapes : \(\log_2 n\)
Complexité temporelle : \(O(\log n)\)

Complexité spatiale

La complexité spatiale mesure la quantité de mémoire nécessaire à l'exécution d'un algorithme. Elle inclut :

L'espace pour les variables d'entrée
L'espace pour les variables auxiliaires (temporaires)
L'espace pour la pile d'appels récursifs

Remarque

On distingue souvent l'espace auxiliaire (mémoire supplémentaire utilisée par l'algorithme) de l'espace total (qui inclut l'entrée elle-même).

Exemple 3 : Tri par sélection

Tri par sélection Python

def tri_selection(tab):
    n = len(tab)
    for i in range(n-1):
        min_idx = i
        for j in range(i+1, n):
            if tab[j] < tab[min_idx]:
                min_idx = j
        tab[i], tab[min_idx] = tab[min_idx], tab[i]
    return tab

Analyse spatiale :

Variables utilisées : \(i, j, min\_idx, n\) → espace constant
Le tri s'effectue en place (pas de tableau supplémentaire)
Complexité spatiale : \(O(1)\) (espace auxiliaire constant)

Exemple 4 : Tri fusion

Tri fusion Python

def tri_fusion(tab):
    if len(tab) <= 1:
        return tab
    milieu = len(tab) // 2
    gauche = tri_fusion(tab[:milieu])
    droite = tri_fusion(tab[milieu:])
    return fusion(gauche, droite)

Analyse spatiale :

Création de nouveaux tableaux à chaque appel récursif
Profondeur de récursion : \(\log n\)
Taille totale des tableaux créés : \(O(n \log n)\) en version naïve
Version optimisée : \(O(n)\) espace auxiliaire

Comparaison des complexités

Algorithme	Complexité temporelle	Complexité spatiale	Caractéristique
Recherche linéaire	\(O(n)\)	\(O(1)\)	Simple, ne nécessite pas de tri préalable
Recherche dichotomique	\(O(\log n)\)	\(O(1)\)	Nécessite un tableau trié
Tri par sélection	\(O(n^2)\)	\(O(1)\)	Tri en place, simple mais lent
Tri fusion	\(O(n \log n)\)	\(O(n)\)	Efficace mais nécessite mémoire supplémentaire
Tri rapide	\(O(n \log n)\) en moyenne	\(O(\log n)\)	En place, très efficace en pratique

Compromis temps-mémoire

Trade-off classique

Il existe souvent un compromis entre la complexité temporelle et la complexité spatiale :

Utiliser plus de mémoire peut permettre d'accélérer un algorithme (ex: mémoïsation, programmation dynamique).
Réduire l'utilisation mémoire peut ralentir l'exécution (ex: algorithmes en place).

Exemple 5 : Calcul de Fibonacci

def fibo_rec(n):
    if n <= 1:
        return n
    return fibo_rec(n-1) + fibo_rec(n-2)

Analyse :

Temps : \(O(2^n)\) (exponentiel)
Espace : \(O(n)\) (pile de récursion)

def fibo_dp(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Analyse :

Temps : \(O(n)\) (linéaire)
Espace : \(O(n)\) (tableau)

Conclusion sur Fibonacci

La version récursive naïve utilise peu de mémoire supplémentaire (hors pile) mais est exponentielle en temps. La version dynamique utilise un tableau pour stocker les résultats intermédiaires, passant ainsi de \(O(2^n)\) à \(O(n)\) en temps, au prix d'un espace \(O(n)\).

Sortie

// La sortie apparaîtra ici…

Prêt · Ctrl+Entrée pour exécuter

Complexité temporelle et spatiale

Types de complexité