Complexité temporelle

Complexité temporelle et spatiale

Complexités

• Complexité temporelle (en temps) : temps de calcul
• Complexité spatiale (en espace) : mémoire requise
• Complexité pratique : mesure précise pour une machine donnée
• Complexité théorique : ordre de grandeur indépendant de la machine

Opérations représentatives

Pour quantifier la complexité, on identifie une ou plusieurs opérations représentatives :

• Comparaisons de lettres
• Échanges ou transferts d'éléments
• Opérations arithmétiques
• Accès aux données

Taille des données

La taille n des données est : longueur d'un tableau, nombre de lignes/colonnes, etc.

Notations O, Ω, Θ

Soit g une fonction positive.

Grand O

O(g) = { f | ∃α>0, ∃n₀, ∀n≥n₀, f(n) ≤ α·g(n) }

f est au plus de l'ordre de g.

Grand Ω

Ω(g) = { f | ∃α>0, ∃n₀, ∀n≥n₀, f(n) ≥ α·g(n) }

f est au moins de l'ordre de g.

Grand Θ

Θ(g) = O(g) ∩ Ω(g)

f est exactement de l'ordre de g.

Classes courantes

Règles pratiques

1. Somme : O(f) + O(g) = O(max(f, g))
2. Produit : O(f) × O(g) = O(f × g)
3. Constantes ignorées : O(3n² + 2n + 10) = O(n²)
4. Base des logarithmes ignorée : O(log₂ n) = O(ln n) = O(log n)

Complexité maximale, minimale et moyenne

Définitions

• Complexité maximale (pire cas) : pour les données de taille n les plus défavorables
• Complexité minimale (meilleur cas) : pour les données les plus favorables
• Complexité moyenne : moyenne sur toutes les données de taille n (nécessite des hypothèses probabilistes)

Exemple : recherche séquentielle

int prem(int x[], int n, int a) {
    for (int k = 0; k < n; k++)
        if (x[k] == a) return k;
    return -1;
}

• Complexité : Ω(1), O(n), Θ(n) en moyenne

Impact du multiplicateur matériel

Aucun progrès technologique ne change la classe de complexité d'un algorithme.

Multiplier la puissance par 1000 ne permet de traiter qu'un problème de taille N+10 pour un algorithme exponentiel, contre 1000N pour un algorithme linéaire.