Complexité temporelle

Vue d'ensemble

Deux programmes peuvent donner le même résultat et pourtant l'un s'exécuter en une fraction de seconde, l'autre mettre des heures sur une grande entrée. Pour comparer des algorithmes sans dépendre de la machine, on ne mesure pas un temps en secondes : on compte le nombre d'opérations élémentaires en fonction de la taille n de l'entrée. La notation grand-O résume ce décompte en un ordre de grandeur ( $O (n)$ , $O (n^{2})$ , $O (lo g n)$ …). Cette fiche te montre comment lire la complexité d'un code à l'œil, en décryptant chaque exemple ligne par ligne.

Au programme (tronc commun, 1^re année — BO 2021) — Coût d'un algorithme : nombre d'opérations élémentaires en fonction de la taille des entrées ; notation

O (\cdot)

; complexité dans le meilleur et le pire des cas ; ordres de grandeur usuels (constant, logarithmique, linéaire, quadratique, exponentiel) sur les algorithmes du programme.

Prérequis

Écrire et lire une boucle for et une boucle while
Connaître la recherche par dichotomie dans un tableau trié
Savoir ce qu'est le logarithme en base 2 : $lo g_{2} n$ est l'exposant tel que $2^{l o g_{2} n} = n$

🎯 Accompagnement Majorant

« Comment je sais si c'est du $O (n)$ ou du $O (n^{2})$ rien qu'en regardant ? » C'est un réflexe qui se travaille, et il rapporte des points à chaque écrit. Nos mentors alumni X · Centrale · Mines t'entraînent à lire la complexité d'un code d'un coup d'œil, sur tes propres sujets, jusqu'à ce que ça devienne automatique.

Trouver un mentor →

1. Compter les opérations, pas les secondes

Le temps réel d'un programme dépend de la machine, du langage, de ce que fait l'ordinateur à côté : ce n'est pas une bonne mesure pour comparer des algorithmes. On raisonne donc sur le nombre d'opérations élémentaires effectuées (une addition, une comparaison, un accès t[i], une affectation…) en fonction de la taille de l'entrée, notée n (le nombre d'éléments d'une liste, la valeur d'un entier, etc.).

Définition 1.1 — Complexité temporelle et notation grand-O

La complexité temporelle d'un algorithme est une fonction $T (n)$ qui donne le nombre d'opérations élémentaires effectuées sur une entrée de taille $n$ . On s'intéresse à son ordre de grandeur pour $n$ grand, à une constante multiplicative près. On écrit $T (n) = O (g (n))$ , et on lit « $T$ est un grand-O de $g$ », lorsqu'il existe une constante $C > 0$ et un rang $n_{0}$ tels que :

$T (n) \leq C g (n) pour tout n \geq n_{0} .$

📝 Pourquoi « à une constante près ». Si un algorithme fait

3 n + 7

opérations et un autre

n

opérations, les deux sont en

O (n)

: pour

n

grand, le facteur

3

et le +7 ne changent pas la catégorie. Le grand-O gomme les constantes et les termes négligeables pour ne garder que le terme dominant :

2 n^{2} + 100 n + 5

est en

O (n^{2})

Prenons un premier exemple : la somme des éléments d'une liste.

def somme(t):
    s = 0
    for x in t:
        s = s + x
    return s

🔍 Décryptage ligne par ligne

s = 0Une affectation : 1 opération, faite une seule fois quelle que soit la taille de t.

for x in t:La boucle parcourt les $n$ éléments. Le corps de la boucle est donc exécuté

n

fois — c'est lui qui va donner l'ordre de grandeur.

s = s + xUne addition + une affectation à chaque tour, donc environ

2 n

opérations en tout. C'est le cœur du coût.

return s1 opération, une seule fois.

💡 Le décompte. Au total

T (n) = 2 n + 2

opérations (à la louche). Le terme dominant est

2 n

, donc somme est en $O (n)$ : on dit qu'elle a une complexité linéaire. Doubler la taille de la liste double (à peu près) le travail.

2. Les familles d'ordres de grandeur

Presque toute la complexité au programme se range dans une poignée de familles. Le tableau ci-dessous est la chose à avoir en tête : il donne, pour chaque famille, le nombre d'opérations quand l'entrée grandit. C'est notre « table de trace » — elle trace non pas l'exécution d'un code, mais l'explosion du nombre d'opérations selon $n$ .

