T(n) et O()
notationsT(n) compte le travail réel ; O(g(n)) décrit la croissance dominante (on néglige les constantes).
O(1)
Temps constant
O(log n)
Logarithmique
O(n)
Linéaire
O(n2)
Quadratique
Complexité algorithmique
Notations T(n) et O()
Analyser la performance d'un algorithme
En Première NSI, on mesure le coût d'un algorithme avec T(n) et la notation asymptotique O(...).
Ce cours : uniquement les notations et ordres de grandeur. Pour la recherche séquentielle et dichotomique, voir le cours Recherche.