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

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

1. Af croît strictement plus 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 moins 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

Une boucle commence avec i = 1 et double i à chaque itération jusqu'à ce que i > n. Combien d'itérations effectue-t-elle ?

1. AEnviron n / 2
2. BEnviron n
3. CEnviron log₂ n
4. DEnviron n²

Comment fonctionne le tri par sélection ?

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

Que mesure l'analyse amortie ?

1. ALe coût moyen par opération sur une suite d'opérations de pire cas
2. BLe coût de l'unique opération la plus chère, où qu'elle se trouve dans la suite
3. CLe coût espéré sur des entrées aléatoires
4. DLe coût d'un algorithme sur la meilleure entrée

Quelle est la complexité temporelle de la multiplication de deux matrices n × n avec la triple boucle standard ?

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

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(mn)
3. CO(m + n)
4. DO(mn log n)

Le tri par insertion s'exécute en O(n) sur une entrée triée. Cela contredit-il la borne inférieure Ω(n log n) des tris par comparaisons ?

1. AOui, mais seulement pour les tableaux de moins de 100 éléments
2. BNon, car le tri par insertion n'est pas un tri par comparaisons
3. COui, la borne inférieure est donc fausse
4. DNon, la borne inférieure s'applique au pire cas sur toutes les entrées, pas à chaque entré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²)
2. BO(n √n)
3. CO(n log n)
4. DO(n)