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

Laquelle de ces fonctions croît le plus lentement quand n devient grand ?

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

L'accès à un élément d'un tableau par son indice prend :

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

Que décrit le temps d'exécution en moyenne ?

1. ALe temps sur l'ordinateur le plus répandu
2. BLe temps pour une entrée de longueur moyenne
3. CLe temps espéré selon une distribution donnée des entrées de taille n
4. DLa valeur intermédiaire entre les temps d'exécution du meilleur et du pire cas

Quelle est la complexité temporelle du calcul du n-ième nombre de Fibonacci avec une table remplie de bas en haut ?

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

Quel algorithme de tri est stable ?

1. ATri par sélection (version habituelle)
2. BTri par tas
3. CTri rapide (version en place habituelle)
4. DTri fusion

Quelle est la complexité temporelle amortie de l'ajout en fin de tableau dynamique qui double sa capacité lorsqu'il est plein ?

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

Quelle définition de la classe NP est correcte ?

1. ALes problèmes de décision dont les réponses « oui » peuvent être vérifiées en temps polynomial à l'aide d'un certificat
2. BLes problèmes qui ne sont pas polynomiaux
3. CLes problèmes qu'aucun algorithme ne peut résoudre
4. DLes problèmes qui ne peuvent pas être résolus en temps polynomial

Le tri par insertion s'exécute en O(n) sur une entrée triée. Cela contredit-il la borne inférieure Ω(n log n) des tris par comparaisons ?

1. AOui, la borne inférieure est donc fausse
2. BOui, mais seulement pour les tableaux de moins de 100 éléments
3. CNon, la borne inférieure s'applique au pire cas sur toutes les entrées, pas à chaque entrée
4. DNon, car le tri par insertion n'est pas un tri par comparaisons