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

Quelle est la complexité temporelle du parcours en profondeur d'un graphe stocké sous forme de listes d'adjacence ?

1. AO(V²)
2. BO(V + E)
3. CO(E log V)
4. DO(V × E)

Laquelle de ces fonctions croît le plus lentement quand n devient grand ?

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

Une boucle commence avec i = 1 et double i à chaque itération jusqu'à ce que i > n. Combien d'itérations effectue-t-elle ?

1. AEnviron n / 2
2. BEnviron log₂ n
3. CEnviron n
4. DEnviron n²

Est-il correct de dire qu'un algorithme en O(n²) est aussi en O(n³) ?

1. ANon, car n³ est plus petit que n² pour n grand
2. BOui, car le grand O est une borne supérieure et n² ne croît pas plus vite que n³
3. CNon, car le grand O doit toujours donner le taux de croissance exact de la fonction
4. DOui, mais seulement si n est inférieur à 100

Dans le problème de sélection d'activités, quelle règle gloutonne donne toujours un nombre maximal d'activités sans chevauchement ?

1. AChoisir l'activité qui se termine le plus tôt, puis recommencer avec les activités compatibles
2. BChoisir d'abord l'activité la plus courte
3. CChoisir l'activité qui commence le plus tôt
4. DChoisir d'abord l'activité ayant le moins de chevauchements, puis recommencer avec les activités compatibles

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

Quel algorithme trouve un arbre couvrant de poids minimal en ajoutant de façon répétée l'arête la moins coûteuse qui ne forme pas de cycle ?

1. AL'algorithme de Kruskal
2. BFloyd-Warshall
3. CL'algorithme de Dijkstra
4. DL'algorithme de Prim à partir d'un seul nœud

La multiplication de Karatsuba vérifie T(n) = 3T(n/2) + O(n). Quelle en est la solution ?

1. AΘ(n log n)
2. BΘ(n²)
3. CΘ(n^{log₂ 3}), soit environ n^1,585
4. DΘ(n³)