Ordres de grandeur — nombre d'opérations selon la taille $n$ de l'entrée
Famille	Nom	$n = 10$	$n = 100$	$n = 1 0^{6}$
$O (1)$	constant	1	1	1
$O (lo g n)$	logarithmique	≈ 3	≈ 7	≈ 20
$O (n)$	linéaire	10	100	10⁶
$O (n lo g n)$	quasi-linéaire	≈ 33	≈ 664	≈ 2 × 10⁷
$O (n^{2})$	quadratique	100	10 000	10¹²
$O (2^{n})$	exponentiel	1024	≈ 10³⁰	inimaginable

📝 Lire ce tableau. Entre

n = 10

n = 1 0^{6}

, un algorithme

O (lo g n)

passe de 3 à 20 opérations : quasi gratuit. Un

O (n^{2})

passe de 100 à

1 0^{12}

: mille milliards d'opérations, soit des minutes voire des heures. Et

O (2^{n})

est déjà hors-jeu dès

n = 100

(

2^{100} \approx 1 0^{30}

: même à un milliard d'opérations par seconde, il faudrait près de 3000 fois l'âge de l'univers pour terminer un seul calcul). La famille compte infiniment plus que la constante devant.

⚠ $O (n^{2})$ n'est pas « toujours plus lent » que $O (n)$ . Le grand-O parle du comportement pour $n$ grand. Sur une petite entrée, un algorithme

O (n^{2})

avec une petite constante peut battre un

O (n)

avec une grosse constante. Ce que garantit le grand-O, c'est qu'à partir d'un certain rang $n_{0}$ , le linéaire l'emporte — et cet écart devient vite gigantesque.

3. Meilleur cas, pire cas, cas moyen

Pour une même taille $n$ , le nombre d'opérations peut dépendre du contenu de l'entrée. On distingue alors trois complexités. L'exemple canonique est la recherche séquentielle : parcourir une liste jusqu'à trouver une valeur.

def recherche_seq(t, x):
    for i in range(len(t)):
        if t[i] == x:
            return i          # trouvé : on renvoie la position
    return -1                 # jamais trouvé : x est absent

🔍 Décryptage ligne par ligne

for i in range(len(t)):On balaie les indices de

0

n - 1

. Le nombre de tours réellement effectués dépend de où se trouve x.

if t[i] == x:
    return i

Une comparaison par tour. Dès qu'on tombe sur x, on renvoie son indice et on s'arrête net : on ne fait pas les tours suivants.

return -1Si la boucle va jusqu'au bout sans rien trouver, x est absent : on a fait

n

comparaisons pour rien.

Meilleur cas — x est en première position (t[0]) : 1 comparaison, donc $O (1)$ .
Pire cas — x est en dernière position, ou absent : $n$ comparaisons, donc $O (n)$ .
Cas moyen — si x est présent à une position au hasard : en moyenne $\frac{n}{2}$ comparaisons, soit encore $O (n)$ .

📝 La convention par défaut. Quand on dit « la recherche séquentielle est en

O (n)

» sans préciser, on parle du pire cas : c'est la garantie la plus utile (« ça ne fera jamais plus que… »). Sauf mention contraire, complexité = complexité dans le pire cas.

4. Méthode : lire la complexité d'un code

📐 Méthode — déterminer la complexité d'un code.

Une boucle qui parcourt $n$ éléments (et corps en $O (1)$ ) → $O (n)$ .
Deux boucles imbriquées, chacune sur $n$ → le corps s'exécute $n \times n$ fois → $O (n^{2})$ .
Une grandeur divisée par 2 à chaque tour (comme la dichotomie) → $O (lo g n)$ .
Des blocs en séquence (l'un après l'autre) → on additionne les coûts et on garde le plus grand : $O (n) + O (n^{2}) = O (n^{2})$ .
On oublie les constantes et les termes non dominants.

Deux boucles imbriquées → quadratique

Comptons les paires d'éléments d'une liste dont la somme vaut une valeur cible s.

def compte_paires(t, s):
    n = len(t)
    c = 0
    for i in range(n):
        for j in range(i + 1, n):
            if t[i] + t[j] == s:
                c = c + 1
    return c

🔍 Décryptage ligne par ligne

for i in range(n):Boucle externe :

n

tours, un pour chaque premier élément de la paire.

for j in range(i + 1, n):Boucle interne : pour chaque i, on essaie tous les j > i. On teste ainsi chaque paire une seule fois. Le nombre total de tours internes est

(2 n) = \frac{n ( n - 1 )}{2}

if t[i] + t[j] == s:
    c = c + 1

Une addition + une comparaison par paire. C'est le corps en

O (1)

, répété

\frac{n ( n - 1 )}{2}

fois.

💡 Le décompte. Le corps s'exécute

\frac{n ( n - 1 )}{2} = \frac{n ^{2} - n}{2}

fois. Le terme dominant est

\frac{n ^{2}}{2}

: à une constante près, c'est

O (n^{2})

, quadratique. Pour

n = 5

, cela fait

\frac{5 \times 4}{2} = 10

paires testées. Doubler

n

multiplie le travail par ≈ 4.

Division par 2 → logarithmique

La dichotomie (vue en prérequis) illustre le cas $O (lo g n)$ : à chaque tour, la zone de recherche est divisée par 2.

def dichotomie(t, x):
    g, d = 0, len(t) - 1
    while g <= d:
        m = (g + d) // 2
        if t[m] == x:
            return m
        elif t[m] < x:
            g = m + 1          # on jette la moitié gauche
        else:
            d = m - 1          # on jette la moitié droite
    return -1

🔍 Décryptage ligne par ligne

while g <= d:On répète tant que la zone $[g, d]$ est non vide. La question de complexité, c'est : combien de fois cette boucle tourne-t-elle ?

m = (g + d) // 2On vise le milieu de la zone courante — coût

O (1)

g = m + 1Cas « trop petit » : on garde la moitié droite. La taille de la zone est (au moins) divisée par 2.

d = m - 1Cas « trop grand » : on garde la moitié gauche. Là encore, la zone est divisée par 2.

Partant de $n$ éléments, la taille de la zone suit $n, \frac{n}{2}, \frac{n}{4}, \dots$ jusqu'à 1. Le nombre de divisions par 2 pour passer de $n$ à 1 est $lo g_{2} n$ : la boucle fait de l'ordre de $lo g_{2} n$ tours, d'où la complexité $O (lo g n)$ . C'est ce que précise le théorème suivant.

Propriété 4.1 — Coût de la dichotomie ★ À savoir démontrer

Sur un tableau trié de $n \geq 1$ éléments, la recherche par dichotomie effectue au plus $⌊ lo g_{2} n ⌋ + 1$ itérations de la boucle. Sa complexité dans le pire cas est donc $O (lo g n)$ .

Démonstration

Notons $N$ la taille de la zone de recherche $[g, d]$ , c'est-à-dire $N = d - g + 1$ . Initialement $N = n$ . À chaque itération où l'on ne renvoie pas, on remplace $g$ par $m + 1$ ou $d$ par $m - 1$ avec $m = ⌊(g + d) /2 ⌋$ ; dans les deux cas la nouvelle zone contient au plus $⌊ N /2 ⌋$ éléments : la taille est (au moins) divisée par 2.

Après $k$ itérations, la zone contient donc au plus $\frac{n}{2 ^{k}}$ éléments. La boucle continue tant que la zone est non vide, soit $N \geq 1$ . Or dès que $\dfrac{n}{2^k} < 1$ , c'est-à-dire $2^k > n$ , la zone est vide et la boucle s'arrête. Cette condition est atteinte pour $k = ⌊ lo g_{2} n ⌋ + 1$ , car alors $2^k > n$ . Le nombre d'itérations est donc au plus $⌊ lo g_{2} n ⌋ + 1$ .

Chaque itération coûte $O (1)$ , d'où un coût total en $O (lo g_{2} n) = O (lo g n)$ . $■$

🎯 Accompagnement Majorant

Bloqué sur « pourquoi diviser par 2 donne un log » ? Ce genre de déclic, une fois posé clairement, ne te lâche plus. Nos mentors alumni X · Centrale · Mines reprennent la preuve avec toi et te font l'appliquer à d'autres algorithmes « diviser pour régner » de ton programme.

Trouver un mentor →

5. Exercices d'application

Fais-les sur papier avant d'ouvrir le corrigé, puis passe au quiz en bas de fiche.

Exo 1Reconnaître l'ordre de grandeurFacile

Donne la complexité (dans le pire cas) de cette fonction, en justifiant.

def maxi(t):
    m = t[0]
    for x in t:
        if x > m:
            m = x
    return m

Voir la correction détaillée

Une seule boucle for parcourt les

n

éléments de t.

Le corps (une comparaison, parfois une affectation) coûte

O (1)

par tour.

Coût total :

n \times O (1) = O (n)

. C'est linéaire : chercher un maximum oblige à tout regarder, on ne peut pas faire mieux.

Exo 2Séquence de blocsIntermédiaire

Quelle est la complexité de f en fonction de n = len(t) ? Justifie avec la règle des blocs en séquence.

def f(t):
    n = len(t)
    s = 0
    for x in t:              # bloc A
        s = s + x
    c = 0
    for i in range(n):       # bloc B
        for j in range(n):
            c = c + 1
    return s + c

Voir la correction détaillée

Bloc A : une boucle simple sur

n

éléments →

O (n)

Bloc B : deux boucles imbriquées, chacune sur

n

→ le corps s'exécute

n \times n = n^{2}

fois →

O (n^{2})

Les deux blocs sont en séquence : on additionne,

O (n) + O (n^{2}) = O (n^{2})

, et on garde le plus grand. La fonction est donc $O (n^{2})$ — le bloc A est négligeable devant le bloc B.

Exo 3Compter les tours d'une division par 2Difficile

Combien de fois la boucle tourne-t-elle pour n = 1000 ? Quelle est la complexité en fonction de n ?

def compte(n):
    r = 0
    while n > 1:
        r = r + 1
        n = n // 2
    return r

Voir la correction détaillée

À chaque tour, n est divisé par 2 (division entière) :

1000 \to 500 \to 250 \to 125 \to 62 \to 31 \to 15 \to 7 \to 3 \to 1

On compte 9 tours avant que n n'atteigne 1 (la fonction renvoie donc 9). C'est cohérent avec

⌊ lo g_{2} 1000 ⌋ = 9

En général, le nombre de tours est de l'ordre de

lo g_{2} n

: la complexité est $O (lo g n)$ . Doubler

n

ajoute un seul tour.

Récap final — Ce qu'il faut absolument retenir

À la veille d'une khôlle ou d'un DS, parcours cette checklist : tu dois pouvoir répondre « oui, sans hésiter » à chaque question.

Sais-tu expliquer pourquoi on compte des opérations et non des secondes ?
Sais-tu donner la définition semi-formelle de $T (n) = O (g (n))$ (constante $C$ et rang $n_{0}$ ) ?
Sais-tu classer les familles $O (1)$ , $O (lo g n)$ , $O (n)$ , $O (n lo g n)$ , $O (n^{2})$ , $O (2^{n})$ et dire laquelle explose le plus vite ?
Sais-tu distinguer meilleur cas, pire cas et cas moyen sur la recherche séquentielle ?
Sais-tu qu'une complexité annoncée sans précision est celle du pire cas ?
Sais-tu reconnaître à l'œil qu'une boucle simple est $O (n)$ , deux boucles imbriquées $O (n^{2})$ , une division par 2 $O (lo g n)$ ?
Sais-tu appliquer la règle « blocs en séquence → on garde le max » ?
Sais-tu démontrer que la dichotomie fait au plus $⌊ lo g_{2} n ⌋ + 1$ itérations ?

À savoir refaire

Coût logarithmique de la dichotomie — la zone est divisée par 2 à chaque tour, donc au plus $⌊ lo g_{2} n ⌋ + 1$ itérations.

Vue d'ensemble

Prérequis

1. Compter les opérations, pas les secondes

2. Les familles d'ordres de grandeur

3. Meilleur cas, pire cas, cas moyen

4. Méthode : lire la complexité d'un code

Deux boucles imbriquées → quadratique

Division par 2 → logarithmique

5. Exercices d'application

Récap final — Ce qu'il faut absolument retenir

À savoir refaire

Débloque la fiche complète

Quiz — Complexité

Fiches associées

Recherche par dichotomie

Variables, types et affectations

Conditions et booléens

Boucles for et while

Fonctions : paramètres et valeurs de retour

Listes et chaînes de caractères

Tu veux aller plus loin sur ce chapitre ?