16 - Complexité

Questions fondamentales

Les trois questions fondamentales à se poser à propos de tout algorithme sont les suivantes :

• donne-t-il un résultat ou ne s’arrête-t-il jamais ? (Notion de terminaison) ;
• donne-t-il le résultat attendu ou calcule-t-il autre chose ? (Notion de correction) ;
• donne-t-il le résultat en un temps raisonnable ou faut-il attendre très longtemps ? (Notion de complexité).

Principe

Dans ce chapitre, nous nous intéressons au coût en temps d’un algorithme (et non au coût en espace mémoire). La question centrale est : combien de temps un algorithme met-il à s’exécuter ?

Ce temps dépend de la taille des données fournies en entrée. On peut facilement concevoir qu’un programme de recherche n’a pas le même temps d’exécution selon que l’on cherche dans une liste de vingt mots ou dans l’ensemble du dictionnaire de la langue française.

Les ordinateurs n’ayant pas tous la même vitesse d’exécution, il convient d’évaluer le coût indépendamment de la machine. On raisonne donc en terme de nombre d’opérations élémentaires : chaque opération simple (comparaison, affectation, opération arithmétique, accès à un élément, etc.) compte pour une étape de calcul.

Meilleur, pire et cas moyen

Pour une même taille de données, le temps d’exécution peut varier selon la configuration des données. On distingue :

• le meilleur des cas : temps minimal pour toutes les entrées de taille \(n\) ;
• le cas moyen : temps moyen pour toutes les entrées de taille \(n\) ;
• le pire des cas : temps maximal pour toutes les entrées de taille \(n\).

Nous nous intéresserons principalement au pire des cas, car il fournit une garantie : l’algorithme ne sera jamais plus lent que cette borne.

Exemple. Considérons la recherche d’un élément dans une liste non triée de \(n\) éléments. Dans le meilleur des cas, l’élément est en première position (une seule comparaison). Dans le pire des cas, il est en dernière position ou absent (\(n\) comparaisons).

La notation \(\mathcal{O}\)

La complexité ne retient qu’un ordre de grandeur du nombre d’opérations, en négligeant les constantes et les termes de moindre degré. On utilise la notation \(\mathcal{O}\) (lire « grand O »), qui donne une borne supérieure du taux de croissance.

Règles pratiques :

• On ne garde que le terme dominant (celui qui croît le plus vite).
• On supprime les coefficients multiplicatifs.

Exemples :

• \(2n + 5\) opérations \(\to \mathcal{O}(n)\) (on ignore le \(+5\) et le coefficient 2)
• \(3n^2 + 5n - 2\) opérations \(\to \mathcal{O}(n^2)\) (le terme \(n^2\) domine)
• \(\frac{n}{2}\) opérations \(\to \mathcal{O}(n)\) (le coefficient \(\frac{1}{2}\) est ignoré)

Autrement dit, des algorithmes en \(n\), \(2n + 5\) ou \(\frac{n}{2}\) opérations ont tous la même classe de complexité : \(\mathcal{O}(n)\).

Classes de complexité

Il est possible de catégoriser les algorithmes par classes de complexité. Voici les principales, rangées par ordre croissant de temps d’exécution :

Conséquences pratiques

Le tableau ci-dessous donne le temps approximatif d’exécution en fonction de la taille des données, en supposant qu’une opération prend 1 µs (\(10^{-6}\) secondes).

À retenir. Multiplier la taille des données par 10 :

• multiplie le temps par 10 si la complexité est linéaire \(\mathcal{O}(n)\) ;
• multiplie le temps par 100 si la complexité est quadratique \(\mathcal{O}(n^2)\) ;
• ajoute une constante au temps si la complexité est logarithmique \(\mathcal{O}(\log n)\) ;
• élève le temps à la puissance 10 si la complexité est exponentielle \(\mathcal{O}(2^n)\).

C’est pourquoi les algorithmes exponentiels sont considérés comme impraticables pour des données de grande taille.

Exemple guidé : compter les opérations

Recherche séquentielle

def recherche(L, x):
    """Cherche x dans la liste L. Renvoie True si trouvé, False sinon."""
    for i in range(len(L)):
        if L[i] == x:
            return True
    return False

Comptons les opérations dans le pire des cas (l’élément n’est pas dans la liste, de longueur \(n\)) :

• La boucle for s’exécute \(n\) fois.
• À chaque tour : un accès à L[i] (une opération) et une comparaison == x (une opération), soit 2 opérations par tour.
• Total : \(2n\) opérations.

