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 (« grand O de f de n ») décrit le comportement asymptotique d'un algorithme quand la taille devient grande.

En pratique, on retient :

On ignore les constantes multiplicatives : et sont tous deux
On garde le terme dominant : est

Les classes de complexité courantes

Nom	Comportement	Exemple
Constante	Indépendant de n	Accès à un élément de tableau
Logarithmique	Très lent à croître	Recherche dichotomique
Linéaire	Proportionnel à n	Parcours d'une liste
Quasi-linéaire	Un peu plus que linéaire	Tri fusion, FFT
Quadratique	×100 si n×10	Produit matrice-vecteur
Cubique	×1000 si n×10	Produit matriciel, élimination de Gauss
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 :

Produit matrice-vecteur : opérations
Produit matriciel : 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

Méthode	Complexité	n=100	n=1000	n=10000
Élimination de Gauss
Gradient conjugué*
Gradient conjugué (creuse)*

* = nombre d'itérations jusqu'à convergence (souvent )

💡

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 → 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	op/s	Laptop (1 cœur)
TeraFLOPS	op/s	GPU moderne
PetaFLOPS	op/s	Supercalculateur
ExaFLOPS	op/s	Frontier (2022)

Estimer le temps de calcul

Exemple : Produit de deux matrices sur un laptop à 10 GFLOPS :

À retenir

💡

Points clés

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