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

Quelle est la complexité temporelle de la recherche dichotomique dans un tableau trié ?

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

Qu'est-ce que le cas de base d'une fonction récursive ?

1. ALa première ligne de la fonction
2. BL'appel qui utilise le plus de mémoire
3. CLe cas avec l'entrée la plus grande, traité avant tout appel récursif
4. DUn cas traité directement, sans nouvel appel récursif

Quel algorithme de tri choisit un pivot et partitionne le tableau en éléments plus petits et plus grands ?

1. ALe tri fusion
2. BLe tri rapide (quicksort)
3. CLe tri à bulles
4. DLe tri par insertion

La complexité temporelle de la version récursive naïve de Fibonacci (fib(n) = fib(n−1) + fib(n−2)) est :

1. AConstante
2. BLinéaire
3. CExponentielle
4. DLogarithmique

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

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

Quelle est la complexité temporelle du tri rapide (quicksort) dans le pire cas ?

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

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, car le tri par insertion n'est pas un tri par comparaisons
3. CNon, la borne inférieure s'applique au pire cas sur toutes les entrées, pas à chaque entrée
4. DOui, la borne inférieure est donc fausse

Quelle est la complexité temporelle de : pour i = 1 à n : pour (j = i ; j ≤ n ; j = j + i) faire un travail O(1) ?

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