Non pas exactement :
- O(n*n) est un "temps quadratique" (abus de langage, il s'agit de complexité, voir d'autres posts)
- O(n) est un "temps linéaire"
- O(1) est un "temps constant" (pas du tout la même chose que O(n) !)
- O(2) est équivalent à O(1) (les constantes multiplicatives sont ignorées, grâce à la "constante K" dans la définition que j'ai donnée) qui est la notation conventionnellement utilisée
O(1) peut paraître bizarre, mais c'est en fait relativement courant. On peut le retrouver par exemple dans les structures à bases de tables hash (à la condition que la répartition soit parfaite ;-)), ou d'autres cas (par exemple récupérer le plus petit élément d'un ensemble déjà trié, comme un std::set en C++...).
[^] # Re: Avancées technologiques du prochain Kernel
Posté par Moby-Dik . En réponse à la dépêche Avancées technologiques du prochain noyau Linux. Évalué à 2.
- O(n*n) est un "temps quadratique" (abus de langage, il s'agit de complexité, voir d'autres posts)
- O(n) est un "temps linéaire"
- O(1) est un "temps constant" (pas du tout la même chose que O(n) !)
- O(2) est équivalent à O(1) (les constantes multiplicatives sont ignorées, grâce à la "constante K" dans la définition que j'ai donnée) qui est la notation conventionnellement utilisée
O(1) peut paraître bizarre, mais c'est en fait relativement courant. On peut le retrouver par exemple dans les structures à bases de tables hash (à la condition que la répartition soit parfaite ;-)), ou d'autres cas (par exemple récupérer le plus petit élément d'un ensemble déjà trié, comme un std::set en C++...).