Complexité algorithmique¶

Avant de choisir un algorithme ou une structure, il faut savoir mesurer le coût — en temps et en mémoire — independamment de la machine.

Pourquoi la complexité plutôt que le benchmarking¶

Un benchmark mesure les performances sur une machine spécifique, avec un compilateur spécifique, un cache a un état particulier, sous une charge donnée. La complexité algorithmique mesure comment le coût croît en fonction de la taille de l'entree — independamment du matériel. C'est ce qui permet de prédire si un algorithme tient encore la route a un million d'éléments quand il etait correct a mille.

La notation asymptotique compare les algorithmes dans leur comportement limite, au dela du bruit des constantes multiplicatives. Elle répond a : "Quand \(n\) grandit, qui grandit le plus vite — le numerateur ou le denominateur ?"

Notation O : définition formelle et interpretation¶

La notation de Landau, introduite par Edmund Landau au début du XXe siecle et popularisee en informatique par Donald Knuth dans "The Art of Computer Programming", formalise la relation entre la taille d'une entree et le coût d'un algorithme.

Définition formelle : \(f(n) = O(g(n))\) si et seulement si il existe deux constantes \(c > 0\) et \(n_0\) telles que pour tout \(n \geq n_0\), \(|f(n)| \leq c \cdot |g(n)|\).

En pratique : \(O\) capture le comportement dominant quand \(n\) devient grand. On élimine les constantes multiplicatives et les termes sous-dominants. \(3n^2 + 7n + 12 = O(n^2)\), car au dela d'un certain \(n\), \(n^2\) domine tout.

Complexites courantes¶

L'ecart entre \(O(n \log n)\) et \(O(n^2)\) semble modeste pour \(n = 100\). A \(n = 10^6\), c'est la différence entre un algorithme qui répond en une seconde et un qui prendrait des années.

Comment calculer la complexité d'un code¶

Avant de se perdre dans les tables de complexites, il faut savoir lire un algorithme et en deduire la complexité. Quelques règles de base.

Boucles : une boucle de \(n\) iterations autour d'un corps \(O(1)\) donne \(O(n)\). Deux boucles imbriquees de \(n\) iterations chacune donnent \(O(n^2)\). Attention aux boucles dont le pas n'est pas 1 : une boucle i = 1; i *= 2 jusqu'à \(n\) réalisé \(\log_2(n)\) iterations — \(O(\log n)\).

Recursion : analyser via le théorème maître ou en deroulant l'arbre de recursion.

Théorème maître : pour une récurrence \(T(n) = a \cdot T(n/b) + f(n)\) ou \(a \geq 1\), \(b > 1\), \(f(n)\) asymptotiquement positive :

Application aux algorithmes classiques :

# Exemple : analyser la complexite de cette fonction
def f(n):
    if n <= 1:          # O(1)
        return 1
    total = 0
    for i in range(n):  # O(n) iterations
        total += i      # O(1)
    return total + f(n // 2) + f(n // 2)  # 2 appels recursifs sur n/2

# Recurrence : T(n) = 2T(n/2) + O(n) -> O(n log n) par theoreme maitre cas 2

Sequences d'opérations : ajouter les complexites (la dominante l'emporte). \(O(n \log n) + O(n^2) = O(n^2)\). \(O(n) + O(n) = O(n)\), pas \(O(2n)\).

Opérations sur des structures : lire la complexité de chaque opération dans la table de la structure, puis multiplier par le nombre d'appels.

Omega et Theta : bornes inférieure et exacte¶

\(O\) est une borne supérieure — elle dit "pas pire que". Deux autres notations completent le tableau.

\(\Omega\) (Omega) — borne inférieure. \(f(n) = \Omega(g(n))\) signifie que l'algorithme prend au minimum un temps proportionnel a \(g(n)\). La recherche dans une liste non triee est \(\Omega(n)\) : dans le pire cas on doit tout parcourir, aucun algorithme de comparaison ne peut faire mieux.

