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

Quelle classe de complexité croît le plus vite pour de grandes valeurs de n ?

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

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

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

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

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

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

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

Que signifie qu'un problème possède une sous-structure optimale ?

1. ALe problème peut être résolu en temps constant
2. BTous les sous-problèmes ont la même taille
3. CLe problème a exactement une solution optimale, que partagent tous les sous-problèmes
4. DUne solution optimale peut être construite à partir de solutions optimales de ses sous-problèmes

Avec des pièces de 1, 3 et 4 et un montant de 6, combien de pièces utilise la méthode gloutonne « la plus grosse pièce d'abord », comparée à l'optimum ?

1. ALe glouton utilise 4 pièces ; l'optimum est 3
2. BLe glouton utilise 2 pièces ; l'optimum est 2
3. CLe glouton utilise 3 pièces ; l'optimum est 2
4. DLe glouton utilise 3 pièces ; l'optimum est 3

Lequel de ces problèmes de satisfiabilité est connu pour être résoluble en temps polynomial ?

1. ALa satisfiabilité de circuits
2. B3-SAT, où chaque clause a exactement trois littéraux
3. C2-SAT, où chaque clause a au plus deux littéraux
4. DSAT général sur des formules en forme normale conjonctive

Quel est le coût amorti de l'incrémentation d'un compteur binaire, sachant qu'une incrémentation peut inverser de nombreux bits ?

1. AO(n) par incrémentation
2. BO(n log n) par incrémentation
3. CO(1) par incrémentation
4. DO(log n) par incrémentation