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

Lequel de ces temps d'exécution est polynomial ?

1. AO(n!)
2. BO(2ⁿ)
3. CO(n³)
4. DO(nⁿ)

Qu'est-ce que la mémoïsation ?

1. AConvertir automatiquement une récursion en boucle équivalente, si bien qu'aucune pile d'appels n'est nécessaire
2. BÉcrire des commentaires à côté de chaque ligne de code
3. CLibérer la mémoire après le retour d'une fonction
4. DStocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire

Qu'exige la recherche dichotomique de son entrée ?

1. ALe tableau ne doit contenir que des nombres positifs
2. BLe tableau ne doit pas avoir plus de 1000 éléments
3. CLa longueur du tableau doit être une puissance de deux
4. DLe tableau doit être trié

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

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

Pourquoi de nombreuses routines de tri des bibliothèques passent-elles au tri par insertion pour les très petits sous-tableaux ?

1. ALe tri par insertion a peu de surcoût et est rapide sur les entrées petites ou presque triées
2. BLes algorithmes récursifs ne peuvent pas traiter les tableaux de moins de 10 éléments
3. CLe tri par insertion est en O(n log n) dans le pire cas
4. DLe tri par insertion utilise moins de mémoire que tout autre algorithme de tri sur les grandes entrées

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

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

Le tri topologique n'est possible que pour :

1. ALes graphes non orientés
2. BLes graphes orientés acycliques (DAG)
3. CLes graphes complets
4. DLes graphes à poids négatifs

Quel énoncé sur la notation petit o est correct ?

1. A2n = o(n), car 2n croît lentement
2. Bn = o(n²), mais n n'est pas o(n)
3. Cn = o(n), puisque toute fonction est un petit o d'elle-même
4. Dn² = o(n)