Complexité des algorithmes

En bref

Résumé de l’article

Dans cet article, vous allez découvrir une notion théorique importante pour comparer les algorithmes : la complexité. Dans les articles précédents, vous avez déjà rencontré des notations comme $O(n)$. Nous allons maintenant les expliciter davantage.

Points clés à retenir

• La complexité d’un algorithme est une mesure abstraite du temps nécessaire pour l’exécuter, en fonction de ses entrées.

• Elle fait abstraction des éléments spécifiques à la machine, comme les performances du processeur, contrairement aux mesures de temps.

• La complexité est généralement donnée dans le pire des cas.

• Nous utilisons la notation $O(\cdot)$, car nous nous intéressons à l’ordre de grandeur du temps nécessaire, de manière asymptotique.

Contenu de l’article

Vidéo

Veuillez consulter la vidéo ci-dessous (en anglais, affichez les sous-titres si besoin). Nous fournissons également une traduction du contenu de la vidéo juste après, si vous préférez.

Ordres de grandeur

La notation $O(\cdot)$ dit comment le temps de calcul évolue avec la taille de l’entrée. Pour se rendre compte de ce que cela représente concrètement, voici le temps nécessaire pour effectuer $f(n)$ opérations élémentaires, en supposant qu’un ordinateur en effectue un milliard ($10^9$) par seconde :

Les complexités polynomiales restent raisonnables même pour de grandes entrées, alors que les complexités exponentielles et factorielles deviennent inutilisables très vite : passer de 10 à 20 éléments fait passer un algorithme en $O(n!)$ de quelques millisecondes à plusieurs dizaines d’années. Aucune amélioration du matériel ne compense une telle croissance : un ordinateur mille fois plus rapide ne permet de traiter qu’une dizaine d’éléments de plus avec un algorithme en $O(2^n)$, et seulement 2 ou 3 avec un algorithme en $O(n!)$.

Appliquons cela à PyRat. Un labyrinthe de taille par défaut compte 156 cases, et une partie par défaut contient 21 morceaux de fromage :

• Un parcours en largeur, en $O(n)$ dans un labyrinthe, traite ces 156 cases en une fraction de milliseconde.
• L’algorithme de Dijkstra, en $O(n \cdot log(n))$, n’est guère plus coûteux.
• En revanche, essayer tous les ordres possibles pour ramasser les 21 morceaux de fromage demande d’examiner $21! \approx 5 \cdot 10^{19}$ ordres, soit environ 1600 ans à un milliard d’ordres par seconde.

C’est pourquoi les séances suivantes s’intéressent à des algorithmes plus astucieux, ou qui acceptent de ne pas trouver la meilleure solution.

Pour aller plus loin

Remarques sur la complexité des algorithmes

Il est souvent tentant de comparer les comportements asymptotiques des complexités des algorithmes pour tirer des conclusions. C’est pourquoi elles sont le plus souvent utilisées, mais parfois le diable se cache dans les détails.

Pire cas

La complexité d’un algorithme est définie comme le nombre d’opérations élémentaires nécessaires dans le pire des cas. En pratique, l’algorithme peut être rapide dans presque tous les cas. Un exemple d’algorithme célèbre avec cette propriété est l’algorithme du simplexe.

Comportement asymptotique

Prenons deux fonctions $f$ et $g$ de $n$. Nous pouvons assez facilement avoir $f(n) = O(g(n))$ et pourtant $f(n) > g(n)$ pour tout $n > N$. En pratique, certains algorithmes peuvent avoir un comportement asymptotique plus favorable mais être beaucoup plus lents en pratique. Un exemple célèbre est le test de primalité.

Importance des constantes

Les écritures de comportement asymptotique ignorent les constantes. En particulier, nous pouvons écrire $10^{10^{10^{10^{10}}}} n^2 = O(n^2)$. Cependant, un algorithme dont la complexité est exactement $10^{10^{10^{10^{10}}}} n^2$ est $10^{10^{10^{10^{10}}}}$ fois plus lent qu’un algorithme dont la complexité est exactement $n^2$.

Les coûts cachés des opérations de Python

Pour calculer la complexité d’un programme, on compte ses opérations : les instructions qui se suivent s’additionnent, et le contenu d’une boucle est multiplié par son nombre de tours. Encore faut-il savoir ce que coûte chaque opération. En Python, certaines instructions qui tiennent en une ligne cachent en réalité une boucle sur toute une structure de données :

Une opération en $O(n)$ placée dans une boucle de $n$ tours donne un programme en $O(n^2)$, même s’il ne contient qu’une seule boucle. Par exemple, voici deux manières de retirer les doublons d’une liste de sommets visités (en gardant l’ordre) :

# Quadratic version: "in" goes through the whole list at each iteration
visited = []
for vertex in path:
    if vertex not in visited:
        visited.append(vertex)

# Linear version: "in" takes a constant time (on average) on a set
visited = []
seen = set()
for vertex in path:
    if vertex not in seen:
        seen.add(vertex)
        visited.append(vertex)

Les deux versions donnent le même résultat, mais voici leurs temps d’exécution pour des listes de différentes tailles :

Quand la taille double, le temps de la première version est multiplié par 4, ce qui est la signature d’une complexité quadratique, alors que celui de la seconde est multiplié par 2. C’est aussi pourquoi l’article sur les parcours de graphes recommande une deque plutôt qu’une liste et pop(0) pour la file du BFS.

Pour aller encore plus loin

• Fonction d’Ackermann

  Cette fonction qui croît très rapidement apparaît parfois dans la complexité de certains algorithmes très exigeants.
• L’algorithme du simplexe

  Un algorithme populaire pour résoudre des problèmes d’optimisation linéaire, de complexité exponentielle dans le pire des cas, mais rapide en pratique.
• Le test de primalité

  Déterminer si un nombre est premier a un comportement asymptotique favorable mais est lent en pratique.