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

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

1. ALire, calculer, écrire
2. BTrier, chercher, renvoyer
3. CDeviner, vérifier, recommencer
4. DDiviser, régner, combiner

Que signifie qu'une opération s'exécute en temps O(1) ?

1. AElle traite exactement un élément par seconde de temps d'exécution
2. BSon temps d'exécution n'augmente pas avec la taille de l'entrée
3. CElle prend toujours exactement une seconde
4. DElle ne peut être exécutée qu'une seule fois

Quel est le temps d'exécution du tri par comptage pour n entiers compris entre 0 et k ?

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

Pourquoi omet-on généralement la base du logarithme dans la notation grand O, comme dans O(log n) ?

1. ALa base n'a d'importance que pour n petit
2. BTous les logarithmes en informatique sont en base 10, elle est donc implicite
3. CDes logarithmes de bases différentes ne diffèrent que d'un facteur constant
4. DLes logarithmes sont toujours arrondis à l'entier

Une fonction exécute une boucle de n itérations, puis, séparément, une autre boucle de n itérations. Quelle est sa complexité temporelle ?

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

La programmation dynamique est utile lorsqu'un problème présente :

1. ADes sous-problèmes qui se chevauchent et une sous-structure optimale
2. BAucun sous-problème, de sorte qu'il peut être résolu en une seule étape
3. CUniquement des entrées aléatoires
4. DUne seule boucle

Quelle borne est correcte pour log(n!) ?

1. AΘ(n²)
2. BΘ(log n)
3. CΘ(n)
4. DΘ(n log n)

L'algorithme de programmation dynamique de Held-Karp résout exactement le problème du voyageur de commerce. Quel est son temps d'exécution pour n villes ?

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