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 à bulles
3. CTri fusion
4. DTri par tas

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

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

Quelle est la complexité temporelle de la recherche de la plus grande valeur dans un tableau non trié de n nombres ?

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

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

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

Comment l'algorithme de Prim construit-il un arbre couvrant de poids minimal ?

1. AIl trie toutes les arêtes par poids et ajoute chacune d'elles sauf si elle formait un cycle dans la forêt
2. BIl fait croître un seul arbre à partir d'un sommet de départ, en ajoutant l'arête la moins chère qui sort de l'arbre
3. CIl supprime l'arête la plus chère jusqu'à ce qu'il ne reste plus de cycle
4. DIl exécute un parcours en largeur et conserve l'arbre du BFS

Environ combien de comparaisons la recherche dichotomique nécessite-t-elle dans le pire cas sur un tableau trié de 1,000,000 d'éléments ?

1. AEnviron 100
2. BEnviron 20
3. CEnviron 500,000
4. DEnviron 1,000

Quels sont les coûts en temps et en espace du calcul du n-ième nombre de Fibonacci avec une boucle qui ne conserve que les deux dernières valeurs ?

1. AO(n) en temps et O(n) en espace
2. BO(2ⁿ) en temps et O(1) en espace
3. CO(log n) en temps et O(n) en espace
4. DO(n) en temps et O(1) en espace

Les plus courts chemins simples peuvent être trouvés en temps polynomial. Que sait-on de la recherche du plus long chemin simple entre deux sommets dans un graphe quelconque ?

1. AC'est toujours résoluble en O(V + E)
2. BC'est NP-difficile
3. CC'est indécidable
4. DOn peut le résoudre avec l'algorithme de Dijkstra en prenant l'opposé des poids