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

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

1. Af croît strictement plus vite que g
2. Bf croît strictement moins 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

Un algorithme en O(n) prend 3 secondes pour n = 1 million. Combien de temps prend-il environ pour n = 2 millions ?

1. A12 secondes
2. B9 secondes
3. C6 secondes
4. D3 secondes

Un algorithme comportant deux boucles imbriquées, chacune exécutée n fois, a généralement quelle complexité ?

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

Quelle est la complexité temporelle amortie de l'ajout en fin de tableau dynamique qui double sa capacité lorsqu'il est plein ?

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

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 20
2. BEnviron 1,000
3. CEnviron 100
4. DEnviron 500,000

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

1. AUn ordre topologique en O(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 arbre couvrant de poids minimal en O(E log V)

D'après le théorème maître, T(n) = 8T(n/2) + O(n²) a pour solution :

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

Quel est le temps d'exécution de l'algorithme de Dijkstra avec un tas binaire sur un graphe à V sommets et E arêtes ?

1. AO(V × E)
2. BO((V + E) log V)
3. CO(V + E)
4. DO(V³)