Un programme qui fonctionne, c'est bien. Un programme qui fonctionne efficacement, c'est mieux. Quand on manipule de grandes quantités de données, la différence entre un algorithme rapide et un algorithme lent n'est pas une question de secondes, mais parfois de minutes, d'heures, voire de jours.

Mais comment mesurer l'« efficacité » ? On ne peut pas se fier au temps d'exécution sur une machine spécifique, car cela dépend du processeur, de la mémoire et d'autres facteurs. On a besoin d'une méthode universelle pour décrire comment la performance d'un algorithme évolue lorsque la taille des données d'entrée augmente. C'est là qu'intervient la notation Grand O (Big O notation).

La notation Grand O nous donne une approximation de la complexité d'un algorithme en se concentrant sur son comportement à grande échelle. On ignore les constantes et les termes de plus bas degré pour ne garder que ce qui domine lorsque la taille de l'entrée, notée n, devient très grande.

On distingue deux types principaux de complexité :

• Complexité temporelle : Le nombre d'opérations que l'algorithme exécute en fonction de n.
• Complexité spatiale : La quantité de mémoire supplémentaire que l'algorithme utilise en fonction de n.

Par exemple, un algorithme qui parcourt une liste de n éléments une seule fois pour trouver une valeur a une complexité temporelle de $O(n)$. Si l'algorithme accède directement à un élément via son index, l'opération est en temps constant, soit $O(1)$, car le temps ne dépend pas de la taille de la liste.

La performance d'un algorithme n'est pas toujours constante. Elle peut varier considérablement en fonction de la structure des données d'entrée. Pour avoir une image complète, on analyse trois scénarios clés :

Prenons l'exemple du tri par insertion. Cet algorithme parcourt une liste et insère chaque élément à sa place correcte dans la partie déjà triée. Si la liste est déjà triée (meilleur cas), l'algorithme n'a qu'à la parcourir une fois, ce qui donne une complexité de $O(n)$.

En revanche, si la liste est triée en ordre inverse (pire cas), chaque élément doit être déplacé jusqu'au début de la liste. Cela nécessite un nombre d'opérations proportionnel au carré de la taille de la liste, soit $O(n^2)$. En pratique, c'est souvent la complexité du pire cas qui nous intéresse le plus, car elle garantit une borne supérieure sur la performance de l'algorithme, quelles que soient les données.

Pour dépasser les limites des algorithmes en $O(n^2)$, les informaticiens ont développé des stratégies plus astucieuses. L'une des plus puissantes est le paradigme « Diviser pour régner ». L'idée est simple et élégante :

1. Diviser : Scinder le problème principal en plusieurs sous-problèmes plus petits du même type.
2. Régner : Résoudre les sous-problèmes de manière récursive. Si les sous-problèmes sont assez petits, on les résout directement.
3. Combiner : Fusionner les solutions des sous-problèmes pour obtenir la solution du problème initial.

Le tri fusion (MergeSort) est l'exemple parfait de cette approche. Il divise une liste en deux moitiés, trie récursivement chaque moitié, puis fusionne les deux moitiés triées en une seule liste. Ce processus de fusion est l'étape clé où le travail s'effectue.

La magie de cette approche est que la complexité temporelle du tri fusion est de $O(n \log n)$ dans tous les cas. Pour de grandes listes, la différence avec $O(n^2)$ est astronomique. Un autre algorithme célèbre utilisant ce paradigme est le tri rapide (QuickSort), qui est souvent plus rapide en pratique mais dont le pire cas est en $O(n^2)$.

Les algorithmes de type « Diviser pour régner » sont presque toujours implémentés à l'aide de la récursivité. Une fonction récursive est une fonction qui s'appelle elle-même pour résoudre une version plus petite du même problème.

Chaque fonction récursive doit avoir deux composantes essentielles :

L'exemple classique est le calcul de la factorielle d'un nombre n, notée $n!$. La factorielle de 5 est $5 \times 4 \times 3 \times 2 \times 1$. On peut la définir de manière récursive : la factorielle de n est $n$ multiplié par la factorielle de $(n-1)$. Le cas de base est que la factorielle de 0 est 1.

L'analyse de la complexité des algorithmes récursifs se fait à l'aide de relations de récurrence (recurrence relations). Ce sont des équations qui décrivent le coût d'un algorithme en fonction de son coût sur des entrées plus petites. Pour le tri fusion, la relation est $T(n) = 2T(n/2) + O(n)$, ce qui signifie que le temps pour trier n éléments est égal à deux fois le temps pour trier n/2 éléments (les deux appels récursifs), plus le temps pour fusionner les résultats ($O(n)$). La résolution de cette relation donne bien $O(n \log n)$.

Comprendre ces concepts de complexité, de paradigmes et de récursivité est essentiel. Cela permet de ne pas seulement écrire du code qui fonctionne, mais d'écrire du code intelligent, optimisé et capable de gérer les défis du monde réel.