Compter les opérations : la notation O()

Leçon optionnelle — Analyse de complexité algorithmique

Pourquoi compter les opérations ?

En analyse numérique, un algorithme peut être mathématiquement correct mais pratiquement inutilisable s'il est trop lent. La complexité algorithmique mesure comment le temps de calcul évolue avec la taille du problème.

💡

Question fondamentale

Si je double la taille de mon problème, est-ce que le temps de calcul double aussi ? Quadruple ? Explose ?

La notation grand O

Définition intuitive

La notation $O(f(n))$ (« grand O de f de n ») décrit le comportement asymptotique d'un algorithme quand la taille $n$ devient grande.

T(n) = O(f(n)) \quad \Leftrightarrow \quad \exists C, n_0 : \forall n \geq n_0, \; T(n) \leq C \cdot f(n)

En pratique, on retient :

On ignore les constantes multiplicatives : $5n^2$ et $100n^2$ sont tous deux $O(n^2)$
On garde le terme dominant : $n^2 + 100n + 1000$ est $O(n^2)$

Les classes de complexité courantes

Complexité	Nom	Comportement	Exemple
$O(1)$	Constante	Indépendant de n	Accès à un élément de tableau
$O(\log n)$	Logarithmique	Très lent à croître	Recherche dichotomique
$O(n)$	Linéaire	Proportionnel à n	Parcours d'une liste
$O(n \log n)$	Quasi-linéaire	Un peu plus que linéaire	Tri fusion, FFT
$O(n^2)$	Quadratique	×100 si n×10	Produit matrice-vecteur
$O(n^3)$	Cubique	×1000 si n×10	Produit matriciel, élimination de Gauss
$O(2^n)$	Exponentielle	Explose rapidement	Énumération de tous les sous-ensembles

Compter les opérations : exemples concrets

Exemple 1 : somme d'un vecteur

somme_vecteur.pypython

def somme(v):
  """Calcule la somme des éléments d'un vecteur."""
  total = 0           # 1 opération
  for x in v:         # n itérations
      total += x      # 1 addition par itération
  return total

# Complexité : O(n)
# - La boucle s'exécute n fois
# - Chaque itération fait 1 addition
# Total : n additions

Exemple 2 : produit scalaire

produit_scalaire.pypython

def produit_scalaire(u, v):
  """Calcule le produit scalaire de deux vecteurs."""
  n = len(u)
  total = 0
  for i in range(n):      # n itérations
      total += u[i] * v[i]  # 1 multiplication + 1 addition
  return total

# Complexité : O(n)
# - n multiplications
# - n additions
# Total : 2n opérations → O(n)

Exemple 3 : produit matrice-vecteur

produit_matrice_vecteur.pypython

import numpy as np

def matrice_vecteur(A, x):
  """Calcule le produit Ax où A est n×n et x est n×1."""
  n = len(x)
  y = np.zeros(n)

  for i in range(n):          # n lignes
      for j in range(n):      # n colonnes
          y[i] += A[i,j] * x[j]  # 1 mult + 1 add

  return y

# Complexité : O(n²)
# - Boucle externe : n itérations
# - Boucle interne : n itérations chacune
# - Opérations par itération : 2
# Total : 2n² opérations → O(n²)

Exemple 4 : produit de deux matrices

produit_matriciel.pypython

def produit_matrices(A, B):
  """Calcule le produit AB où A et B sont n×n."""
  n = len(A)
  C = np.zeros((n, n))

  for i in range(n):          # n lignes de C
      for j in range(n):      # n colonnes de C
          for k in range(n):  # produit scalaire ligne × colonne
              C[i,j] += A[i,k] * B[k,j]

  return C

# Complexité : O(n³)
# - Trois boucles imbriquées de n itérations
# - 2 opérations par itération la plus interne
# Total : 2n³ opérations → O(n³)

⚠️

Impact pratique

Pour $n = 1000$ :

Produit matrice-vecteur : $\sim 10^6$ opérations
Produit matriciel : $\sim 10^9$ opérations

Le produit matriciel est 1000 fois plus coûteux !

Règles de comptage

Règle 1 : boucles imbriquées

Les complexités se multiplient :

python

for i in range(n):      # O(n)
  for j in range(n):  # × O(n)
      operation()     # = O(n²)

Règle 2 : boucles séquentielles

Les complexités s'additionnent (on garde le terme dominant) :

python

for i in range(n):      # O(n)
  operation1()

for j in range(n**2):   # O(n²)
  operation2()

