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(log n)
4. DO(n²)

Quelle stratégie de conception utilise le tri fusion ?

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

Que signifie f(n) = Θ(g(n)) ?

1. Af croît strictement moins vite que g
2. Bf croît strictement plus vite que g
3. Cf croît au même rythme que g, bornée en haut et en bas par des multiples constants de g
4. Df est toujours plus petite que g pour tout n, donc g la borne par le haut mais jamais par le bas

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 déjà trié
2. BUn tableau de longueur 2
3. CUn tableau dont tous les éléments sont distincts
4. DUn tableau dans un ordre aléatoire

Quelle est la complexité temporelle de : pour i = 1 à n : (j = 1 ; tant que j < n : j = j × 2) ?

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

Quelle est la complexité temporelle de la multiplication de deux matrices n × n avec la triple boucle standard ?

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

Un problème est NP-complet s'il :

1. AEst résoluble en temps polynomial
2. BAppartient à NP et si tout problème NP se réduit à lui en temps polynomial
3. CEst hors de NP mais plus difficile que tous les problèmes NP, comme le problème de l'arrêt
4. DEst impossible à résoudre