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

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

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

Quelles sont les trois étapes d'un algorithme « diviser pour régner » ?

1. ALire, calculer, écrire
2. BDeviner, vérifier, recommencer
3. CDiviser, régner, combiner
4. DTrier, chercher, renvoyer

La complexité spatiale mesure :

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

Un algorithme glouton :

1. AFait le meilleur choix local à chaque étape
2. BDonne toujours la solution optimale
3. CN'utilise que la récursivité
4. DEssaie toutes les solutions possibles

Un tri rapide utilise toujours le premier élément comme pivot. Sur quelle entrée présente-t-il son comportement de pire cas ?

1. AUn tableau dont tous les éléments sont distincts
2. BUn tableau de longueur 2
3. CUn tableau déjà trié
4. DUn tableau dans un ordre aléatoire

Quel est le temps d'exécution du tri par base LSD sur n entiers de d chiffres en base k ?

1. AO(n log n)
2. BO(n²)
3. CO(dn log k)
4. DO(d(n + k))

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

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. ANon, la borne inférieure s'applique au pire cas sur toutes les entrées, pas à chaque entrée
2. BNon, car le tri par insertion n'est pas un tri par comparaisons
3. COui, la borne inférieure est donc fausse
4. DOui, mais seulement pour les tableaux de moins de 100 éléments