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 divise le tableau en deux moitiés et les fusionne
3. CIl insère chaque élément dans une partie triée croissante par décalages
4. DIl échange à plusieurs reprises les éléments voisins mal ordonnés

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

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

Quel algorithme de tri choisit un pivot et partitionne le tableau en éléments plus petits et plus grands ?

1. ALe tri rapide (quicksort)
2. BLe tri par insertion
3. CLe tri fusion
4. DLe tri à bulles

Combien de niveaux comporte la récursion du tri fusion pour un tableau de n éléments ?

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

Environ combien de comparaisons la recherche dichotomique nécessite-t-elle dans le pire cas sur un tableau trié de 1,000,000 d'éléments ?

1. AEnviron 1,000
2. BEnviron 500,000
3. CEnviron 20
4. DEnviron 100

Pourquoi de nombreuses routines de tri des bibliothèques passent-elles au tri par insertion pour les très petits sous-tableaux ?

1. ALes algorithmes récursifs ne peuvent pas traiter les tableaux de moins de 10 éléments
2. BLe tri par insertion est en O(n log n) dans le pire cas
3. CLe tri par insertion utilise moins de mémoire que tout autre algorithme de tri sur les grandes entrées
4. DLe tri par insertion a peu de surcoût et est rapide sur les entrées petites ou presque triées

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

Quelle affirmation concernant P et NP est correcte ?

1. ATout problème de P appartient aussi à NP
2. BNP signifie « non polynomial »
3. CLes solutions des problèmes NP ne peuvent pas être vérifiées rapidement
4. DIl a été démontré que P ≠ NP