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

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

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

Quelle classe de complexité croît le plus vite pour de grandes valeurs de n ?

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

On dit généralement qu'un problème est traitable (« tractable ») si :

1. AIl peut être résolu en temps constant
2. BIl peut être résolu en temps polynomial
3. CIl n'a pas de solution
4. DIl ne peut être résolu qu'en essayant toutes les possibilités

Un tri rapide utilise toujours le premier élément comme pivot. Sur quelle entrée présente-t-il son comportement de pire cas ?

1. AUn tableau dans un ordre aléatoire
2. BUn tableau dont tous les éléments sont distincts
3. CUn tableau déjà trié
4. DUn tableau de longueur 2

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

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

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

Pourquoi toute recherche par comparaisons dans un tableau trié nécessite-t-elle Ω(log n) comparaisons dans le pire cas ?

1. AChaque comparaison prend un temps logarithmique
2. BChaque élément doit être comparé au moins une fois
3. CLa recherche dichotomique est le seul algorithme possible, et elle nécessite log₂ n comparaisons
4. DUn arbre de décision à n issues possibles doit avoir une profondeur d'au moins log₂ n

L'algorithme de Strassen multiplie des matrices en utilisant 7 au lieu de 8 multiplications récursives de blocs de taille moitié. Quel est son temps d'exécution ?

1. AΘ(n^{log₂ 7}), soit environ n^2,81
2. BΘ(n³)
3. CΘ(n² log n)
4. DΘ(n²)