La notation O
Les notations O, Ω et Θ, leur définition par une constante et un rang, les règles de simplification d'un coût et l'échelle des classes de croissance, de 1 à n!.
- 26 cartes
- 5 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Les courbes
Quelques cartes du deck
Borne supérieure asymptotique : de quoi s'agit-il ?
Voir la réponse
Dire que f est dans O(g), c'est dire qu'il existe une constante c > 0 et un rang n₀ tels que f(n) ≤ c × g(n) pour tout n ≥ n₀.
La constante absorbe les détails de la machine et le rang écarte les petites tailles : seule compte la croissance. 3n + 10 est dans O(n) avec c = 4 et n₀ = 10.
Un algorithme coûte T(n) = 3n² + 40 n log n opérations. Dans quelle classe Θ se trouve-t-il ?
- Θ(n²)
- Θ(n log n)
- Θ(n² log n)
- Θ(n³)
Voir la réponse
Θ(n²)
n² grandit plus vite que n log n : le terme en n² domine et le coefficient 3 disparaît. Les deux termes s'additionnent : on ne les multiplie pas pour obtenir n² log n.
Si f est à la fois dans O(g) et dans Ω(g), alors f est dans …(g).
Voir la réponse
Si f est à la fois dans O(g) et dans Ω(g), alors f est dans Θ(g).
Θ encadre le coût des deux côtés : c'est la seule notation qui dit « exactement cette croissance ».