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

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

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

Quelle stratégie de conception utilise le tri fusion ?

1. ADiviser pour régner
2. BLe choix glouton
3. CLa programmation dynamique
4. DLa force brute

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

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

La programmation dynamique est utile lorsqu'un problème présente :

1. AAucun sous-problème, de sorte qu'il peut être résolu en une seule étape
2. BUne seule boucle
3. CUniquement des entrées aléatoires
4. DDes sous-problèmes qui se chevauchent et une sous-structure optimale

Quel espace de pile utilise une fonction factorielle récursive simple fact(n) = n × fact(n − 1) ?

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

Pourquoi omet-on généralement la base du logarithme dans la notation grand O, comme dans O(log n) ?

1. ALes logarithmes sont toujours arrondis à l'entier
2. BLa base n'a d'importance que pour n petit
3. CDes logarithmes de bases différentes ne diffèrent que d'un facteur constant
4. DTous les logarithmes en informatique sont en base 10, elle est donc implicite

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

Quelle est la différence entre un problème indécidable et un problème intraitable ?

1. ALes problèmes indécidables sont dans NP, tandis que les problèmes intraitables sont dans P
2. BUn problème indécidable n'a aucun algorithme valable pour toutes les entrées ; un problème intraitable en a un, mais il est trop lent
3. CLes problèmes intraitables ne peuvent être résolus par aucun algorithme, tandis que les indécidables demandent seulement un temps exponentiel
4. DLes deux signifient que le problème n'a aucun algorithme