La complexité
algorithmique

Pr. EL HADIQ Zouhair

Informatique CPGE — MP / PSI · Première période

1 / 23

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 utiliser le grand $O$.
Calculer la complexité d'un programme itératif et récursif (récurrences, Master théorème).

2 / 23

Pourquoi mesurer la complexité ?

Un même problème admet plusieurs algorithmes corrects menant à la même solution, mais avec des efficacités différentes. La complexité sert à choisir lequel.

Méthode On incrémente un compteur à chaque opération élémentaire et on compte en fonction de $n$ : c'est la mesure objective, indépendante de la machine.

3 / 23

Deux types de complexité

Temporelle

Nombre d'opérations élémentaires en fonction de $n$ — estime le temps d'exécution.

Spatiale

Quantité de mémoire supplémentaire utilisée en fonction de $n$ (variables, tableaux, pile d'appels).

Compromis temps / espace Gagner du temps coûte souvent de la mémoire (et inversement).

4 / 23

Opération élémentaire

Instruction de base, de coût supposé constant :

affectation ($x = 3$), comparaison ($a < b$) ;
opération arithmétique ($a + b$, $a \times b$) ;
accès à une case de tableau (liste[i]).

Incrémenter & compter On associe un compteur à ces opérations et on l'évalue en fonction de $n$.

5 / 23

La taille du problème $n$CLÉ

La complexité s'exprime en fonction d'un entier $n$ qui mesure la taille de l'entrée. Il faut toujours 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$ à traiter	$n = N$, ou $n = \log_2 N$ (nombre de chiffres / bits)
Une matrice $p \times q$	$n = p\,q$ (nombre de cases)
Un graphe	$n$ = nombre de sommets (et $m$ = nombre d'arêtes)
Une chaîne de caractères	$n$ = longueur de la chaîne

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

6 / 23

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 CPGE : meilleur et pire des cas.

Meilleur cas : entrée la plus favorable.
Pire cas : entrée la plus défavorable — borne supérieure garantie.

Recherche séquentielle : meilleur $O(1)$, pire $O(n)$.

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

7 / 23

Compter les opérations $\Rightarrow O(n)$POURQUOI

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

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

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

Idée Doubler $n$ double (à peu près) le temps.

8 / 23

Boucles imbriquées

Avec $n = \operatorname{len}(\text{liste})$, le corps d'une boucle interne se multiplie par les tours de la boucle externe :

for i in range(n): # n fois for j in range(n): # n fois traiter(i, j) # n x n

$n \times n = n^2$ opérations : complexité quadratique $O(n^2)$.

9 / 23

La notation grand $O$

Définition $T(n) = O\big(f(n)\big)$ s'il existe $C > 0$ et un rang $n_0$ tels que $$\forall n \ge n_0, \quad T(n) \le C\, f(n).$$ $f(n)$ est une borne supérieure de la croissance de $T(n)$, à une constante près.

10 / 23

Règles pratiques

Ignorer les constantes multiplicatives : $5n^2 = O(n^2)$.
Ne garder que le terme dominant : $3n^2 + 7n + 4 = O(n^2)$.
La base du logarithme n'importe pas : $\log_2 n,\ \log_{10} n = O(\log n)$.

11 / 23

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 / rapide
$O(n^2)$	Quadratique	Double boucle
$O(2^n)$	Exponentielle	Parties d'un ensemble, force brute

Attention Ce tableau ne donne que des exemples de complexités — ce n'est pas une règle générale : d'autres ordres existent ($O(\sqrt{n})$, $O(n^3)$, $O(n!)$, $O(n^k)$…).

12 / 23

Hiérarchie de croissance

$$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n) < O(n!)$$

Concrètement, pour $n = 10^6$ $O(n)$ : instantané · $O(n^2)$ : $10^{12}$ opérations (minutes/heures) · $O(2^n)$ : irréalisable.

Là encore, ce ne sont que des repères par l'exemple ; l'important est de savoir situer une complexité donnée.

13 / 23

Exercice — classer par grand $O$APPLIQUÉ

Donner la classe de complexité (terme dominant) de chaque expression :

$T(n)$	Réponse $O(\,\cdot\,)$
$7n + 100$	$O(n)$
$3n^2 + 50n + 9$	$O(n^2)$
$5\log_2 n + 2$	$O(\log n)$
$4n^3 + n^2\log n$	$O(n^3)$
$2^n + n^{10}$	$O(2^n)$
$n\log n + 3n$	$O(n\log n)$

Règle On garde le terme qui croît le plus vite, sans son coefficient.

14 / 23

Itératif : dichotomie — calcul formel$O(\log n)$

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

Étapes formelles. Soit $t$ = nombre d'éléments de l'intervalle $[g,d]$. Au départ $t_0 = n$. Chaque tour divise $t$ par 2 :

$$t_k = \frac{n}{2^k}$$

La boucle s'arrête quand $t_k < 1$, soit $\dfrac{n}{2^k} < 1 \Rightarrow k > \log_2 n$.

Conclusion Au plus $\lfloor \log_2 n\rfloor + 1$ tours $\Rightarrow O(\log n)$.

15 / 23

Exemples (itératif) par classe

Classe	Boucle type
$O(1)$	`return L[0]` (aucune boucle dépendant de $n$)
$O(\log n)$	`while n>1: n = n//2` (on divise par 2)
$O(n)$	`for i in range(n): ...`
$O(n^2)$	deux boucles imbriquées sur $n$
$O(n^k)$	$k$ boucles imbriquées sur $n$
$O(2^n)$	parcourir tous les sous-ensembles de $n$ éléments

16 / 23

Méthode : équation caractéristiqueRÉCURRENCES

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)$$

