Fiche d’exercices de Algorithmes et complexité avec corrigé

Quel algorithme de tri échange de façon répétée les éléments adjacents qui sont dans le mauvais ordre ?

1. ATri rapide (quicksort)
2. BTri par tas
3. CTri fusion
4. DTri à bulles

Combien de mémoire supplémentaire utilise un tri fusion standard sur tableau ?

1. AO(1)
2. BO(log n)
3. CO(n²)
4. DO(n)

Quel algorithme de tri choisit un pivot et partitionne le tableau en éléments plus petits et plus grands ?

1. ALe tri rapide (quicksort)
2. BLe tri par insertion
3. CLe tri à bulles
4. DLe tri fusion

Que mesure l'analyse amortie ?

1. ALe coût espéré sur des entrées aléatoires
2. BLe coût de l'unique opération la plus chère, où qu'elle se trouve dans la suite
3. CLe coût moyen par opération sur une suite d'opérations de pire cas
4. DLe coût d'un algorithme sur la meilleure entrée

Dans un tableau trié, vous cherchez deux éléments dont la somme vaut une cible en déplaçant un pointeur depuis chaque extrémité vers l'intérieur. Quelle est la complexité temporelle ?

1. AO(n²)
2. BO(n log n)
3. CO(log n)
4. DO(n)

Quelle est la solution de la récurrence T(n) = 2T(n − 1) + O(1) ?

1. AO(n)
2. BO(n log n)
3. CO(n²)
4. DO(2ⁿ)

D'après le théorème maître, T(n) = 8T(n/2) + O(n²) a pour solution :

1. AΘ(n³)
2. BΘ(n log n)
3. CΘ(n²)
4. DΘ(n² log n)

Comment le problème du voyageur de commerce est-il classé ?

1. AIl est indécidable
2. BLa version décisionnelle est dans P mais la version d'optimisation est NP-complète
3. CIl est dans P car l'algorithme de Dijkstra le résout en visitant chaque ville une seule fois
4. DLa version décisionnelle est NP-complète et la version d'optimisation est NP-difficile