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

Que décrit le temps d'exécution dans le pire cas d'un algorithme ?

1. ALe temps sur la plus petite entrée
2. BLe temps maximal sur toutes les entrées de taille n
3. CLe temps espéré sur une entrée aléatoire de taille n
4. DLe temps sur un ordinateur lent

Quelles sont les trois étapes d'un algorithme « diviser pour régner » ?

1. ADeviner, vérifier, recommencer
2. BDiviser, régner, combiner
3. CTrier, chercher, renvoyer
4. DLire, calculer, écrire

Une boucle commence avec i = 1 et double i à chaque itération jusqu'à ce que i > n. Combien d'itérations effectue-t-elle ?

1. AEnviron log₂ n
2. BEnviron n / 2
3. CEnviron n²
4. DEnviron 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(log n)
2. BO(n²)
3. CO(n)
4. DO(1)

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

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

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

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

Prendre les deux extrémités de chaque arête d'un couplage maximal donne une couverture par sommets. Quelle est la qualité de cette couverture ?

1. ADe qualité inconnue par rapport à l'optimum
2. BAu plus log n fois le minimum
3. CAu plus deux fois la taille d'une couverture par sommets minimale
4. DToujours une couverture par sommets minimale

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(log n) par incrémentation
3. CO(n) par incrémentation
4. DO(1) par incrémentation