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

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 log n)
3. CO(n)
4. DO(log n)

Un algorithme en O(n) prend 3 secondes pour n = 1 million. Combien de temps prend-il environ pour n = 2 millions ?

1. A12 secondes
2. B6 secondes
3. C3 secondes
4. D9 secondes

Qu'exige la recherche dichotomique de son entrée ?

1. ALe tableau ne doit contenir que des nombres positifs
2. BLe tableau doit être trié
3. CLe tableau ne doit pas avoir plus de 1000 éléments
4. DLa longueur du tableau doit être une puissance de deux

Un tri rapide utilise toujours le premier élément comme pivot. Sur quelle entrée présente-t-il son comportement de pire cas ?

1. AUn tableau dont tous les éléments sont distincts
2. BUn tableau de longueur 2
3. CUn tableau dans un ordre aléatoire
4. DUn tableau déjà trié

Quel est le temps d'exécution du tri par base LSD sur n entiers de d chiffres en base k ?

1. AO(dn log k)
2. BO(n log n)
3. CO(d(n + k))
4. DO(n²)

Quelle est la complexité temporelle de l'algorithme de Bellman-Ford sur un graphe à V sommets et E arêtes ?

1. AO(V³ × E)
2. BO(V × E)
3. CO(V + E)
4. DO(E log V)

Pourquoi la recherche dichotomique ne s'exécute-t-elle pas en O(log n) sur une liste simplement chaînée ?

1. ALes listes chaînées ne peuvent pas être triées
2. BLes comparaisons sur les nœuds d'une liste chaînée sont plus lentes
3. CAtteindre l'élément du milieu prend O(n) étapes, faute d'accès direct par indice
4. DLa recherche dichotomique nécessite au moins deux fois plus de mémoire

Que se passerait-il si quelqu'un trouvait un algorithme en temps polynomial pour un problème NP-complet ?

1. ATout problème de NP pourrait être résolu en temps polynomial, donc P = NP
2. BTous les algorithmes en temps exponentiel s'exécuteraient immédiatement en temps linéaire
3. CSeul ce problème passerait dans P
4. DLe problème de l'arrêt deviendrait décidable