Big O

Une définition du Jargon Français.
Aller à : Navigation, rechercher

Dr enus.png locution nominale, féminin.  [algorithmie]. Convention de notation résumant le rendement (efficacité) d'un algorithme.

Pour un type de méthode de résolution (l'algorithme) défini cela révèle la durée du traitement en fonction du nombre de données fournies (entrées, en résumé la « taille » du problème posé). C'est donc de l'ordre de grandeur du temps nécessaire à la résolution dans un cas (correspondant à un certain nombre de données) lorsque l'on connaît le temps nécessaire à un autre (toutes choses égales par ailleurs, donc avec la même implémentation de l'algorithme animée par la même machine...).

Par exemple dans le tableau suivant avec un algorithme en O(n2) le traitement de 3 données dure 9 unités de temps, et celui de 7 données exigera 49 unités de temps. Utiliser un algorithme en O(log(n)) en lieu et place permettra de traiter 3 données en 1,1 unité de temps, et 7 données en 1,94 unités de temps.

En résumé cela révèle l'intérêt, lorsqu'on dispose déjà d'un algorithme approprié, de se creuser la tête pour en trouver et implanter un autre plus efficace, en fonction de la taille des problèmes que l'on souhaite traiter.

En pratique il faut aussi tenir compte de nombreux autres paramètres physiques. La taille d'un éventuel cache, par exemple, est déterminante car lorsque toutes les données à traiter y tiennent les performances sont considérablement meilleures (au point qu'un algorithme peu efficace mais traitant les données par sous-ensembles tenant chacun en cache sera parfois le plus performant).

Big O Durée Durée (3 données) Durée (7 données) Durée (100 données)
O(1) constante 1 1 1
O(log(n)) logarithmique 1,1 1,94 4,6
O(n) linéaire 3 7 100
O(n * log(n)) log linéaire 3,3 13,6 460,5
O(n2) quadratique 9 49 10000
O(n3) cubique 27 343 1000000
O(2n) exponentielle 8 128 1267650600228229401496703205376
O(2!) factorielle 6 5040 9.3E157

Voir aussi complexité de Kolmogorov