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

La complexité spatiale mesure :

1. ALa taille physique de l'ordinateur
2. BL'espace disque du fichier du programme une fois compilé
3. CLa quantité de mémoire dont un algorithme a besoin lorsque la taille de l'entrée augmente
4. DLe nombre de lignes de code

Quelle est la complexité temporelle de la recherche linéaire dans un tableau non trié de n éléments (pire cas) ?

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

Lequel de ces temps d'exécution est polynomial ?

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

Que signifie qu'un problème possède une sous-structure optimale ?

1. AUne solution optimale peut être construite à partir de solutions optimales de ses sous-problèmes
2. BLe problème a exactement une solution optimale, que partagent tous les sous-problèmes
3. CTous les sous-problèmes ont la même taille
4. DLe problème peut être résolu en temps constant

Quelle est la complexité temporelle de : pour i = 1 à n : pour j = 1 à i : faire un travail O(1) ?

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

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

1. AO(n²)
2. BO(n)
3. CO(n log n)
4. DO(log 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 comparaisons sur les nœuds d'une liste chaînée sont plus lentes
2. BAtteindre l'élément du milieu prend O(n) étapes, faute d'accès direct par indice
3. CLa recherche dichotomique nécessite au moins deux fois plus de mémoire
4. DLes listes chaînées ne peuvent pas être triées

Pour quelle variante du problème du sac à dos la règle gloutonne « prendre les objets par ordre de valeur par unité de poids » donne-t-elle toujours une réponse optimale ?

1. ALe sac à dos fractionnaire, où les objets peuvent être fractionnés
2. BAucune des deux variantes
3. CLes deux variantes
4. DLe sac à dos 0/1, où les objets doivent toujours être pris entiers