Introduction

Soit deux algorithmes A et B résolvant le même problème de complexité respectives $100n$ et $n^2$. Quel est le plus efficace ?

La réponse courte : L'algorithme A ($100n$) est le plus efficace.

L'explication détaillée : Tout dépend de la taille $n$.

• Pour une petite taille (ex: $n=10$) :
  • A : $100×10=1000$ opérations.
  • B : $10^2=100$ opérations. → B est plus rapide.
• Pour une grande taille (ex: n=200) :
  • A : $100×200=20000$ opérations.
  • B : $200^2=40000$ opérations. → A devient plus rapide.

Il y a un point de bascule à $n=100$ ($100×100=100^2$). Dès que l'on dépasse cette taille, l'algorithme quadratique ($n^2$) explose, tandis que le linéaire ($100n$) reste stable.

<aside> 💡

En informatique, on privilégie le comportement sur les grandes données. C'est le cœur de la complexité asymptotique.

</aside>

Définitions

La complexité asymptotique est l'étude du comportement de l'algorithme lorsque $n$ tend vers l'infini ($n→∞$). On cherche à définir l'ordre de grandeur de la croissance, en négligeant les constantes et les termes de bas degré.

1. Les Notations de Landau

Pour classer les algorithmes, on utilise trois notations grecques principales qui décrivent les "bornes" de la fonction de coût.

A. Le Grand O ($O$) : La Borne Supérieure (Pire des cas)

C'est la notation la plus utilisée. Elle garantit que l'algorithme ne sera jamais plus lent que cette limite.

• Définition : $f(n)=O(g(n))$ signifie qu'à partir d'un certain rang, $f(n)≤c⋅g(n)$.
• Signification : "Au pire, ça coûte ça."
• Usage : Sert à garantir la performance limite d'un programme (SLA, temps réel).

B. Le Grand Omega ($Ω$) : La Borne Inférieure (Meilleur des cas)

C'est l'inverse du Grand O. Elle indique que l'algorithme prendra au moins ce temps-là.

• Définition : $f(n)=Ω(g(n))$ signifie qu'à partir d'un certain rang, $f(n)≥c⋅g(n)$.