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

Comment fonctionne le tri par sélection ?

1. AIl cherche à plusieurs reprises le minimum de la partie non triée et l'échange vers l'avant
2. BIl insère chaque élément dans une partie triée croissante par décalages
3. CIl divise le tableau en deux moitiés et les fusionne
4. DIl échange à plusieurs reprises les éléments voisins mal ordonnés

Le temps d'exécution d'un algorithme est O(n). Comment appelle-t-on cette croissance ?

1. AQuadratique
2. BLinéaire
3. CLogarithmique
4. DConstante

Laquelle de ces fonctions croît le plus lentement quand n devient grand ?

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

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(n)
2. BO(2ⁿ)
3. CO(n²)
4. DO(log n)

La programmation dynamique est utile lorsqu'un problème présente :

1. AAucun sous-problème, de sorte qu'il peut être résolu en une seule étape
2. BUniquement des entrées aléatoires
3. CUne seule boucle
4. DDes sous-problèmes qui se chevauchent et une sous-structure optimale

Pourquoi la programmation dynamique n'apporte-t-elle aucune accélération réelle au tri fusion ?

1. ALe tri fusion n'a pas de structure récursive
2. BLe tri fusion est déjà en O(n)
3. CSes sous-problèmes ne se chevauchent pas, il n'y a donc rien à réutiliser
4. DLa programmation dynamique ne fonctionne que sur les problèmes de graphes, pas sur les tableaux

Quel est le temps d'exécution de l'algorithme de Dijkstra avec un tas binaire sur un graphe à V sommets et E arêtes ?

1. AO(V³)
2. BO((V + E) log V)
3. CO(V × E)
4. DO(V + E)

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 √n)
2. BO(n²)
3. CO(n)
4. DO(n log n)