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

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

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

Que signifie f(n) = Θ(g(n)) ?

1. Af croît strictement moins vite que g
2. Bf est toujours plus petite que g pour tout n, donc g la borne par le haut mais jamais par le bas
3. Cf croît strictement plus vite que g
4. Df croît au même rythme que g, bornée en haut et en bas par des multiples constants de g

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

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

Que signifie qu'un problème possède une sous-structure optimale ?

1. ALe problème a exactement une solution optimale, que partagent tous les sous-problèmes
2. BUne solution optimale peut être construite à partir de solutions optimales de ses sous-problèmes
3. CTous les sous-problèmes ont la même taille
4. DLe problème peut être résolu en temps constant

Quel est le temps d'exécution du tri par base LSD sur n entiers de d chiffres en base k ?

1. AO(n log n)
2. BO(dn log k)
3. CO(n²)
4. DO(d(n + k))

Une fonction exécute une boucle de n itérations, puis, séparément, une autre boucle de n itérations. Quelle est sa complexité temporelle ?

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

Quelle est la complexité temporelle de : pour i = 1 à n : pour (j = i ; j ≤ n ; j = j + i) faire un travail O(1) ?

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

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

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