Boucles imbriquées et complexité quadratique
Cours · informatique (tronc commun des prépas scientifiques), chapitre 3 · prépas scientifiques, tronc commun · le début du chapitre, la suite sur Adloun
3.1 Introduction et motivation
Quand une question porte non plus sur les éléments d'un tableau mais sur ses couples — quelles sont les deux mesures les plus proches ? ce motif apparaît-il dans ce texte ? ces éléments sont-ils dans le bon ordre ? — un seul parcours ne suffit plus : il faut une boucle dans la boucle. Cette structure, la plus naturelle qui soit, a un prix : le nombre d'opérations ne croît plus comme mais comme . Doubler l'entrée quadruple le temps ; la multiplier par mille le multiplie par un million.
Ce chapitre apprend à manier les boucles imbriquées sur trois problèmes classiques — la paire la plus proche, la recherche d'un facteur dans un texte, le tri à bulles — et, à chaque fois, à faire les deux gestes du métier : estimer le coût (en comptant ce que l'on exécute vraiment) et valider la correction (par les invariants du chapitre 1, qui deviennent ici indispensables : avec deux indices qui bougent, l'intuition seule ne suffit plus).
3.2 La complexité quadratique
3.2.1 Compter les tours d'une double boucle
for i in range(n):
for j in range(n):
... # corps en O(1)Le corps s'exécute fois : coût . Variante essentielle, le triangle — quand ne parcourt que les indices après :
for i in range(n):
for j in range(i + 1, n):
... # corps en O(1)Le nombre de tours est : la somme des premiers entiers, vue en cours de mathématiques. C'est moitié moins que , mais c'est toujours — la constante disparaît dans le .
Un algorithme est de complexité quadratique si son coût dans le cas le pire est — typiquement, un travail à coût constant effectué pour chaque couple d'indices. Ordres de grandeur, à opérations par seconde :
| ms | ms | ||
| ms | s | heures |
Un algorithme quadratique est parfaitement honorable jusqu'à , pénible vers , et inutilisable au-delà : savoir situer son entrée sur cette échelle est le premier réflexe de l'analyse.
