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)

Qu'est-ce que la mémoïsation ?

1. AStocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire
2. BLibérer la mémoire après le retour d'une fonction
3. CConvertir automatiquement une récursion en boucle équivalente, si bien qu'aucune pile d'appels n'est nécessaire
4. DÉcrire des commentaires à côté de chaque ligne de code

Quelle notation décrit une borne supérieure de la croissance ?

1. APetit oméga (little omega)
2. BGrand O (Big O)
3. CGrand Thêta (Big Theta)
4. DGrand Oméga (Big Omega)

Combien de niveaux comporte la récursion du tri fusion pour un tableau de n éléments ?

1. AEnviron n / 2
2. BEnviron log₂ n
3. CEnviron √n
4. DEnviron n

Pourquoi de nombreuses routines de tri des bibliothèques passent-elles au tri par insertion pour les très petits sous-tableaux ?

1. ALe tri par insertion est en O(n log n) dans le pire cas
2. BLe tri par insertion utilise moins de mémoire que tout autre algorithme de tri sur les grandes entrées
3. CLes algorithmes récursifs ne peuvent pas traiter les tableaux de moins de 10 éléments
4. DLe tri par insertion a peu de surcoût et est rapide sur les entrées petites ou presque triées

Pourquoi la programmation dynamique n'apporte-t-elle aucune accélération réelle au tri fusion ?

1. ALa programmation dynamique ne fonctionne que sur les problèmes de graphes, pas sur les tableaux
2. BLe tri fusion n'a pas de structure récursive
3. CSes sous-problèmes ne se chevauchent pas, il n'y a donc rien à réutiliser
4. DLe tri fusion est déjà en O(n)

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

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

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 deux signifient que le problème n'a aucun algorithme
4. DLes problèmes intraitables ne peuvent être résolus par aucun algorithme, tandis que les indécidables demandent seulement un temps exponentiel