La complexité au pire des cas est donc \(\mathcal{O}(n)\) : linéaire.

Somme de deux listes

def somme_listes(L1, L2):
    """Renvoie la liste des sommes élément par élément."""
    n = len(L1)
    resultat = []
    for i in range(n):
        resultat.append(L1[i] + L2[i])
    return resultat

La boucle s’exécute \(n\) fois. À chaque tour : deux accès, une addition, un append. La complexité est \(\mathcal{O}(n)\).

Exemple : la fonction mystère

Un élève un peu anxieux a réalisé le code suivant.

def mystere(L):
    nombre = L[0]
    n = len(L)
    for i in range(n):
        if nombre < L[i]:
            nombre = L[i]
        # Deuxième vérification au cas où
        for j in range(i):
            if nombre < L[j]:
                nombre = L[j]
    return nombre

1. Que fait cette fonction ? Elle renvoie le maximum de la liste L. La boucle interne est inutile : la première comparaison suffit déjà.

2. Complexité. La boucle externe s’exécute \(n\) fois. Pour chaque valeur de \(i\), la boucle interne s’exécute \(i\) fois. Le nombre total d’itérations de la boucle interne est donc : \[0 + 1 + 2 + \ldots + (n-1) = \frac{n(n-1)}{2}\] La complexité est \(\mathcal{O}(n^2)\) : quadratique. L’élève aurait pu écrire un algorithme en \(\mathcal{O}(n)\) en supprimant simplement la boucle interne.

Exercices

Exercice 1 : déterminer la complexité de référence

Pour chaque expression, donner la complexité de référence correspondante :

1. \(3n^2 + 5n - 2 = \mathcal{O}(\ldots)\)
2. \(n^3 + 5n^2 + 2 = \mathcal{O}(\ldots)\)
3. \(\frac{1}{3}n^4 + 7n^3 + 2n = \mathcal{O}(\ldots)\)
4. \(2 + 3n\log(n) = \mathcal{O}(\ldots)\)
5. \(n\log(n) + 2^n + 7n^3 = \mathcal{O}(\ldots)\)
6. \(n! + 8^n + 9n^2 = \mathcal{O}(\ldots)\)

Exercice 2 : analyser un algorithme

Déterminer la complexité au pire des cas de chacune des fonctions suivantes.

a) Calcul de la somme des éléments d’une liste :

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

b) Recherche d’un doublon :

def a_doublon(L):
    n = len(L)
    for i in range(n):
        for j in range(i + 1, n):
            if L[i] == L[j]:
                return True
    return False

c) Division par deux successive :

def nb_divisions(n):
    compteur = 0
    while n > 1:
        n = n // 2
        compteur += 1
    return compteur

Exercice 3 : comparer expérimentalement

On souhaite mesurer expérimentalement la complexité de la fonction a_doublon de l’exercice 2b.

1. Utiliser le module time pour mesurer le temps d’exécution sur des listes de tailles 1000, 2000, 5000 et 10000 (sans doublons, pour être dans le pire des cas).
2. Vérifier que lorsque la taille est multipliée par 2, le temps est approximativement multiplié par 4 (caractéristique d’une complexité quadratique).

import time

def a_doublon(L):
    n = len(L)
    for i in range(n):
        for j in range(i + 1, n):
            if L[i] == L[j]:
                return True
    return False

for taille in [1000, 2000, 5000, 10000]:
    L = list(range(taille))  # pas de doublon
    debut = time.time()
    a_doublon(L)
    fin = time.time()
    print(f"n = {taille:>5} : {fin - debut:.4f} s")

Exercice 4 : optimiser

La fonction suivante vérifie si tous les éléments d’une liste sont distincts. Sa complexité est \(\mathcal{O}(n^2)\).

def tous_distincts(L):
    n = len(L)
    for i in range(n):
        for j in range(i + 1, n):
            if L[i] == L[j]:
                return False
    return True

Proposer un algorithme plus efficace (en \(\mathcal{O}(n \log n)\) ou \(\mathcal{O}(n)\)) pour résoudre le même problème.

Exercice 5 : prédire le temps

Un algorithme en \(\mathcal{O}(n^2)\) met 0,5 seconde à traiter 1000 éléments.

1. Combien de temps mettra-t-il approximativement pour 10 000 éléments ?
2. Quelle taille de données peut-il traiter en moins d’une minute ?