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 log n)
3. CO(n³)
4. DO(2ⁿ)

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 ne peut être exécutée qu'une seule fois
4. DElle prend toujours exactement une seconde

Quel est le grand O de 3n² + 5n + 2 ?

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

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

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

La borne inférieure du tri par comparaisons dans le pire cas est :

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

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 borne est correcte pour log(n!) ?

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

Les plus courts chemins simples peuvent être trouvés en temps polynomial. Que sait-on de la recherche du plus long chemin simple entre deux sommets dans un graphe quelconque ?

1. AOn peut le résoudre avec l'algorithme de Dijkstra en prenant l'opposé des poids
2. BC'est NP-difficile
3. CC'est indécidable
4. DC'est toujours résoluble en O(V + E)