Quelle est la différence entre un algorithme linéaire et un algorithme quadratique ?

Réponse courte

Un algorithme linéaire demande un nombre d’opérations proportionnel à la taille n des données ; un algorithme quadratique en demande un proportionnel à n². Quand n double, le second croît donc beaucoup plus vite à grande échelle.

Comprendre

Compter selon la taille

Le coût décrit l’évolution du nombre d’opérations quand la taille n augmente. Un parcours qui examine chaque case une fois a un coût linéaire : pour 100 valeurs, il réalise au plus environ 100 examens ; pour 200, environ 200. On note souvent cet ordre de grandeur O(n).

Reconnaître le coût quadratique

Un algorithme qui compare chaque paire de valeurs peut effectuer environ n² comparaisons. Le tri par sélection examine successivement des parties de tailles n − 1, n − 2, jusqu’à 1 ; son total est n(n − 1)/2. Avec 5 valeurs, cela représente 10 comparaisons ; avec 10, 45. Lorsque n devient grand, doubler la taille multiplie approximativement par quatre le coût quadratique, alors que le coût linéaire est approximativement multiplié par deux.

Comparer correctement

Ces mots décrivent un ordre de croissance, pas une durée exacte en secondes. Le temps mesuré dépend aussi de l’ordinateur et de l’implémentation. Pour le tri par insertion, il faut préciser le cas : un tableau déjà trié ne demande qu’une comparaison de valeurs par étape, tandis que le pire cas a un coût quadratique.

Deux pièges de comparaison

Ne conclus pas qu’un algorithme quadratique est toujours plus lent sur de toutes petites entrées : les constantes et l’implémentation comptent. Ne donne pas non plus un coût sans indiquer l’opération comptée et le cas étudié ; comparer le temps réel d’un seul essai ne suffit pas à établir l’ordre de croissance.

Exemples

  • Un parcours de 200 cases examine au plus 200 éléments : le nombre d’examens est proportionnel à n.
  • Le tri par sélection de 5 valeurs effectue 4 + 3 + 2 + 1 = 10 comparaisons ; pour 10 valeurs, il en effectue 9 + 8 + … + 1 = 45.
  • Pour une entrée deux fois plus grande, un coût linéaire est environ doublé et un coût quadratique environ quadruplé lorsque n est grand.

Pièges fréquents

  • Dire qu’un algorithme quadratique prend toujours quatre fois plus de secondes quand l’entrée double confond l’ordre de croissance et un temps d’exécution mesuré.
  • Qualifier un algorithme sans préciser le cas peut masquer qu’un tri par insertion est rapide sur un tableau déjà rangé mais quadratique dans son pire cas.

Pourquoi ça marche

Un examen par élément s’additionne n fois, tandis qu’un examen de toutes les paires met en jeu un nombre de couples qui croît comme le carré de n.

Et maintenant ?

Questions proches

← Toutes les questions-réponses