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

Quelle est la complexité temporelle de la recherche de la plus grande valeur dans un tableau non trié de n nombres ?

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

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

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

Comment fonctionne le tri par sélection ?

1. AIl échange à plusieurs reprises les éléments voisins mal ordonnés
2. BIl cherche à plusieurs reprises le minimum de la partie non triée et l'échange vers l'avant
3. CIl divise le tableau en deux moitiés et les fusionne
4. DIl insère chaque élément dans une partie triée croissante par décalages

Quelle est la complexité temporelle de la multiplication de deux matrices n × n avec la triple boucle standard ?

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

Quelle est la complexité temporelle du calcul du n-ième nombre de Fibonacci avec une table remplie de bas en haut ?

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

Quelle est la complexité temporelle de l'algorithme standard de programmation dynamique pour la plus longue sous-séquence commune de chaînes de longueurs m et n ?

1. AO(mn)
2. BO(mn log n)
3. CO(m + n)
4. DO(2^m+n)

Pourquoi la recherche dichotomique ne s'exécute-t-elle pas en O(log n) sur une liste simplement chaînée ?

1. ALa recherche dichotomique nécessite au moins deux fois plus de mémoire
2. BLes listes chaînées ne peuvent pas être triées
3. CLes comparaisons sur les nœuds d'une liste chaînée sont plus lentes
4. DAtteindre l'élément du milieu prend O(n) étapes, faute d'accès direct par indice

Comment se comparent n! et 2ⁿ pour n grand ?

1. An! croît plus vite que 2ⁿ
2. B2ⁿ croît plus vite que n!
3. Cn! est O(n²)
4. DIls croissent au même rythme