Exercice 1 Questions de cours (8 points)
Complexité
1. Que veut dire f = O(g) ?
2. Expliquez la signification de la phrase « f est du même ordre asymptotique
que g ».
3. Dans le cadre de la complexité, qu’est-ce qu’un algorithme optimal ?
Tris et recherche
1. Donnez deux noms d’algorithmes de tris.
2. Expliquez en quelques lignes le fonctionnement de ceux-ci. Vous pouvez
vous aider d’un exemple.
3. La recherche d’un élément dans un tableau trié se fait au pire en n
comparaisons. Expliquez en quelques lignes un algorithme permettant
d’améliorer cette complexité au pire. Vous pouvez vous appuyer sur un
exemple.
Exercice 2 Complexité dans un tableau trié
Soit un tableau de N entiers.
1. Donner un algorithme ou un programme permettant de déterminer si
les éléments de ce tableau sont triés par Ordre croissant ou pas.
2. Déterminer la complexité de votre algorithme, fonction de N, en nombre
de comparaisons et en nombre d’affectation
– dans le pire des cas,
– dans le meilleur des cas.
Lun 7 Déc - 11:15
