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

Quelle notation décrit une borne supérieure de la croissance ?

1. AGrand O (Big O)
2. BPetit oméga (little omega)
3. CGrand Oméga (Big Omega)
4. DGrand Thêta (Big Theta)

Que vaut log₂ 1024 ?

1. A32
2. B12
3. C10
4. D512

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

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

Environ combien de comparaisons la recherche dichotomique nécessite-t-elle dans le pire cas sur un tableau trié de 1,000,000 d'éléments ?

1. AEnviron 500,000
2. BEnviron 100
3. CEnviron 1,000
4. DEnviron 20

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

Comment l'algorithme de Prim construit-il un arbre couvrant de poids minimal ?

1. AIl exécute un parcours en largeur et conserve l'arbre du BFS
2. BIl fait croître un seul arbre à partir d'un sommet de départ, en ajoutant l'arête la moins chère qui sort de l'arbre
3. CIl trie toutes les arêtes par poids et ajoute chacune d'elles sauf si elle formait un cycle dans la forêt
4. DIl supprime l'arête la plus chère jusqu'à ce qu'il ne reste plus de cycle

Quelle est la solution de la récurrence T(n) = 2T(n/2) + n log n ?

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

Quel est le coût amorti de l'incrémentation d'un compteur binaire, sachant qu'une incrémentation peut inverser de nombreux bits ?

1. AO(1) par incrémentation
2. BO(n log n) par incrémentation
3. CO(n) par incrémentation
4. DO(log n) par incrémentation