Ordres de grandeur des algorithmes
Les croissances constante, logarithmique, linéaire, quasi linéaire, quadratique et exponentielle : les classer, prévoir l'effet d'un doublement de n et estimer un temps d'exécution.
- 32 cartes
- 8 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
- Sur la frise
- Les chiffres
- Les courbes
- Mises en situation
- Comprendre
Quelques cartes du deck
Ordre de grandeur d'un coût : de quoi s'agit-il ?
Voir la réponse
Allure de la croissance du coût quand n devient grand, où l'on ne garde que le terme dominant et où l'on ignore les constantes multiplicatives.
3n² + 5n + 2 est de l'ordre de n². Pour n = 1000, le terme 3n² vaut 3 000 000 et les autres 5002 : ils ne comptent presque plus.
Le tri par sélection met 1 s pour 10 000 valeurs. Combien de temps pour 20 000 valeurs ?
4 s2 s2,2 s8 s
Voir la réponse
4 sLe coût est quadratique : doubler n multiplie les opérations par 4. 2 s serait la réponse d'un coût linéaire, 2,2 s celle d'un coût en n log n, et 8 s celle d'un coût en n³.
Quand n double, un coût linéaire est multiplié par … et un coût quadratique par ….
Voir la réponse
Quand n double, un coût linéaire est multiplié par 2 et un coût quadratique par 4.
Pour la croissance en n : 2n / n = 2. Pour n² : (2n)² / n² = 4. Un coût logarithmique, lui, n'augmente que d'une unité.