Meilleur, pire et moyen cas
Le coût d'un algorithme dépend de l'entrée, pas seulement de sa taille : meilleur cas, pire cas et cas moyen, pour les recherches et les tris du parcours.
- 26 cartes
- 6 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
- Mises en situation
- Comprendre
Quelques cartes du deck
Meilleur cas : de quoi s'agit-il ?
Voir la réponse
Entrée de taille n pour laquelle l'algorithme exécute le moins d'opérations.
Pour la recherche séquentielle, c'est la valeur située dans la première case : 1 comparaison, quel que soit n.
Combien de décalages le tri par insertion fait-il sur le tableau
[6, 5, 4, 3, 2, 1]?155621
Voir la réponse
15Chaque élément doit passer devant tous ceux qui le précèdent : 1 + 2 + 3 + 4 + 5 = 15 décalages. C'est le pire cas pour 6 valeurs. 5 serait le nombre de comparaisons sur un tableau déjà trié.
Pour la recherche séquentielle, le meilleur cas coûte … comparaison (valeur en première case) et le pire cas coûte … comparaisons (valeur absente ou en dernière case).
Voir la réponse
Pour la recherche séquentielle, le meilleur cas coûte 1 comparaison (valeur en première case) et le pire cas coûte n comparaisons (valeur absente ou en dernière case).
Les deux dépendent de l'entrée, pas seulement de n. La taille du tableau est la même, 100 par exemple, dans les deux cas.
Pire cas : de quoi s'agit-il ?
Voir la réponse
Entrée de taille n pour laquelle l'algorithme exécute le plus d'opérations ; son coût borne celui de toutes les autres entrées de même taille.
Pour la recherche séquentielle, c'est une valeur absente ou placée en dernière case : n comparaisons. On peut garantir « jamais plus que cela ».