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

On dit généralement qu'un problème est traitable (« tractable ») si :

1. AIl peut être résolu en temps polynomial
2. BIl n'a pas de solution
3. CIl peut être résolu en temps constant
4. DIl ne peut être résolu qu'en essayant toutes les possibilités

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

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

Que décrit le temps d'exécution en moyenne ?

1. ALe temps pour une entrée de longueur moyenne
2. BLe temps sur l'ordinateur le plus répandu
3. CLa valeur intermédiaire entre les temps d'exécution du meilleur et du pire cas
4. DLe temps espéré selon une distribution donnée des entrées de taille n

Une fonction exécute une boucle de n itérations, puis, séparément, une autre boucle de n itérations. Quelle est sa complexité temporelle ?

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

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

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

Vous triez une fois un tableau de n éléments, puis répondez à k requêtes d'appartenance par recherche dichotomique. Quel est le coût total ?

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

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. BO(n³)
3. CO(n² 2ⁿ)
4. DO(2^n²)

Quels sont les coûts en temps et en espace du calcul du n-ième nombre de Fibonacci avec une boucle qui ne conserve que les deux dernières valeurs ?

1. AO(n) en temps et O(n) en espace
2. BO(log n) en temps et O(n) en espace
3. CO(2ⁿ) en temps et O(1) en espace
4. DO(n) en temps et O(1) en espace