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

Un algorithme en O(n²) prend 1 seconde pour n = 1000. Combien de temps prend-il environ pour n = 2000 ?

1. A2 secondes
2. B8 secondes
3. C1 seconde
4. D4 secondes

Qu'est-ce que le cas de base d'une fonction récursive ?

1. AUn cas traité directement, sans nouvel appel récursif
2. BL'appel qui utilise le plus de mémoire
3. CLe cas avec l'entrée la plus grande, traité avant tout appel récursif
4. DLa première ligne de la fonction

Quelle est la complexité temporelle dans le meilleur cas du tri par insertion, sur un tableau déjà trié ?

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

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

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

La complexité temporelle de la version récursive naïve de Fibonacci (fib(n) = fib(n−1) + fib(n−2)) est :

1. AExponentielle
2. BLogarithmique
3. CLinéaire
4. DConstante

Quelle est la complexité temporelle du tri rapide (quicksort) dans le pire cas ?

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

Quel est le coût amorti de l'incrémentation d'un compteur binaire, sachant qu'une incrémentation peut inverser de nombreux bits ?

1. AO(n log n) par incrémentation
2. BO(1) par incrémentation
3. CO(n) par incrémentation
4. DO(log n) par incrémentation

Pour quelle variante du problème du sac à dos la règle gloutonne « prendre les objets par ordre de valeur par unité de poids » donne-t-elle toujours une réponse optimale ?

1. AAucune des deux variantes
2. BLe sac à dos fractionnaire, où les objets peuvent être fractionnés
3. CLes deux variantes
4. DLe sac à dos 0/1, où les objets doivent toujours être pris entiers