1. Équation caractéristique :

$$r^k = a_1 r^{k-1} + \dots + a_k$$

2. Racines $r_1,\dots,r_k$.

3. Solution générale :

racines distinctes : $T(n)=\sum_i C_i\,r_i^{\,n}$ ;
racine $r$ de multiplicité $m$ : terme $(C_0+C_1 n+\dots+C_{m-1}n^{m-1})\,r^{\,n}$.

4. Les $C_i$ se calculent avec les conditions initiales.

Comportement asymptotique La racine de plus grand module $r_{\max}$ domine : $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=\tfrac{1+\sqrt5}{2} \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)$.

17 / 23

Récursif : Fibonacci — calcul détailléNOMBRE D'OR

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

Nombre d'appels : $C(n)=C(n-1)+C(n-2)+1$, avec $C(0)=C(1)=1$ : la croissance est celle de la suite de Fibonacci.

Partie homogène $T(n)=T(n-1)+T(n-2)$. Équation caractéristique :

$$r^2 = r+1 \;\Longleftrightarrow\; r^2-r-1=0$$

Racines $r=\dfrac{1\pm\sqrt5}{2}$ : $\varphi=\dfrac{1+\sqrt5}{2}\approx 1{,}618$ (nombre d'or) et $\psi=\dfrac{1-\sqrt5}{2}\approx -0{,}618$.

$T(n)=A\,\varphi^{\,n}+B\,\psi^{\,n}$ ; comme $|\psi|<1$, $\psi^{\,n}\to 0$.

Conclusion $T(n)=\Theta(\varphi^{\,n})$ avec $\varphi=\frac{1+\sqrt5}{2}\approx 1{,}618$. La borne $O(2^n)$ est correcte mais lâche car $\varphi<2$.

18 / 23

Confirmation : algèbre linéaireDIAGONALISATION

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},\quad A=\begin{pmatrix}1&1\\ 1&0\end{pmatrix}$$

Par récurrence : $\begin{pmatrix}F_{n+1}\\ F_n\end{pmatrix}=A^{\,n}\begin{pmatrix}F_1\\ F_0\end{pmatrix}=A^{\,n}\begin{pmatrix}1\\ 0\end{pmatrix}$.

Valeurs propres : $\det(A-\lambda I)=\lambda^2-\lambda-1=0 \Rightarrow \lambda=\varphi,\ \psi$.

$A$ est diagonalisable : $A=PDP^{-1}$ avec $D=\operatorname{diag}(\varphi,\psi)$, donc $$A^{\,n}=P\,D^{\,n}P^{-1},\qquad D^{\,n}=\operatorname{diag}(\varphi^{\,n},\psi^{\,n}).$$

Terme général (formule de Binet) $F_n=\dfrac{\varphi^{\,n}-\psi^{\,n}}{\sqrt5}$. Comme $|\psi|<1$, on a $F_n\sim \dfrac{\varphi^{\,n}}{\sqrt5}$ : on retrouve bien $\Theta(\varphi^{\,n})$.

19 / 23

Exemples (récursif) par classeCALCUL

Récurrence	Exemple	Complexité
$T(n)=O(1)$ (aucun appel récursif dépendant de $n$)	cas de base / accès direct	$O(1)$
$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)=T(n-1)+O(n^{k-1})$	imbrication d'ordre $k$	$O(n^k)$
$T(n)=T(n-1)+T(n-2)+O(1)$	Fibonacci naïf	$O(\varphi^{\,n})$, $\varphi\approx1{,}618$

Méthode Dérouler la récurrence : $T(n)=O(1)+O(1)+\dots$ (compter le nombre de termes), ou appliquer le Master théorème (slide suivante).

20 / 23

Diviser pour régner — Master théorèmePARTITION

Découper en $a$ sous-problèmes de taille $n/b$, avec un coût de partition/recombinaison $O(n^d)$ :

$$T(n) = a\,T\!\left(\tfrac{n}{b}\right) + O(n^d)$$

Comparaison	Complexité	Exemple
$d > \log_b a$	$O(n^d)$	—
$d = \log_b a$	$O(n^d \log n)$	tri fusion : $a{=}b{=}2,\ d{=}1 \Rightarrow O(n\log n)$
$d < \log_b a$	$O(n^{\log_b a})$	—

Cas équilibré usuel : $T(n)=2T(n/2)+O(n) \Rightarrow O(n\log n)$.

21 / 23

Complexité spatiale

Quelques variables → $O(1)$ (algorithme en place).
Création d'une liste de taille $n$ → $O(n)$.
Récursivité : chaque appel occupe la pile ; profondeur $n$ → $O(n)$ d'espace, même sans tableau.

Un algorithme rapide n'est pas toujours économe : tri fusion $O(n\log n)$ en temps mais $O(n)$ en espace.

22 / 23

Récapitulatif

Toujours préciser $n$ (souvent $n = \operatorname{len}(\text{liste})$).
Compter les opérations, garder le terme dominant → grand $O$.
Itératif : compter les tours (boucle $\to O(n)$, imbriquées $\to O(n^2)$, division par 2 $\to 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.

23 / 23

La complexitéalgorithmique