\(\Theta\) (Theta) — borne exacte (encadrement). \(f(n) = \Theta(g(n))\) signifie que \(f\) est à la fois \(O(g(n))\) et \(\Omega(g(n))\). Le tri par comparaison est \(\Theta(n \log n)\) dans le cas général : c'est la borne supérieure des meilleurs algorithmes ET la borne inférieure théorique prouvee par la théorie de l'information (un arbre de décision sur \(n\) éléments a au moins \(n!\) feuilles, donc une hauteur minimale de \(\log_2(n!) \approx n \log n\)).

En pratique, \(\Theta\) est la notation la plus utile quand on connait le comportement exact, et \(O\) suffit pour les estimations courantes.

Analyse : pire cas, cas moyen, cas amorti¶

La complexité d'un algorithme peut varier selon les entrees. Il faut distinguer trois angles d'analyse.

Pire cas¶

Le pire cas borne le coût maximal pour toute entree de taille \(n\). C'est la garantie la plus forte et la plus utilisée en pratique. Quicksort naif (pivot = premier élément) sur un tableau déjà trie est \(O(n^2)\) dans le pire cas : chaque partition ne retire qu'un élément.

Cas moyen¶

Le cas moyen calcule le coût attend pour une entree aléatoire, selon une distribution supposee. Quicksort avec un pivot aléatoire est \(O(n \log n)\) en cas moyen — la partition est en moyenne equilibree. L'analyse de cas moyen nécessité de supposer une distribution de l'entree, ce qui la rend moins généralement applicable que le pire cas.

Cas amorti : l'exemple du tableau dynamique¶

L'analyse amortie s'applique quand une sequence d'opérations a un coût total borne, même si certaines opérations individuelles sont coûteuses.

Le tableau dynamique (Python list, Java ArrayList) double sa capacité quand il est plein. Une insertion peut déclencher une recopie de tous les éléments — coût \(O(n)\) pour cette seule opération. Pourtant, le coût amorti par insertion reste \(O(1)\).

Preuve par potentiel : après une recopie sur un tableau de taille \(n\), le tableau a \(n/2\) éléments et une capacité de \(n\). Les \(n/2\) insertions suivantes avant la prochaine recopie "remboursent" chacune deux unites : une pour leur propre insertion, une pour leur future recopie. Le coût total de \(n\) insertions est \(O(n)\), soit \(O(1)\) amorti par opération.

Complexité spatiale : mémoire auxiliaire et compromis temps/espace¶

La complexité temporelle est souvent le premier critère, mais la mémoire est tout aussi critique en production. La complexité spatiale mesure la mémoire supplémentaire (auxiliaire) utilisée par l'algorithme, séparément de la mémoire occupee par l'entree elle-même.

Compromis temps/espace¶

Deux stratégies classiques illustrent le compromis fondamental :

Memoisation — on stocke les résultats de sous-problèmes déjà calcules pour éviter de les recalculer. On échange de l'espace contre du temps. Fibonacci naif est \(O(2^n)\) en temps. Avec memoisation : \(O(n)\) en temps et \(O(n)\) en espace.

Double hachage vs chaining — dans une table de hachage, l'open addressing (double hachage) est plus compact (pas de pointeurs), meilleur pour le cache, mais se dégradé rapidement au-delà de 70% de charge. Le chaining utilisé plus de mémoire (pointeurs par entree) mais supporte des facteurs de charge élevés sans dégradation catastrophique.

Classes de complexité : P, NP, NP-complet¶

La théorie de la complexité classifie les problèmes selon les ressources nécessaires pour les résoudre ou vérifier leurs solutions. Ces classes s'appliquent aux problèmes de décision (réponse oui/non).

Classe P¶

P est la classe des problèmes resolubles en temps polynomial par une machine de Turing deterministe. En pratique : les problèmes pour lesquels il existe un algorithme "efficace". Tri, recherche, plus court chemin, flot maximum sont dans P.

Classe NP¶

NP (Non-deterministic Polynomial) est la classe des problèmes dont une solution peut être vérifiée en temps polynomial. Attention : NP ne signifie pas "non-polynomial". Si on vous donne une solution candidate, vous pouvez vérifier en temps polynomial qu'elle est correcte.

Le problème ouvert central de l'informatique théorique est \(P = NP\) ? Si \(P = NP\), alors tout problème dont la solution est verifiable rapidement peut aussi être résolu rapidement. L'immense majorité des specialistes pense que \(P \neq NP\), mais personne n'a encore prouve ni refute cette conjecture — posee formellement par Stephen Cook en 1971.

