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

La complexité spatiale mesure :

1. ALa taille physique de l'ordinateur
2. BLe nombre de lignes de code
3. CL'espace disque du fichier du programme une fois compilé
4. DLa quantité de mémoire dont un algorithme a besoin lorsque la taille de l'entrée augmente

Quelle est la complexité temporelle de la recherche linéaire dans un tableau non trié de n éléments (pire cas) ?

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

Quel algorithme de tri échange de façon répétée les éléments adjacents qui sont dans le mauvais ordre ?

1. ATri fusion
2. BTri par tas
3. CTri rapide (quicksort)
4. DTri à bulles

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(n)
3. CO(2ⁿ)
4. DO(log 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 500,000
2. BEnviron 1,000
3. CEnviron 20
4. DEnviron 100

Comment l'algorithme de Prim construit-il un arbre couvrant de poids minimal ?

1. AIl supprime l'arête la plus chère jusqu'à ce qu'il ne reste plus de cycle
2. BIl trie toutes les arêtes par poids et ajoute chacune d'elles sauf si elle formait un cycle dans la forêt
3. CIl fait croître un seul arbre à partir d'un sommet de départ, en ajoutant l'arête la moins chère qui sort de l'arbre
4. DIl exécute un parcours en largeur et conserve l'arbre du BFS

Quel énoncé sur la notation petit o est correct ?

1. An = o(n), puisque toute fonction est un petit o d'elle-même
2. Bn = o(n²), mais n n'est pas o(n)
3. Cn² = o(n)
4. D2n = o(n), car 2n croît lentement

Le problème du sac à dos 0/1 résolu par programmation dynamique prend un temps O(nW). Pourquoi dit-on qu'il est pseudo-polynomial ?

1. AW est un nombre, donc le temps est exponentiel en le nombre de bits utilisés pour écrire W
2. BParce que n est toujours petit
3. CParce que l'algorithme est probabiliste et que son temps d'exécution varie à chaque entrée
4. DParce qu'il ne fonctionne que pour W = 0