Complexité des algorithmes

L'étude de la complexité algorithmique est fondamentale en informatique. Elle nous permet de comprendre et de prédire la performance des programmes que nous écrivons. Imaginez que vous avez plusieurs recettes pour faire un gâteau : certaines sont rapides, d'autres prennent beaucoup de temps, et d'autres encore demandent beaucoup d'ingrédients. En informatique, c'est pareil pour les algorithmes.

L'objectif principal est de pouvoir réaliser une comparaison d'algorithmes de manière objective. Si deux algorithmes résolvent le même problème, comment choisir le meilleur ? Intuitivement, on pourrait penser à tester les deux et voir lequel est le plus rapide. Cependant, cette approche a des limites, comme nous le verrons plus tard. L'analyse de la complexité offre une méthode théorique pour évaluer cette efficacité.

L'importance en informatique de cette discipline est cruciale. Elle permet aux développeurs de :

• Choisir l'algorithme le plus adapté à un problème donné, surtout quand la taille des données augmente.
• Anticiper le comportement d'un programme face à des volumes de données importants.
• Identifier les goulots d'étranglement (les parties lentes) d'un programme pour les optimiser.
• Concevoir des algorithmes plus efficaces dès le départ.

En résumé, étudier la complexité, c'est apprendre à évaluer la "qualité" d'un algorithme indépendamment de la machine qui l'exécute ou du langage de programmation utilisé.

La complexité d'un algorithme est une mesure des ressources consommées par cet algorithme pour s'exécuter. Ces ressources sont principalement de deux types :

1. Complexité temporelle : C'est la quantité de temps qu'un algorithme prend pour s'exécuter en fonction de la taille de ses données d'entrée. Il ne s'agit pas du temps réel mesuré en secondes (qui dépend de la machine), mais du nombre d'opérations élémentaires effectuées.
2. Complexité spatiale : C'est la quantité de mémoire (espace de stockage) qu'un algorithme requiert pour s'exécuter, toujours en fonction de la taille de ses données d'entrée. Cela inclut la mémoire pour stocker les variables, les structures de données, etc.

Le but est de trouver une fonction mathématique qui décrit comment le temps ou l'espace nécessaire augmente à mesure que la taille des données d'entrée (souvent notée $N$) augmente. Par exemple, si un algorithme prend $N$ étapes pour un problème de taille $N$, sa complexité temporelle sera "linéaire". Si un autre prend $N^2$ étapes, elle sera "quadratique".

Il existe deux grandes manières d'évaluer la performance d'un algorithme :

