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

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 notation décrit une borne inférieure de croissance ?

1. Ao (petit o)
2. BO (grand O)
3. CΩ (grand Oméga)
4. DΘ (grand Thêta)

Quel algorithme de tri échange de façon répétée les éléments adjacents qui sont dans le mauvais ordre ?

1. ATri à bulles
2. BTri fusion
3. CTri par tas
4. DTri rapide (quicksort)

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

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

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

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

Quelle est la complexité temporelle du calcul du n-ième nombre de Fibonacci avec une table remplie de bas en haut ?

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

Comment se comparent n! et 2ⁿ pour n grand ?

1. An! est O(n²)
2. B2ⁿ croît plus vite que n!
3. CIls croissent au même rythme
4. Dn! croît plus vite que 2ⁿ

Pourquoi la recherche dichotomique ne s'exécute-t-elle pas en O(log n) sur une liste simplement chaînée ?

1. AAtteindre l'élément du milieu prend O(n) étapes, faute d'accès direct par indice
2. BLes listes chaînées ne peuvent pas être triées
3. CLa recherche dichotomique nécessite au moins deux fois plus de mémoire
4. DLes comparaisons sur les nœuds d'une liste chaînée sont plus lentes