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

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

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

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

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

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 n
2. BEnviron n²
3. CEnviron log₂ n
4. DEnviron n / 2

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

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

Un tri rapide utilise toujours le premier élément comme pivot. Sur quelle entrée présente-t-il son comportement de pire cas ?

1. AUn tableau dans un ordre aléatoire
2. BUn tableau dont tous les éléments sont distincts
3. CUn tableau déjà trié
4. DUn tableau de longueur 2

Est-il correct de dire qu'un algorithme en O(n²) est aussi en O(n³) ?

1. AOui, car le grand O est une borne supérieure et n² ne croît pas plus vite que n³
2. BOui, mais seulement si n est inférieur à 100
3. CNon, car n³ est plus petit que n² pour n grand
4. DNon, car le grand O doit toujours donner le taux de croissance exact de la fonction

Quelle borne est correcte pour log(n!) ?

1. AΘ(n log n)
2. BΘ(log n)
3. CΘ(n²)
4. DΘ(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(1) par incrémentation
2. BO(log n) par incrémentation
3. CO(n) par incrémentation
4. DO(n log n) par incrémentation