CPGE 2ᵉ année — MP / PSI · Informatique

La complexité algorithmique

Pr. EL HADIQ Zouhair

Estimer les ressources (temps et mémoire) nécessaires à l'exécution d'un algorithme en fonction de la taille de l'entrée, pour évaluer ses performances et anticiper ses limites.

🎯 Objectifs du chapitre

Comprendre la notion de complexité et son intérêt (choisir un algorithme).
Définir la taille du problème \(n\).
Distinguer complexité temporelle et spatiale ; meilleur et pire des cas.
Compter les opérations (méthode incrémenter & compter) et maîtriser le grand \(O\).
Calculer la complexité d'un programme itératif et récursif (récurrences, Master théorème).

Sommaire

Pourquoi mesurer la complexité ?
La taille du problème \(n\)
Complexité temporelle et complexité spatiale
Les cas d'étude : meilleur et pire des cas
Compter les opérations élémentaires
La notation asymptotique grand \(O\)
Les ordres de grandeur classiques
Complexité des programmes itératifs
Complexité des programmes récursifs
Complexité spatiale
Récapitulatif

1. Pourquoi mesurer la complexité ?

Un même problème peut être résolu par plusieurs algorithmes. Tous donnent le bon résultat, mais pas avec la même efficacité. Mesurer le temps d'exécution avec un chronomètre est trompeur : il dépend de la machine, du langage, de la charge du système et des données.

La complexité algorithmique offre une mesure objective et indépendante de la machine : elle exprime comment évoluent les ressources (temps, mémoire) lorsque la taille de l'entrée augmente. On note traditionnellement \(n\) cette taille.

💡 Idée clé. On ne cherche pas le temps exact en secondes, mais la loi de croissance : si je double la taille de l'entrée, le temps est-il doublé, quadruplé, ou presque inchangé ? Méthode : incrémenter un compteur d'opérations et le compter en fonction de \(n\).

2. La taille du problème \(n\)

La complexité s'exprime toujours en fonction d'un entier \(n\) qui mesure la taille de l'entrée. Avant tout calcul, il faut préciser ce qu'est \(n\).