1. Mesure du temps d'exécution (approche empirique) : Cette méthode consiste à implémenter l'algorithme et à le faire tourner sur un ordinateur, en mesurant le temps qu'il prend pour différentes tailles de données d'entrée. On utilise des fonctions de chronométrage fournies par les langages de programmation.

   • Avantages : Donne une mesure concrète et réelle.
   • Inconvénients (limites de l'approche empirique) :
     • Dépend de la machine utilisée (processeur, RAM, etc.).
     • Dépend du langage de programmation et du compilateur/interpréteur.
     • Dépend des autres programmes exécutés en même temps sur la machine.
     • Nécessite d'implémenter l'algorithme avant de pouvoir le tester.
     • Ne permet pas de prédire le comportement sur des entrées beaucoup plus grandes que celles testées.

2. Nécessité d'une approche théorique : Pour pallier les limites de l'approche empirique, on utilise l'analyse théorique de la complexité. Cette approche est indépendante de la machine et du langage. Elle se concentre sur le nombre d'opérations élémentaires que l'algorithme doit effectuer.

   • Elle permet de prédire la croissance du temps d'exécution lorsque la taille des données d'entrée tend vers l'infini.
   • Elle facilite la comparaison objective d'algorithmes.
   • Elle permet d'évaluer un algorithme avant même de l'avoir codé.

C'est cette approche théorique que nous allons explorer en détail, en nous concentrant principalement sur la complexité temporelle.

Une opération élémentaire est une opération qui prend un temps constant et borné, quelle que soit la taille des données. On considère généralement que les opérations suivantes sont élémentaires :

• Affectation : x = 5, y = a.
• Comparaison : a < b, x == y.
• Opération arithmétique : a + b, x * 2, y / 3.
• Accès mémoire : Lecture ou écriture d'une valeur dans une variable ou à une adresse spécifique dans un tableau (ex: tab[i]).
• Appel de fonction sans boucle ou récursion (si son corps est constant).

Chacune de ces opérations est considérée comme prenant "une unité de temps". Le but est de compter combien de ces unités de temps sont nécessaires en fonction de la taille de l'entrée $N$.

Les boucles sont souvent les parties les plus coûteuses d'un algorithme car elles répètent un bloc d'opérations plusieurs fois.

Boucle for

Considérons une boucle for simple :

somme = 0
for i in range(n): # n représente la taille de l'entrée
    somme = somme + i

• L'initialisation somme = 0 est 1 opération.
• La boucle for i in range(n) va s'exécuter n fois (pour i allant de 0 à n-1).
• À chaque itération :
  • somme = somme + i : 1 addition, 1 affectation (2 opérations).
  • L'incrémentation de i et la comparaison i < n sont également des opérations (environ 2 par itération).
• Total : $1 \text{ (initialisation)} + n \times (2 \text{ (corps de boucle)} + 2 \text{ (gestion de boucle)})$
• Soit environ $4n + 1$ opérations.
• Lorsque $n$ devient très grand, le terme $4n$ domine. On dit que la complexité est linéaire en $n$.

Boucle while

Le principe est similaire pour une boucle while :

i = 0
while i < n: # n représente la taille de l'entrée
    print(i)
    i = i + 1

• L'initialisation i = 0 est 1 opération.
• La condition i < n est évaluée n+1 fois (la dernière fois pour sortir de la boucle).
• Le corps de la boucle s'exécute n fois :
  • print(i) : 1 opération (affichage).
  • i = i + 1 : 1 addition, 1 affectation (2 opérations).
• Total : $1 \text{ (initialisation)} + (n+1) \text{ (comparaisons)} + n \times (1 \text{ (print)} + 2 \text{ (incrémentation)})$
• Soit environ $4n + 2$ opérations.
• Là encore, la complexité est linéaire en $n$.

Le nombre d'itérations est la clé de l'analyse des boucles.

Les structures conditionnelles (if/else) introduisent une notion de choix dans l'exécution de l'algorithme.

if condition:
    # Bloc A
else:
    # Bloc B

Pour analyser la complexité d'une structure conditionnelle, on doit considérer différents scénarios :

• Cas le pire (worst-case) : C'est le scénario qui entraîne le plus grand nombre d'opérations. C'est généralement celui que l'on privilégie pour l'analyse de la complexité car il garantit que l'algorithme ne fera jamais "pire" que cette estimation.
• Cas le meilleur (best-case) : C'est le scénario qui entraîne le plus petit nombre d'opérations. C'est rarement utilisé car il ne donne aucune garantie sur la performance générale.
• Cas moyen (average-case) : C'est le nombre moyen d'opérations effectuées sur toutes les entrées possibles. C'est souvent difficile à calculer car cela nécessite des hypothèses sur la distribution des entrées.

Exemple : Recherche d'un élément dans un tableau non trié.

• Cas le pire : L'élément recherché est le dernier du tableau, ou il n'est pas dans le tableau. L'algorithme doit parcourir tout le tableau (complexité linéaire).
• Cas le meilleur : L'élément recherché est le premier du tableau. L'algorithme le trouve immédiatement (complexité constante).

Reprenons quelques algorithmes pour illustrer le comptage des opérations. Pour simplifier, nous allons nous concentrer sur le nombre de fois qu'une opération "clé" est exécutée.

Recherche séquentielle (ou linéaire)

On cherche un élément x dans un tableau tab de taille n.

def recherche_seq(tab, x):
    for i in range(len(tab)): # Boucle s'exécute len(tab) = n fois max
        if tab[i] <mark> x:      # 1 comparaison par itération
            return True
    return False

• Cas le pire : x n'est pas dans le tableau, ou x est le dernier élément. La boucle s'exécute n fois. Chaque itération fait une comparaison. La complexité est linéaire, proportionnelle à $n$. On écrira $O(n)$.
• Cas le meilleur : x est le premier élément. La boucle s'exécute 1 fois. La complexité est constante==. On écrira $O(1)$.
• Cas moyen : Si l'élément est présent, il est en moyenne au milieu du tableau, soit $\frac{n}{2}$ comparaisons. La complexité reste $O(n)$.

Calcul de somme

Calculer la somme de tous les éléments d'un tableau de taille n.

def calculer_somme(tab):
    somme = 0
    for element in tab: # Boucle s'exécute n fois
        somme = somme + element # 1 addition, 1 affectation
    return somme

• La boucle s'exécute n fois. À chaque itération, il y a un nombre constant d'opérations (une addition, une affectation).
• La complexité est toujours linéaire, proportionnelle à $n$. On écrira $O(n)$.

Recherche du maximum

Trouver le plus grand élément dans un tableau de taille n.

def trouver_max(tab):
    if not tab:
        return None # Gérer le cas du tableau vide
    
    maximum = tab[0] # 1 initialisation
    for i in range(1, len(tab)): # Boucle s'exécute n-1 fois
        if tab[i] > maximum: # 1 comparaison par itération
            maximum = tab[i] # 1 affectation (pas toujours exécutée)
    return maximum

• La boucle s'exécute $n-1$ fois. À chaque itération, il y a au moins une comparaison.
• Le nombre d'affectations de maximum varie, mais la comparaison est toujours là.
• La complexité est linéaire, proportionnelle à $n$. On écrira $O(n)$.

La notation Grand O (prononcé "grand O" ou "O de") est la plus couramment utilisée. Elle décrit la borne supérieure du temps d'exécution d'un algorithme. En d'autres termes, elle nous donne un ordre de grandeur du temps d'exécution dans le cas le pire.

Formellement, on dit qu'une fonction $f(n)$ est $O(g(n))$ s'il existe des constantes positives $c$ et $n_0$ telles que pour tout $n \ge n_0$, $0 \le f(n) \le c \cdot g(n)$. En clair, cela signifie que pour des valeurs de $n$ suffisamment grandes, $f(n)$ ne croîtra jamais plus vite que $g(n)$ multiplié par une constante.

Exemple : Si un algorithme prend $4n+1$ opérations, on dit qu'il est $O(n)$.

• On ignore les constantes multiplicatives (ici 4) car pour de très grands $n$, elles sont moins importantes que la puissance de $n$.
• On ignore les termes d'ordre inférieur (ici +1) car pour de très grands $n$, ils deviennent négligeables par rapport au terme dominant ($4n$).

L'objectif est de trouver la fonction $g(n)$ la plus simple possible qui représente le taux de croissance de $f(n)$.

Voici les classes de complexité les plus courantes, classées de la plus efficace à la moins efficace pour de grandes valeurs de $N$ :

• $O(1)$ : constante
  • Le temps d'exécution ne dépend pas de la taille de l'entrée. C'est le plus rapide !
  • Exemple : Accéder à un élément dans un tableau par son index (tab[5]).
• $O(\log n)$ : logarithmique
  • Le temps d'exécution augmente très lentement avec la taille de l'entrée. Souvent rencontré avec les algorithmes qui divisent le problème en deux à chaque étape.
  • Exemple : Recherche dichotomique dans un tableau trié.
• $O(n)$ : linéaire
  • Le temps d'exécution est directement proportionnel à la taille de l'entrée.
  • Exemple : Recherche séquentielle, parcours d'un tableau, calcul de somme.
• $O(n \log n)$ : quasi-linéaire
  • Plus lent que linéaire, mais beaucoup plus rapide que quadratique. C'est la complexité de certains des algorithmes de tri les plus efficaces.
  • Exemple : Tri fusion, Tri rapide (en moyenne).
• $O(n^2)$ : quadratique
  • Le temps d'exécution est proportionnel au carré de la taille de l'entrée. Souvent rencontré avec des boucles imbriquées.
  • Exemple : Tri par sélection, Tri par insertion, Tri à bulles.
• $O(2^n)$ : exponentielle
  • Le temps d'exécution double à chaque fois que la taille de l'entrée augmente d'une unité. Devient très vite impraticable même pour de petites valeurs de $N$.
  • Exemple : Calcul de la suite de Fibonacci par récursion naïve, résolution du problème du voyageur de commerce par force brute.

Tableau comparatif des croissances (pour $N=1000$) :

On voit clairement l'impact de l'ordre de grandeur sur la performance. Un algorithme $O(n^2)$ est acceptable pour $N=100$, mais catastrophique pour $N=100000$.

Pour déterminer la complexité d'un algorithme :

1. Identifier la variable d'entrée $N$ : C'est la taille des données (nombre d'éléments dans un tableau, longueur d'une chaîne, etc.).
2. Compter les opérations élémentaires : Estimer combien d'opérations sont réalisées en fonction de $N$. Concentrez-vous sur les boucles et les appels récursifs.
3. Identifier le terme dominant : Si vous avez une expression comme $3N^2 + 5N + 10$, le terme dominant est $3N^2$.
4. Simplifier l'expression avec la notation Grand O : On supprime les constantes multiplicatives et les termes d'ordre inférieur. $3N^2 + 5N + 10$ devient $O(N^2)$.

Exemple : Boucles imbriquées

for i in range(n):
    for j in range(n):
        print(i, j)

• La boucle extérieure s'exécute n fois.
• Pour chaque exécution de la boucle extérieure, la boucle intérieure s'exécute n fois.
• Le corps de la boucle intérieure (print(i, j)) s'exécute $n \times n = n^2$ fois.
• La complexité est donc $O(n^2)$.

La comparaison d'ordres de grandeur est essentielle. Un algorithme $O(n \log n)$ sera toujours préférable à un $O(n^2)$ pour de grandes valeurs de $N$, même si pour de très petits $N$, l'algorithme $O(n^2)$ pourrait être plus rapide à cause des constantes cachées par la notation Grand O.

Les algorithmes de tri réorganisent les éléments d'une liste dans un ordre spécifique (croissant ou décroissant). La complexité est généralement mesurée par le nombre de comparaisons et d'échanges.

Tri par sélection ($O(n^2)$)

Le tri par sélection fonctionne en trouvant le plus petit élément du tableau non trié et en le plaçant au début. Il répète ce processus pour le reste du tableau.

• Pour trouver le minimum dans un tableau de $N$ éléments, il faut $N-1$ comparaisons.
• Ensuite, on échange cet élément.
• Pour le deuxième plus petit, on cherche dans les $N-1$ éléments restants, soit $N-2$ comparaisons.
• ...
• Le nombre total de comparaisons est $(N-1) + (N-2) + \dots + 1 = \frac{N(N-1)}{2}$.
• La complexité est donc $O(N^2)$ (quadratique).

Tri par insertion ($O(n^2)$)

Le tri par insertion construit la liste triée un élément à la fois. À chaque étape, il prend un élément du tableau non trié et l'insère à sa position correcte dans la partie déjà triée.

• Pour insérer le 2ème élément, il faut au maximum 1 comparaison et 1 déplacement.
• Pour insérer le 3ème élément, il faut au maximum 2 comparaisons et 2 déplacements.
• ...
• Pour insérer le $N$-ième élément, il faut au maximum $N-1$ comparaisons et $N-1$ déplacements.
• Le nombre total d'opérations est $1 + 2 + \dots + (N-1) = \frac{N(N-1)}{2}$.
• La complexité est donc $O(N^2)$ (quadratique) dans le cas le pire (tableau trié en ordre inverse).
• Dans le cas le meilleur (tableau déjà trié), la complexité est $O(N)$ car chaque élément est comparé une seule fois.

Tri fusion ($O(n \log n)$)

Le tri fusion est un algorithme de type "diviser pour régner". Il divise le tableau en deux moitiés, trie récursivement chaque moitié, puis fusionne les deux moitiés triées.

• La division du tableau en moitiés prend $O(1)$ à chaque niveau de récursion.
• Il y a $\log n$ niveaux de récursion (car on divise par 2 à chaque fois).
• À chaque niveau, l'opération de fusion de deux sous-tableaux triés prend un temps linéaire par rapport au nombre total d'éléments à fusionner (soit $O(n)$).
• Donc, la complexité est $O(n \log n)$ (quasi-linéaire). C'est beaucoup plus efficace que $O(n^2)$ pour de grandes listes.

Recherche séquentielle ($O(n)$)

Comme vu précédemment, pour trouver un élément dans un tableau non trié, il faut potentiellement parcourir tout le tableau.

• Complexité : $O(n)$ dans le cas le pire.

Recherche dichotomique ($O(\log n)$)

La recherche dichotomique (ou binaire) est beaucoup plus rapide, mais elle a un prérequis : le tableau doit être trié.

L'algorithme fonctionne en comparant l'élément recherché avec l'élément du milieu du tableau.

• Si c'est l'élément recherché, on a trouvé.
• S'il est plus petit, on réduit la recherche à la moitié gauche du tableau.
• S'il est plus grand, on réduit la recherche à la moitié droite du tableau.
• À chaque étape, la taille de l'espace de recherche est divisée par deux.
• Le nombre d'étapes nécessaires pour réduire un tableau de taille $N$ à un seul élément est $\log_2 N$.
• Complexité : $O(\log n)$.

Exemple : Pour un tableau de 1 million d'éléments ($N = 10^6$), $\log_2(10^6) \approx 20$. Il ne faut que 20 comparaisons dans le pire des cas, contre 1 million pour la recherche séquentielle !

Le choix de l'algorithme a un impact majeur sur l'évolutivité des solutions. Un algorithme $O(N^2)$ sera parfaitement utilisable pour $N=100$, mais deviendra impraticable pour $N=100000$. Un algorithme $O(N \log N)$ ou $O(N)$ aura une performance bien meilleure sur de grands jeux de données.

Il est important de comprendre qu'il y a souvent un compromis temps/espace. Certains algorithmes plus rapides (meilleure complexité temporelle) peuvent nécessiter plus de mémoire (pire complexité spatiale), et vice-versa. Le choix dépendra des contraintes spécifiques du problème et des ressources disponibles. Par exemple, le tri fusion est $O(N \log N)$ en temps, mais nécessite $O(N)$ d'espace supplémentaire pour les fusions, alors que le tri par insertion est $O(N^2)$ en temps, mais $O(1)$ en espace (il trie "en place").

La complexité spatiale d'un algorithme mesure la quantité de mémoire utilisée par l'algorithme pour s'exécuter, en fonction de la taille de ses données d'entrée $N$. Cette mémoire est généralement mesurée en unités de stockage (octets) ou en nombre de variables/cellules mémoire.

Elle inclut :

• La mémoire pour stocker les variables d'entrée.
• La mémoire pour stocker les variables locales et temporaires de l'algorithme.
• La mémoire pour les structures de données auxiliaires créées par l'algorithme.
• La pile d'appels pour les fonctions récursives.

Comme pour la complexité temporelle, on s'intéresse à l'ordre de grandeur de cette consommation d'espace en fonction de $N$.

• Algorithmes in-place : Un algorithme est dit "in-place" s'il ne nécessite qu'une quantité de mémoire supplémentaire constante (ou très faible) par rapport à la taille de l'entrée. Sa complexité spatiale est $O(1)$.
  • Exemple : Le tri par insertion est un algorithme in-place. Il ne crée pas de nouveau tableau significatif.
• Utilisation de structures auxiliaires : Certains algorithmes créent de nouvelles structures de données dont la taille dépend de $N$.
  • Exemple : Le tri fusion nécessite un tableau temporaire de taille $N$ pour la phase de fusion. Sa complexité spatiale est $O(N)$.
  • Le stockage d'une copie du tableau d'entrée entraînera également une complexité spatiale de $O(N)$.
• Impact sur les ressources : Dans les environnements avec des ressources mémoire limitées (systèmes embarqués, serveurs avec de très grandes données), la complexité spatiale peut être un facteur limitant aussi important que la complexité temporelle. Un algorithme $O(N)$ en espace peut être acceptable, mais un $O(N^2)$ en espace pourrait rapidement saturer la mémoire pour des $N$ élevés.

Même avec les algorithmes les plus efficaces, il existe des limites fondamentales à ce que les ordinateurs peuvent résoudre :

• Problèmes indécidables : Ce sont des problèmes pour lesquels il a été prouvé qu'aucun algorithme ne peut exister pour les résoudre dans tous les cas. Le plus célèbre est le problème de l'arrêt (déterminer si un programme donné va s'arrêter ou boucler indéfiniment). Il n'y a pas d'algorithme universel pour ça.
• Problèmes NP-complets : Ce sont des problèmes pour lesquels aucun algorithme "efficace" (c'est-à-dire avec une complexité polynomiale comme $O(N)$, $O(N \log N)$, $O(N^2)$ etc.) n'a été trouvé à ce jour. Les meilleurs algorithmes connus ont une complexité exponentielle ($O(2^N)$ ou pire).
  • Exemples : Problème du voyageur de commerce, problème du sac à dos, problème de satisfiabilité booléenne.
  • L'implication pratique est que pour ces problèmes, si $N$ est grand, il est impossible de trouver la solution exacte dans un temps raisonnable. On doit souvent se contenter de solutions approchées ou d'heuristiques qui donnent de "bonnes" solutions, mais pas nécessairement la meilleure.

L'étude de la complexité nous aide donc à comprendre non seulement comment rendre nos programmes plus rapides, mais aussi ce qui est fondamentalement faisable ou infaisable en informatique.