Complexité algorithmique et taille des données

Bonjour ! Bienvenue dans cette nouvelle leçon.

Dans notre dernière session, nous avons appris à classer les algorithmes selon leur efficacité en utilisant la notation Big O. Nous avons établi une hiérarchie, de l'excellent $O (1)$ au très mauvais $O (2^{n})$ . C'est un peu comme savoir qu'une voiture de sport est plus rapide qu'un tracteur.

Aujourd'hui, nous allons aller plus loin. L'objectif est de comprendre et d'évaluer l'impact concret de la taille des données sur le temps d'exécution d'un algorithme. Autrement dit, si la voiture de sport et le tracteur doivent faire un trajet deux fois plus long, de combien leur temps de parcours augmente-t-il respectivement ? Comprendre cette "mise à l'échelle" (ou scalabilité) est fondamental pour anticiper la performance de vos futurs programmes et donc, pour écrire du "code clean" et efficace.

1. La croissance du temps d'exécution : une histoire de courbes

La notation Big O décrit la forme de la courbe de croissance du temps d'exécution d'un algorithme lorsque la taille des données d'entrée, notée n, augmente. Visualisons ces différentes formes.

Graphique des Classes de Complexité Algorithmique — Ce graphique illustre comment le temps d'exécution (axe vertical) évolue en fonction de la taille du problème (axe horizontal) pour différentes complexités. Chaque courbe raconte une histoire différente sur l'impact de 'n'.

Observons ces courbes :

$O (1)$ (Constant) : La ligne est plate. Peu importe si n est 10 ou 10 millions, le temps est le même.
$O (lo g n)$ (Logarithmique) : La courbe s'aplatit très vite. Même si n devient immense, le temps n'augmente que très peu.
$O (n)$ (Linéaire) : C'est une droite. Si on double la quantité de données n, on double le temps d'exécution. C'est une croissance proportionnelle et prévisible.
$O (n^{2})$ (Quadratique) : La courbe s'envole. Si on double n, le temps est multiplié par quatre ( $2^{2}$ ). L'impact de l'augmentation de n est déjà très significatif.
$O (2^{n})$ (Exponentiel) : La courbe monte de façon quasi-verticale. Le temps d'exécution explose à la moindre augmentation de n.

Ces formes de courbes sont la clé pour prédire le comportement d'un algorithme.

2. De la théorie aux chiffres : l'impact quantifié

Les graphiques donnent une bonne intuition, mais des chiffres concrets sont encore plus parlants pour mesurer l'impact de la taille des données.

Imaginons que nous fassions tourner des algorithmes de différentes complexités sur un ordinateur standard. Le document suivant présente un tableau qui calcule le temps d'exécution pour une taille d'entrée n = 10 000. C'est une excellente façon de se rendre compte des ordres de grandeur.

[PDF] Complexité d'un algorithme I Généralités

Pour vraiment saisir l'impact de la taille des données, rien ne vaut des chiffres concrets. Le document suivant présente un tableau saisissant qui montre combien de temps prendrait un algorithme en fonction de sa complexité pour une taille d'entrée donnée.

Lisez la section I.5, en vous concentrant particulièrement sur le tableau intitulé 'Quel est le temps d’exécution t(n) d’un algorithme avec n = 10⁴ entrées... ?'. L'expression 'Ce tableau est édifiant !' est très juste. Réfléchissez à ce que ces chiffres impliquent pour un programmeur.

Ce que ce tableau nous apprend est crucial :

