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

Qu'est-ce qu'un algorithme de force brute ?

1. AUn algorithme qui essaie toutes les solutions candidates possibles
2. BUn algorithme qui utilise toujours la récursion
3. CUn algorithme qui devine une réponse au hasard
4. DUn algorithme qui s'exécute sur de nombreux processeurs

Quel est le temps d'exécution du tri par comptage pour n entiers compris entre 0 et k ?

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

Quelle est la complexité temporelle dans le meilleur cas du tri par insertion, sur un tableau déjà trié ?

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

Quel est le temps d'exécution du tri par base LSD sur n entiers de d chiffres en base k ?

1. AO(n²)
2. BO(n log n)
3. CO(d(n + k))
4. DO(dn log k)

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(log n)
4. DO(2ⁿ)

Quel espace de pile utilise une fonction factorielle récursive simple fact(n) = n × fact(n − 1) ?

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

Pourquoi une recherche dans une table de hachage est-elle en O(1) en moyenne mais en O(n) dans le pire cas ?

1. ALes fonctions de hachage sont lentes
2. BL'accès aux tableaux est en O(n)
3. CLes clés doivent d'abord être triées
4. DDe nombreuses clés peuvent entrer en collision dans le même compartiment

Quelle technique donne au tri rapide un temps d'exécution espéré en O(n log n) pour toute entrée ?

1. AChoisir le pivot uniformément au hasard
2. BToujours choisir le premier élément
3. CTrier l'entrée avant d'exécuter le tri rapide
4. DN'utiliser la récursivité que sur la partie gauche