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

Que vaut log₂ 1024 ?

1. A10
2. B32
3. C12
4. D512

Quelle notation décrit une borne inférieure de croissance ?

1. AO (grand O)
2. BΩ (grand Oméga)
3. Co (petit o)
4. DΘ (grand Thêta)

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

1. AO(n log n)
2. BO(n²)
3. CO(n + k)
4. DO(k 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(m + n)
3. CO(2^m+n)
4. DO(mn log n)

Que calcule l'algorithme de Floyd-Warshall, et en combien de temps ?

1. AUn arbre couvrant de poids minimal en O(E log V)
2. BLes plus courts chemins depuis un sommet source vers tous les autres en O(V + E)
3. CLes plus courts chemins entre toutes les paires de sommets en O(V³)
4. DUn ordre topologique en O(V²)

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

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

Pourquoi toute recherche par comparaisons dans un tableau trié nécessite-t-elle Ω(log n) comparaisons dans le pire cas ?

1. AChaque élément doit être comparé au moins une fois
2. BUn arbre de décision à n issues possibles doit avoir une profondeur d'au moins log₂ n
3. CChaque comparaison prend un temps logarithmique
4. DLa recherche dichotomique est le seul algorithme possible, et elle nécessite log₂ n comparaisons

Quelle est la complexité temporelle de la construction d'un tas binaire à partir de n éléments non triés avec la méthode ascendante (bottom-up) ?

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