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

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

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

Quelle est la complexité temporelle de la recherche de la plus grande valeur dans un tableau non trié de n nombres ?

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

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

1. Af croît au même rythme que g, bornée en haut et en bas par des multiples constants de g
2. Bf croît strictement plus vite que g
3. Cf croît strictement moins vite que 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 complexité temporelle du calcul du n-ième nombre de Fibonacci avec une table remplie de bas en haut ?

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

Dans le problème de sélection d'activités, quelle règle gloutonne donne toujours un nombre maximal d'activités sans chevauchement ?

1. AChoisir l'activité qui se termine le plus tôt, puis recommencer avec les activités compatibles
2. BChoisir d'abord l'activité ayant le moins de chevauchements, puis recommencer avec les activités compatibles
3. CChoisir l'activité qui commence le plus tôt
4. DChoisir d'abord l'activité la plus courte

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(2ⁿ) en temps et O(1) en espace
2. BO(log n) en temps et O(n) en espace
3. CO(n) en temps et O(n) en espace
4. DO(n) en temps et O(1) en espace

Pour montrer qu'un nouveau problème X est NP-difficile, que faut-il faire ?

1. ARéduire X à un problème NP-difficile connu en temps polynomial
2. BRéduire un problème NP-difficile connu à X en temps polynomial
3. CMontrer que X peut être vérifié en temps polynomial
4. DMontrer que X n'a pas d'algorithme polynomial pour les petites entrées