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

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

1. A9 secondes
2. B12 secondes
3. C3 secondes
4. D6 secondes

Que signifie qu'une opération s'exécute en temps O(1) ?

1. AElle ne peut être exécutée qu'une seule fois
2. BSon temps d'exécution n'augmente pas avec la taille de l'entrée
3. CElle prend toujours exactement une seconde
4. DElle traite exactement un élément par seconde de temps d'exécution

Quelle est la complexité temporelle dans le pire cas du tri par insertion ?

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

Un algorithme glouton :

1. ADonne toujours la solution optimale
2. BFait le meilleur choix local à chaque étape
3. CN'utilise que la récursivité
4. DEssaie toutes les solutions possibles

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

Quel est le temps d'exécution du tri par base LSD sur n entiers de d chiffres en base k ?

1. AO(n²)
2. BO(d(n + k))
3. CO(dn log k)
4. DO(n log n)

Quelles sont les deux choses à montrer pour prouver qu'un problème de décision X est NP-complet ?

1. AX est dans NP, et un problème NP-complet connu se réduit à X en temps polynomial
2. BX n'a pas d'algorithme polynomial, et X est décidable
3. CX est dans P, et X se réduit à SAT
4. DX se réduit à un problème de P, et X est dans NP

La multiplication de Karatsuba vérifie T(n) = 3T(n/2) + O(n). Quelle en est la solution ?

1. AΘ(n²)
2. BΘ(n^{log₂ 3}), soit environ n^1,585
3. CΘ(n log n)
4. DΘ(n³)