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

On dit généralement qu'un problème est traitable (« tractable ») si :

1. AIl n'a pas de solution
2. BIl peut être résolu en temps constant
3. CIl ne peut être résolu qu'en essayant toutes les possibilités
4. DIl peut être résolu en temps polynomial

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

1. AO(log n)
2. BO(n²)
3. CO(n log 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 fusion
4. DLe tri à bulles

Quel algorithme trouve les plus courts chemins depuis une source dans un graphe dont les poids des arêtes sont positifs ou nuls ?

1. AL'algorithme de Kruskal
2. BBellman-Ford est nécessaire dans tous les cas
3. CLe parcours en profondeur (DFS)
4. DL'algorithme de Dijkstra

Quelle est la complexité temporelle du tri rapide (quicksort) dans le pire cas ?

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

Une fonction exécute une boucle de n itérations, puis, séparément, une autre boucle de n itérations. Quelle est sa complexité temporelle ?

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

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. BLa recherche dichotomique nécessite au moins deux fois plus de mémoire
3. CLes comparaisons sur les nœuds d'une liste chaînée sont plus lentes
4. DAtteindre l'élément du milieu prend O(n) étapes, faute d'accès direct par indice

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(log n) en temps et O(n) en espace
2. BO(n) en temps et O(1) en espace
3. CO(n) en temps et O(n) en espace
4. DO(2ⁿ) en temps et O(1) en espace