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

Que vaut log₂ 1024 ?

1. A32
2. B12
3. C10
4. D512

Que décrit le temps d'exécution dans le pire cas d'un algorithme ?

1. ALe temps maximal sur toutes les entrées de taille n
2. BLe temps sur un ordinateur lent
3. CLe temps sur la plus petite entrée
4. DLe temps espéré sur une entrée aléatoire de taille n

Le temps d'exécution d'un algorithme est O(n). Comment appelle-t-on cette croissance ?

1. AConstante
2. BLogarithmique
3. CLinéaire
4. DQuadratique

Pourquoi de nombreuses routines de tri des bibliothèques passent-elles au tri par insertion pour les très petits sous-tableaux ?

1. ALe tri par insertion est en O(n log n) dans le pire cas
2. BLe tri par insertion utilise moins de mémoire que tout autre algorithme de tri sur les grandes entrées
3. CLe tri par insertion a peu de surcoût et est rapide sur les entrées petites ou presque triées
4. DLes algorithmes récursifs ne peuvent pas traiter les tableaux de moins de 10 éléments

Dans un tableau trié, vous cherchez deux éléments dont la somme vaut une cible en déplaçant un pointeur depuis chaque extrémité vers l'intérieur. Quelle est la complexité temporelle ?

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

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

Quelle est la solution de la récurrence T(n) = 2T(n/2) + n log n ?

1. AΘ(n²)
2. BΘ(n log² n)
3. CΘ(n)
4. DΘ(n 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. AC'est indécidable
2. BOn peut le résoudre avec l'algorithme de Dijkstra en prenant l'opposé des poids
3. CC'est NP-difficile
4. DC'est toujours résoluble en O(V + E)