T(n) et O() - Complexité NSI

← Retour au cours Complexité

Fonction de coût T(n)

définition

T(n) est le nombre d'opérations élémentaires (comparaisons, affectations…) en fonction de la taille n des données.

Taille de l'entrée : nombre d'éléments d'un tableau, de caractères d'une chaîne…

Pire cas

On s'intéresse souvent au pire cas : maximum d'opérations pour une entrée de taille n

Meilleur cas

Minimum possible (ex. trouvé dès le 1er test en recherche séquentielle)

Cas moyen

Moyenne sur toutes les entrées de taille n (plus rare en Première)

À retenir

Exemple : parcourir un tableau de n cases → au pire on fait n comparaisons → T(n) = n.

Notation O (grand O)

asymptotique

On garde seulement le terme dominant quand n tend vers l'infini ; on ignore les constantes multiplicatives.

Définition

f(n) = O(g(n)) si, au-delà d'un certain n, f(n) ≤ k × g(n) pour une constante k

Exemple

T(n) = 3n + 10 → on dit O(n) (pas O(3n))

Exemple

T(n) = n² + 5n → O(n²)

Intérêt

Comparer des algorithmes indépendamment de la machine ou du langage

Ordres de grandeur à connaître

croissance

Du plus rapide au plus lent quand n augmente (hors constantes).

O(1)

Constant : accès à un index de tableau

O(log n)

Logarithmique : dichotomie

O(n)

Linéaire : une boucle sur n éléments

O(n log n)

Tri efficace (fusion, rapide)

O(n²)

Quadratique : deux boucles imbriquées sur n

O(2ⁿ)

Exponentiel : exploration combinatoire naïve

À retenir

Pour n = 1 000 000 : O(log n) ≈ 20, O(n) = 1 000 000, O(n²) explose.

📋 Règles pratiques pour déduire O(...)

Boucle simple

Une boucle qui parcourt n éléments une fois → O(n).

Boucles imbriquées

Deux boucles chacune sur n → O(n²). Trois boucles → O(n³).

Diviser par 2 à chaque étape

Comme la dichotomie : on halve l'intervalle → O(log n).

T(n) vs O(n) en contrôle

T(n) peut être une expression précise (3n + 2). O(n) est la classe de croissance. On écrit : « la complexité est O(n) » ou « T(n) = O(n) ».

Expression T(n)	Notation O
5	O(1)
2 log₂ n + 3	O(log n)
n + 100	O(n)
4n² + n	O(n²)

Notations T(n) et O()