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

Quelle est la complexité temporelle du tri fusion dans le pire cas ?

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

Qu'est-ce qu'un algorithme de force brute ?

1. AUn algorithme qui essaie toutes les solutions candidates possibles
2. BUn algorithme qui s'exécute sur de nombreux processeurs
3. CUn algorithme qui devine une réponse au hasard
4. DUn algorithme qui utilise toujours la récursion

Que décrit le temps d'exécution dans le pire cas d'un algorithme ?

1. ALe temps sur un ordinateur lent
2. BLe temps maximal sur toutes les entrées de taille n
3. CLe temps espéré sur une entrée aléatoire de taille n
4. DLe temps sur la plus petite entrée

Un algorithme glouton :

1. AFait le meilleur choix local à chaque étape
2. BN'utilise que la récursivité
3. CDonne toujours la solution optimale
4. DEssaie toutes les solutions possibles

Quelle est la complexité temporelle du calcul du n-ième nombre de Fibonacci avec une table remplie de bas en haut ?

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

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

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

Quelle borne est correcte pour log(n!) ?

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

L'algorithme de programmation dynamique de Held-Karp résout exactement le problème du voyageur de commerce. Quel est son temps d'exécution pour n villes ?

1. AO(2^n²)
2. BO(n!)
3. CO(n² 2ⁿ)
4. DO(n³)