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

Comment appelle-t-on une croissance en O(2ⁿ) ?

1. ALogarithmique
2. BPolynomiale
3. CExponentielle
4. DLinéaire

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

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

Que signifie f(n) = Θ(g(n)) ?

1. Af croît strictement moins vite que g
2. Bf croît strictement plus vite que g
3. Cf croît au même rythme que g, bornée en haut et en bas par des multiples constants de g
4. Df est toujours plus petite que g pour tout n, donc g la borne par le haut mais jamais par le bas

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

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

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

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

Le parcours en largeur (BFS) sur un graphe non pondéré trouve :

1. AL'arbre couvrant de poids minimal
2. BLes plus courts chemins en nombre d'arêtes depuis le nœud de départ
3. CUn ordre topologique dans tous les graphes
4. DLes plus courts chemins dans les graphes qui contiennent des poids d'arêtes négatifs

L'algorithme de programmation dynamique de Held-Karp résout exactement le problème du voyageur de commerce. Quel est son temps d'exécution pour n villes ?

1. AO(n² 2ⁿ)
2. BO(n³)
3. CO(2^n²)
4. DO(n!)

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

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