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

Quelle est la complexité temporelle de la recherche linéaire dans un tableau non trié de n éléments (pire cas) ?

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

Qu'exige la recherche dichotomique de son entrée ?

1. ALe tableau ne doit contenir que des nombres positifs
2. BLa longueur du tableau doit être une puissance de deux
3. CLe tableau ne doit pas avoir plus de 1000 éléments
4. DLe tableau doit être trié

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

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

Quelle est la solution de la récurrence T(n) = T(n − 1) + O(n) ?

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

Quel algorithme trouve les plus courts chemins depuis une source dans un graphe dont les poids des arêtes sont positifs ou nuls ?

1. ABellman-Ford est nécessaire dans tous les cas
2. BL'algorithme de Kruskal
3. CLe parcours en profondeur (DFS)
4. DL'algorithme de Dijkstra

Le parcours en largeur (BFS) sur un graphe non pondéré trouve :

1. AL'arbre couvrant de poids minimal
2. BUn ordre topologique dans tous les graphes
3. CLes plus courts chemins dans les graphes qui contiennent des poids d'arêtes négatifs
4. DLes plus courts chemins en nombre d'arêtes depuis le nœud de départ

Le tri par insertion s'exécute en O(n) sur une entrée triée. Cela contredit-il la borne inférieure Ω(n log n) des tris par comparaisons ?

1. AOui, mais seulement pour les tableaux de moins de 100 éléments
2. BNon, la borne inférieure s'applique au pire cas sur toutes les entrées, pas à chaque entrée
3. COui, la borne inférieure est donc fausse
4. DNon, car le tri par insertion n'est pas un tri par comparaisons

D'après le théorème maître, T(n) = 8T(n/2) + O(n²) a pour solution :

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