Pour n = 10 000, les complexités $O (lo g n)$ , $O (n)$ et $O (n lo g n)$ donnent des temps de réponse quasi instantanés (de l'ordre de la nanoseconde ou de la microseconde).
La complexité $O (n^{2})$ commence à se faire sentir avec un temps de 1 milliseconde.
La complexité $O (n^{3})$ est déjà lente, avec 10 secondes. C'est inacceptable pour une action interactive dans une application.
La complexité $O (2^{n})$ est si grande qu'elle dépasse l'imagination. L'algorithme est totalement inutilisable pour cette taille de données.

On voit bien que l'impact de n n'est pas du tout le même selon la complexité !

3. Un exemple frappant : l'explosion de la complexité cubique $O (n^{3})$

Pour bien enfoncer le clou, regardons comment le temps évolue pour une même machine et un même algorithme, en faisant simplement varier n. L'image suivante illustre le cas d'un algorithme en $O (n^{3})$ , typiquement un algorithme avec trois boucles imbriquées.

Algorithmic Complexity: Impact of Input Size on Execution Time (O(n³)) — Cette image montre un algorithme en O(n³) et estime son temps d'exécution pour différentes tailles de listes. L'augmentation du temps est spectaculaire.

Analysez attentivement le tableau dans l'image :

Pour n = 1 000, le temps est de 15 secondes. C'est déjà long.
Pour n = 10 000 (10 fois plus de données), le temps n'est pas multiplié par 10, mais par $1 0^{3} = 1000$ . Le temps estimé est de 4 heures et 10 minutes.
Pour n = 100 000 (encore 10 fois plus), le temps est à nouveau multiplié par 1000. L'estimation atteint 173 jours.

Cet exemple démontre de manière spectaculaire le concept de mise à l'échelle. Pour un algorithme en $O (n^{3})$ , une multiplication de la taille des données par un facteur k entraîne une multiplication du temps d'exécution par un facteur $k^{3}$ .

4. Exercice pratique : estimez la performance

Votre tour de jouer ! En vous basant sur ce que nous venons de voir, essayez d'estimer les temps d'exécution dans les scénarios suivants. L'objectif n'est pas le calcul exact, mais le raisonnement sur l'ordre de grandeur.

Scénario 1 : Tri quadratique
Un algorithme de tri par sélection ( $O (n^{2})$ ) met 2 secondes pour trier un tableau de 5 000 éléments.
Question : Combien de temps prendrait-il approximativement pour trier un tableau de 10 000 éléments ?

Scénario 2 : Recherche linéaire
Un algorithme de recherche linéaire ( $O (n)$ ) parcourt une liste de 2 millions d'articles en 80 millisecondes.
Question : Combien de temps prendrait-il approximativement pour parcourir une liste de 200 000 articles ?

Scénario 3 : Recherche dichotomique
Un algorithme de recherche dichotomique ( $O (lo g n)$ ) trouve un mot dans un dictionnaire d'un million d'entrées en 5 microsecondes. Le dictionnaire est mis à jour et contient maintenant un milliard d'entrées (1000 fois plus).
Question : Le temps de recherche va-t-il exploser et devenir de l'ordre de la milliseconde (5 microsecondes x 1000) ?

Cliquez ici pour voir les solutions et les explications

Solution 1 : Tri quadratique

Le nombre d'éléments n est doublé (de 5 000 à 10 000).
La complexité est $O (n^{2})$ . Le temps d'exécution doit donc être multiplié par $2^{2} = 4$ .
Estimation : 2 secondes * 4 = 8 secondes.

Solution 2 : Recherche linéaire

Le nombre d'éléments n est divisé par 10 (de 2 000 000 à 200 000).
La complexité est $O (n)$ . Le temps d'exécution doit donc être divisé par 10.
Estimation : 80 ms / 10 = 8 millisecondes.

Solution 3 : Recherche dichotomique

Le nombre d'éléments n est multiplié par 1000 (de $1 0^{6}$ à $1 0^{9}$ ).
La complexité est $O (lo g n)$ . Le temps est proportionnel au logarithme de n.
$lo g_{2} (1 0^{6})$ est environ 20.
$lo g_{2} (1 0^{9})$ est environ 30.
Le nombre d'opérations passe de ~20 à ~30. Le temps ne sera donc pas multiplié par 1000, mais augmentera seulement de 50% environ.
Estimation : 5 microsecondes * 1.5 = 7.5 microsecondes. Le temps de recherche reste quasi-instantané, démontrant la puissance incroyable des algorithmes logarithmiques face à d'énormes volumes de données.

Conclusion

Cette leçon était dense mais fondamentale. Vous avez maintenant les outils pour non seulement classer les algorithmes, mais aussi pour prédire concrètement leur comportement face à des données de plus en plus volumineuses.

Points clés à retenir :

La complexité Big O décrit comment le temps d'exécution se met à l'échelle avec la taille de l'entrée n.
Pour une complexité linéaire $O (n)$ , doubler n double le temps.
Pour une complexité quadratique $O (n^{2})$ , doubler n quadruple le temps.
Pour une complexité logarithmique $O (lo g n)$ , doubler n n'ajoute qu'une petite quantité de travail constante.
Cette analyse prédictive est la raison pour laquelle le choix d'un algorithme efficace est l'une des décisions les plus importantes qu'un développeur puisse prendre, surtout à notre époque où les applications manipulent des quantités massives de données.

Et après ?

Nous venons de terminer notre exploration de l'analyse de complexité. Vous êtes maintenant armé pour évaluer l'efficacité d'un algorithme. Dans le prochain module, nous allons utiliser ces connaissances pour découvrir des stratégies algorithmiques plus avancées et élégantes. Nous commencerons par un principe puissant appelé "Diviser pour Régner", qui est à l'origine de certains des algorithmes de tri les plus rapides qui existent.

Recommended resources