Entrée	Taille \(n\)
Une liste / un tableau	\(n = \operatorname{len}(\text{liste})\) (nombre d'éléments)
Un entier \(N\)	\(n = N\), ou \(n = \log_2 N\) (nombre de bits)
Une matrice \(p \times q\)	\(n = p\,q\) (nombre de cases)
Un graphe	\(n\) = nombre de sommets (\(m\) = nombre d'arêtes)
Une chaîne de caractères	\(n\) = longueur de la chaîne

À retenir. Dans chaque calcul, on précisera explicitement \(n\) (le plus souvent \(n = \operatorname{len}(\text{liste})\)).

3. Complexité temporelle et complexité spatiale

Type	Ce qu'elle mesure
Temporelle	Le nombre d'opérations élémentaires en fonction de \(n\). Estimation du temps d'exécution.
Spatiale	La mémoire supplémentaire utilisée en fonction de \(n\) (variables, tableaux, pile d'appels récursifs).

⚠️ Compromis temps / espace. Réduire le temps augmente souvent la mémoire utilisée (et inversement). Le bon algorithme dépend de la ressource la plus contrainte.

4. Les cas d'étude : meilleur et pire des cas

Pour une même taille \(n = \operatorname{len}(\text{liste})\), le nombre d'opérations dépend du contenu. En classe préparatoire, on étudie seulement le meilleur et le pire des cas.

Meilleur des cas : la configuration la plus favorable (nombre minimal d'opérations).
Pire des cas : la configuration la plus défavorable. Il garantit une borne supérieure sur le temps.

Exemple — recherche séquentielle dans une liste de \(n\) éléments :

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

Meilleur cas : \(x\) en première position → \(O(1)\).
Pire cas : \(x\) absent → \(n\) comparaisons → \(O(n)\).

5. Compter les opérations élémentaires

Une opération élémentaire (affectation, comparaison, addition, accès à une case) a un coût constant. On compte combien de fois chaque instruction s'exécute, puis on additionne.

def somme(n):
    s = 0          # 1 affectation
    for i in range(1, n+1):   # n itérations
        s = s + i  # 2 opérations, n fois
    return s       # 1 opération

Total : \(T(n) = 1 + 2n + 1 = 2n + 2\).

Pourquoi \(O(n)\) ? Quand \(n\) grandit, le terme dominant est \(2n\) ; la constante (\(+2\)) et le facteur (\(2\)) sont négligeables devant la croissance. On écrit \(T(n) = O(n)\) : croissance linéaire (doubler \(n\) double le temps).

Boucles imbriquées. Le coût d'une boucle interne se multiplie par les tours de la boucle externe : deux boucles allant jusqu'à \(n\) donnent \(n \times n = n^2\) opérations.

6. La notation asymptotique grand \(O\)

Définition. \(T(n) = O\big(f(n)\big)\) s'il existe une constante \(C \gt 0\) et un rang \(n_0\) tels que : pour tout \(n \ge n_0\), \(T(n) \le C \cdot f(n)\). Autrement dit, \(f(n)\) est une borne supérieure de la croissance de \(T(n)\), à une constante près.

On ignore les constantes multiplicatives : \(5n^2 = O(n^2)\).
On ne garde que le terme dominant : \(3n^2 + 7n + 4 = O(n^2)\).
La base d'un logarithme est sans importance : \(\log_2 n\) et \(\log_{10} n\) sont des \(O(\log n)\).

7. Les ordres de grandeur classiques

Notation	Nom	Exemple
\(O(1)\)	Constante	Accès `liste[i]`
\(O(\log n)\)	Logarithmique	Recherche dichotomique
\(O(n)\)	Linéaire	Parcours de liste
\(O(n \log n)\)	Quasi-linéaire	Tri fusion, tri rapide
\(O(n^2)\)	Quadratique	Boucles imbriquées
\(O(2^n)\)	Exponentielle	Force brute, parties d'un ensemble
\(O(n!)\)	Factorielle	Permutations

\(O(1) \lt O(\log n) \lt O(n) \lt O(n \log n) \lt O(n^2) \lt O(2^n) \lt O(n!)\)

⚠️ Ce ne sont que des exemples. Ce tableau et cette hiérarchie ne constituent pas une règle générale : il existe d'autres ordres de complexité (\(O(\sqrt{n})\), \(O(n^3)\), \(O(n^k)\), \(O(n\,2^n)\)…). L'important est de savoir situer une complexité donnée.

📈 Concrètement. Pour \(n = 10^6\) : un \(O(n)\) est instantané, un \(O(n^2)\) effectue \(10^{12}\) opérations (minutes à heures), un \(O(2^n)\) est irréalisable. La complexité détermine la faisabilité.

8. Complexité des programmes itératifs

On analyse les boucles de l'intérieur vers l'extérieur : instruction simple \(O(1)\) ; boucle de \(n\) tours \(O(n)\) ; deux boucles imbriquées \(O(n^2)\) ; \(k\) boucles imbriquées \(O(n^k)\).

Exemple — recherche dichotomique (liste triée) :

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

Calcul formel. Soit \(t\) le nombre d'éléments de l'intervalle \([g, d]\) ; au départ \(t_0 = n\). Chaque tour divise \(t\) par 2 : \(t_k = \dfrac{n}{2^k}\). La boucle s'arrête quand \(t_k \lt 1\), soit \(\dfrac{n}{2^k} \lt 1\), c'est-à-dire \(k \gt \log_2 n\). Il y a donc au plus \(\lfloor \log_2 n \rfloor + 1\) tours : la complexité est \(O(\log n)\).

9. Complexité des programmes récursifs

Pour un programme récursif, on exprime la complexité par une relation de récurrence : \(T(n)\) s'écrit en fonction du coût des appels plus petits, puis on la déroule.

Exemple 1 — factorielle.

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

\(T(n) = T(n-1) + O(1)\). En déroulant : \(T(n) = O(1) + O(1) + \dots\) (\(n\) termes) \(= O(n)\).

Exemple 2 — Fibonacci récursif naïf.

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

Chaque appel en engendre deux : \(T(n) = T(n-1) + T(n-2) + O(1)\). Le nombre d'appels croît comme la suite de Fibonacci elle-même, d'où une complexité exponentielle.

Calcul détaillé (nombre d'or). La partie homogène \(T(n) = T(n-1) + T(n-2)\) a pour équation caractéristique \(r^2 = r + 1\), soit \(r^2 - r - 1 = 0\). Ses racines sont \(r = \dfrac{1 \pm \sqrt5}{2}\) : le nombre d'or \(\varphi = \dfrac{1+\sqrt5}{2} \approx 1{,}618\) et \(\psi = \dfrac{1-\sqrt5}{2} \approx -0{,}618\). La solution est \(T(n) = A\,\varphi^{\,n} + B\,\psi^{\,n}\) ; comme \(|\psi| \lt 1\), \(\psi^{\,n} \to 0\). Donc \(T(n) = \Theta(\varphi^{\,n})\) avec \(\varphi \approx 1{,}618\). La borne \(O(2^n)\) est correcte mais lâche, car \(\varphi \lt 2\).

Méthode générale — résolution par équation caractéristique. Pour une récurrence linéaire à coefficients constants \(T(n) = a_1 T(n-1) + a_2 T(n-2) + \dots + a_k T(n-k)\) :

écrire l'équation caractéristique \(r^k = a_1 r^{k-1} + \dots + a_k\) ;
trouver ses racines \(r_1, \dots, r_k\) ;
solution générale : racines distinctes \(\Rightarrow T(n) = \sum_i C_i\, r_i^{\,n}\) ; une racine \(r\) de multiplicité \(m\) apporte un terme \((C_0 + C_1 n + \dots + C_{m-1} n^{m-1})\, r^{\,n}\) ;
les constantes \(C_i\) sont fixées par les conditions initiales.

Comportement asymptotique : la racine de plus grand module \(r_{\max}\) domine, donc \(T(n) = \Theta\big(|r_{\max}|^{\,n}\big)\) (à un facteur polynomial près en cas de multiplicité).
Exemples : Fibonacci \(r^2 = r+1 \Rightarrow \varphi \Rightarrow \Theta(\varphi^{\,n})\) ; \(T(n) = 2T(n-1) \Rightarrow r=2 \Rightarrow \Theta(2^{\,n})\) ; \(T(n) = 2T(n-1) - T(n-2) \Rightarrow (r-1)^2 = 0 \Rightarrow \Theta(n)\).

Confirmation — algèbre linéaire (Fibonacci). On pose le vecteur d'état \(\begin{pmatrix}F_{n+1}\\ F_n\end{pmatrix} = A\begin{pmatrix}F_n\\ F_{n-1}\end{pmatrix}\) avec \(A=\begin{pmatrix}1&1\\ 1&0\end{pmatrix}\), d'où \(\begin{pmatrix}F_{n+1}\\ F_n\end{pmatrix} = A^{\,n}\begin{pmatrix}1\\ 0\end{pmatrix}\). Les valeurs propres vérifient \(\det(A-\lambda I)=\lambda^2-\lambda-1=0\), soit \(\lambda = \varphi,\ \psi\). En diagonalisant \(A = P D P^{-1}\) avec \(D=\operatorname{diag}(\varphi,\psi)\), on a \(A^{\,n}=P D^{\,n} P^{-1}\) et l'on obtient la formule de Binet : \(F_n = \dfrac{\varphi^{\,n} - \psi^{\,n}}{\sqrt5}\). Comme \(|\psi| \lt 1\), \(F_n \sim \dfrac{\varphi^{\,n}}{\sqrt5}\) : on retrouve \(\Theta(\varphi^{\,n})\).

Exemples de récurrences classiques :

Récurrence	Exemple	Complexité
\(T(n) = T(n/2) + O(1)\)	dichotomie récursive	\(O(\log n)\)
\(T(n) = T(n-1) + O(1)\)	factorielle	\(O(n)\)
\(T(n) = T(n-1) + O(n)\)	somme de paires	\(O(n^2)\)
\(T(n) = 2T(n/2) + O(n)\)	tri fusion	\(O(n \log n)\)
\(T(n) = T(n-1) + T(n-2) + O(1)\)	Fibonacci naïf	\(O(\varphi^{\,n})\), \(\varphi \approx 1{,}618\)

Diviser pour régner — Master théorème. Pour \(T(n) = a\,T(n/b) + O(n^d)\), en posant l'exposant critique \(\log_b a\) :

si \(d \gt \log_b a\) : \(T(n) = O(n^d)\) ;
si \(d = \log_b a\) : \(T(n) = O(n^d \log n)\) ;
si \(d \lt \log_b a\) : \(T(n) = O\big(n^{\log_b a}\big)\).

Cas usuel : \(T(n) = 2T(n/2) + O(n)\) (\(a = b = 2\), \(d = 1\)) \(\to O(n \log n)\), comme le tri fusion.

10. Complexité spatiale

La complexité spatiale mesure la mémoire supplémentaire nécessaire, au-delà des données d'entrée (calcul asymptotique, meilleur et pire des cas).

Quelques variables seulement : \(O(1)\) (espace constant, dit en place).
Création d'une nouvelle liste de taille \(n\) : \(O(n)\).
Récursivité : chaque appel non terminé occupe une case de la pile d'appels. Une récursion de profondeur \(n\) a une complexité spatiale \(O(n)\), même sans tableau.

À retenir. Un algorithme rapide n'est pas toujours économe en mémoire : le tri fusion est \(O(n \log n)\) en temps mais nécessite \(O(n)\) d'espace auxiliaire.

11. Récapitulatif

Structure de code	Complexité temporelle
Instruction simple, accès tableau	\(O(1)\)
Boucle simple sur \(n\)	\(O(n)\)
Deux boucles imbriquées sur \(n\)	\(O(n^2)\)
Division de l'intervalle par 2	\(O(\log n)\)
Diviser pour régner (recombinaison linéaire)	\(O(n \log n)\)
Récursion à deux appels (Fibonacci naïf)	\(O(\varphi^{\,n})\)

✅ Points essentiels.

Toujours préciser \(n\) (souvent \(n = \operatorname{len}(\text{liste})\)).
Compter les opérations, garder le terme dominant → grand \(O\).
On étudie le meilleur et le pire des cas ; le pire cas garantit une borne.
Itératif : boucle → \(O(n)\), imbriquées → \(O(n^2)\), division par 2 → \(O(\log n)\).
Récursif : poser et dérouler la récurrence ; Master théorème pour diviser pour régner.
Les ordres classiques sont des exemples, pas une liste exhaustive.

CPGE MP/PSI — Informatique · Chapitre : La complexité algorithmique · Conforme au programme officiel 2023