NP-complet et NP-difficile¶

NP-complet — sous-classe de NP contenant les problèmes les plus difficiles de NP : tout problème NP peut être réduit en temps polynomial a un problème NP-complet. Si un problème NP-complet etait résolu en temps polynomial, tous les problèmes NP le seraient aussi (\(P = NP\)).

NP-difficile — problèmes au moins aussi durs que les problèmes NP-complets, mais pas necessairement dans NP (leur solution n'est pas necessairement verifiable en temps polynomial).

Exemples classiques¶

Recurrences et analyse des algorithmes diviser-pour-regner¶

Beaucoup d'algorithmes efficaces s'ecrivent recursivement : diviser le problème en sous-problèmes plus petits, les résoudre, combiner les résultats. L'analyse de leur complexité passe par la résolution de recurrences.

Dérouler l'arbre de recursion¶

Une méthode universelle : dessiner l'arbre de recursion, calculer le coût par niveau, sommer sur tous les niveaux.

Pour Mergesort avec \(T(n) = 2T(n/2) + O(n)\) : au niveau 0, un problème de coût \(n\). Au niveau 1, deux sous-problèmes de coût \(n/2\) chacun — total \(n\). Au niveau 2, quatre sous-problèmes de coût \(n/4\) — total \(n\). Chaque niveau a un coût \(O(n)\). Il y a \(\log_2 n\) niveaux. Total : \(O(n \log n)\).

Pour quicksort en cas moyen : la partition esperee est equilibree, soit \(T(n) = 2T(n/2) + O(n)\) — même récurrence, même résultat \(O(n \log n)\).

Algorithmes sous-quadratiques importants¶

Karatsuba (1960) : multiplication de deux entiers de \(n\) chiffres. La méthode naive est \(O(n^2)\). Karatsuba observe qu'on peut calculer le produit avec seulement 3 multiplications de sous-entiers au lieu de 4, ce qui donne \(T(n) = 3T(n/2) + O(n) \rightarrow O(n^{1.585})\) par le théorème maître (cas 1, \(\log_2 3 \approx 1.585\)). Utilisé dans les bibliotheques de grands entiers (Python int, OpenSSL, GMP).

Strassen (1969) : multiplication de matrices \(n \times n\). La méthode naive est \(O(n^3)\). Strassen réduit a 7 multiplications recursives de matrices \(n/2 \times n/2\) : \(T(n) = 7T(n/2) + O(n^2) \rightarrow O(n^{2.807})\). Utilisé dans les bibliotheques d'algebre lineaire pour les grandes matrices.

FFT (Cooley-Tukey, 1965) : transformee de Fourier discrète de \(n\) points. L'algorithme naif est \(O(n^2)\). La FFT est \(O(n \log n)\) en exploitant la symétrie de la transformation. Fondamentale en traitement du signal, compression audio (MP3), multiplication de polynomes, convolution d'images.

Impact des constantes cachees¶

La notation \(O\) masque les constantes multiplicatives. Pour de petits \(n\), un algorithme \(O(n^2)\) avec une petite constante peut battre un \(O(n \log n)\) avec une grande constante.

C'est pourquoi Timsort utilise le tri par insertion (\(O(n^2)\)) pour les sous-tableaux de moins de 64 éléments : les constantes sont plus favorables que mergesort a cette taille, et le cache est chaud. Les implémentations de quicksort modernes font de même — passage à l'insertion sort sous un seuil (typiquement 8 a 16 éléments).

Table de complexites : algorithmes et structures courants¶

Application : cet algorithme tiendra-t-il sur N éléments ?¶

Estimation des temps de calcul en supposant \(10^9\) opérations elementaires par seconde (machine moderne, sans parallélisme).

Les seuils pratiques pour des algorithmes interactifs (réponse < 100 ms) :

• \(O(n^2)\) : viable jusqu'à \(n \approx 10\,000\)
• \(O(n \log n)\) : viable jusqu'à \(n \approx 10^7\)
• \(O(n)\) : viable jusqu'à \(n \approx 10^8\)

Au-delà, il faut paralleliser, precalculer ou changer de stratégie algorithmique.