Available inFrenchEnglishGermanHindiPortugueseRussianSpanish
Complexité algorithmique (Big O) et structures de données
Apprenez la notation Big O depuis zéro et le coût en temps et en mémoire des structures de données, recherches et tris essentiels. Pour les entretiens techniques et les cours d’informatique, des boucles aux graphes.
Qu’exprime la notation Big O ?
La croissance du coût avec la taille de l’entrée
Source
Big O désigne la forme de la croissance, et non une durée : O(n) signifie que le travail augmente au même rythme que l’entrée, O(n²) comme son carré. Les courbes montrent à quel point ces formes s’écartent dès que l’entrée devient grande. Au sens strict, Big O énonce une borne supérieure de cette croissance. Le O vient de l’allemand Ordnung, « ordre » : la notation est due à Paul Bachmann (1894) et a été popularisée par Edmund Landau.