# Total : O(n) + O(n²) = O(n²)

Règle 3 : conditions

On prend le pire cas :

python

if condition:
  boucle_lineaire()    # O(n)
else:
  boucle_quadratique() # O(n²)

# Complexité : O(n²) (pire cas)

Application : comparer deux algorithmes

Résolution d'un système linéaire $Ax = b$

Méthode	Complexité	n=100	n=1000	n=10000
Élimination de Gauss	$O(n^3)$	$10^6$	$10^9$	$10^{12}$
Gradient conjugué*	$O(kn^2)$	$10^5$	$10^7$	$10^9$
Gradient conjugué (creuse)*	$O(kn)$	$10^3$	$10^4$	$10^5$

* $k$ = nombre d'itérations jusqu'à convergence (souvent $k \ll n$ )

💡

Conclusion

Pour un système de 10 000 équations, le bon choix d'algorithme peut faire la différence entre quelques secondes et plusieurs heures de calcul.

Vérification expérimentale

verifier_complexite.pypython

import numpy as np
import time

def mesurer_temps(fonction, tailles):
  """Mesure le temps d'exécution pour différentes tailles."""
  temps = []
  for n in tailles:
      # Générer des données de taille n
      A = np.random.rand(n, n)
      x = np.random.rand(n)

      # Mesurer le temps
      debut = time.time()
      fonction(A, x)
      fin = time.time()

      temps.append(fin - debut)
  return temps

def matrice_vecteur(A, x):
  return A @ x

# Test
tailles = [100, 200, 400, 800, 1600]
temps = mesurer_temps(matrice_vecteur, tailles)

print("Vérification de O(n²) pour le produit matrice-vecteur")
print("-" * 50)
for i in range(1, len(tailles)):
  ratio_n = tailles[i] / tailles[i-1]
  ratio_t = temps[i] / temps[i-1]
  print(f"n × {ratio_n:.1f} → temps × {ratio_t:.1f} (attendu : {ratio_n**2:.1f})")

Sortie typique :

n × 2.0 → temps × 4.1 (attendu : 4.0)
n × 2.0 → temps × 3.9 (attendu : 4.0)
n × 2.0 → temps × 4.0 (attendu : 4.0)
n × 2.0 → temps × 4.2 (attendu : 4.0)

Le ratio de temps suit bien le carré du ratio de tailles → $O(n^2)$ confirmé.

FLOPS : mesure absolue de performance

Définition

Les FLOPS (Floating-point Operations Per Second) mesurent le nombre d'opérations virgule flottante par seconde. Les ordres de grandeur modernes :

Échelle	FLOPS	Exemple
GigaFLOPS	$10^9$ op/s	Laptop (1 cœur)
TeraFLOPS	$10^{12}$ op/s	GPU moderne
PetaFLOPS	$10^{15}$ op/s	Supercalculateur
ExaFLOPS	$10^{18}$ op/s	Frontier (2022)

Estimer le temps de calcul

\text{Temps} = \frac{\text{Nombre d'opérations}}{\text{FLOPS}}

Exemple : Produit de deux matrices $10\,000 \times 10\,000$ sur un laptop à 10 GFLOPS :

\text{Temps} = \frac{2 \times 10^{12}}{10^{10}} = 200 \text{ secondes}

À retenir

💡

Points clés

La notation $O()$ décrit comment le temps évolue avec la taille du problème
On ignore les constantes et on garde le terme dominant
Passer de $O(n^3)$ à $O(n^2)$ peut accélérer un calcul de 1000× pour $n = 1000$
Pour vérifier la complexité : doubler $n$ et observer le ratio des temps
Le choix de l'algorithme est souvent plus important que la puissance du matériel

Compter les opérations : la notation O()

Pourquoi compter les opérations ?

Question fondamentale

La notation grand O

Définition intuitive

Les classes de complexité courantes

Compter les opérations : exemples concrets

Exemple 1 : somme d'un vecteur

Exemple 2 : produit scalaire

Exemple 3 : produit matrice-vecteur

Exemple 4 : produit de deux matrices

Impact pratique

Règles de comptage

Règle 1 : boucles imbriquées

Règle 2 : boucles séquentielles

Règle 3 : conditions

Application : comparer deux algorithmes

Résolution d'un système linéaire Ax=bAx = bAx=b

Conclusion

Vérification expérimentale

FLOPS : mesure absolue de performance

Définition

Estimer le temps de calcul

À retenir

Points clés

Résolution d'un système linéaire $Ax = b$