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

Quelle est la complexité temporelle dans le pire cas du tri par insertion ?

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

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

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

Quel algorithme de tri choisit un pivot et partitionne le tableau en éléments plus petits et plus grands ?

1. ALe tri par insertion
2. BLe tri rapide (quicksort)
3. CLe tri fusion
4. DLe tri à bulles

Vous triez une fois un tableau de n éléments, puis répondez à k requêtes d'appartenance par recherche dichotomique. Quel est le coût total ?

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

Pourquoi omet-on généralement la base du logarithme dans la notation grand O, comme dans O(log n) ?

1. ADes logarithmes de bases différentes ne diffèrent que d'un facteur constant
2. BLes logarithmes sont toujours arrondis à l'entier
3. CTous les logarithmes en informatique sont en base 10, elle est donc implicite
4. DLa base n'a d'importance que pour n petit

Quelle est la complexité temporelle de l'algorithme standard de programmation dynamique pour la plus longue sous-séquence commune de chaînes de longueurs m et n ?

1. AO(2^m+n)
2. BO(m + n)
3. CO(mn)
4. DO(mn log n)

Quelle est la différence entre un problème indécidable et un problème intraitable ?

1. ALes deux signifient que le problème n'a aucun algorithme
2. BLes problèmes intraitables ne peuvent être résolus par aucun algorithme, tandis que les indécidables demandent seulement un temps exponentiel
3. CUn problème indécidable n'a aucun algorithme valable pour toutes les entrées ; un problème intraitable en a un, mais il est trop lent
4. DLes problèmes indécidables sont dans NP, tandis que les problèmes intraitables sont dans P

Quelle technique donne au tri rapide un temps d'exécution espéré en O(n log n) pour toute entrée ?

1. AToujours choisir le premier élément
2. BChoisir le pivot uniformément au hasard
3. CTrier l'entrée avant d'exécuter le tri rapide
4. DN'utiliser la récursivité que sur la partie gauche