Le développement d’algorithmes induit l’optimisation de leur efficacité. Cela consiste à leur permettre de réaliser la tâche pour laquelle ils ont été conçus (le fait que les valeurs d’entrée respectent les spécifications implique que les valeurs de sorties respecteront à leur tour les spécifications) le plus rapidement et en mobilisant le moins de mémoire possible. Le temps d’exécution et la quantité de mémoire (vive) utilisée sont ainsi les deux ressources caractérisant l’efficacité d’un algorithme. La comparaison de l’efficacité de deux algorithmes nécessite donc leur implémentation dans un même langage de programmation et sur deux machines identiques (autant que possible).

La complexité algorithmique constitue, en quelque sorte, l’inverse de l’efficacité : les algorithmes de faible complexité seront ainsi favorisés pour leur rapidité de mise en œuvre et l’économie de mémoire qu’ils procurent. La complexité est matérialisée par une fonction, généralement notée $\bf C(n)$, de la taille de la donnée d’entrée, généralement notée $\bf n$. La complexité dépendant du nombre d’opérations élémentaires effectuées par l’algorithme (opérations arithmétiques et logiques, affectation, modification d’un élément de liste), si celui-ci possède plusieurs données à son entrée, celle représentant la taille sera celle dont la valeur influera sur le nombre d’opérations élémentaires, par exemple intervenant dans la condition d’une boucle « tant que » (« while ») :

Dans le cas présenté ci-dessus, l’ordre de grandeur du nombre d’opérations élémentaires sera celui du nombre de tours de boucle effectués. En effet, la complexité est généralement évaluée dans le pire des cas, en l’occurrence en l’absence de l’élément $\rm x$ dans la liste $\rm L$ : en notant $\rm n = len(L)$, le test sera réalisé $\rm n$ fois, aboutissant à une complexité de la forme $\rm C(n) = \alpha • n + \beta$, soit $\rm O(n)$, qualifiée de linéaire.

L’enjeu étant d’optimiser les algorithmes, ceux dont la complexité excède $\rm O(n^3))$ seront considérés comme trop complexes, dont trop peu efficaces. Le tableau ci-dessous recense les principales complexités « favorables » rencontrées.

$\underset{\longleftarrow}{\scriptstyle \rm Efficacité}$

$\rm O(1)$ $\rm O(\log_{2}(n))$ $\rm O(n))$ $\rm O(n.\log_{2}(n))$ $\rm O(n^2)$
Temps constant Logarithmique Linéaire Quasi-linéaire Quadratique
1 à 10 ns * 10 à 100 ns * 1 à 10 ms * 10 à 100 ns * 10 min à 5 h *
Accès à un élément de liste Recherche par dichotomie Parcours d’une liste Tri de type « fusion » Tri par insertion ou par sélection

* ordre de grandeur de la durée d’exécution pour une donnée d’entrée de taille $\rm n = 10^6)$.