QCM : Complexité des algorithmes (9 questions)

Questions et réponses du QCM

1. Une équipe chronomètre un programme sur des données réelles et relève sa consommation moyenne de mémoire, puis étudie théoriquement son nombre d’instructions et ses besoins en mémoire. Quelle distinction décrit ces deux démarches ?

La démarche empirique mesure notamment le temps et la mémoire moyenne, tandis que la démarche théorique étudie la complexité en instructions et en mémoire.
La démarche empirique étudie le nombre d’instructions et la mémoire théorique, tandis que la démarche théorique mesure le temps réel et la mémoire moyenne.
La démarche empirique étudie la complexité en instructions, tandis que la démarche théorique mesure le temps réel et l’usage moyen de mémoire.
La démarche empirique mesure le temps et le nombre d’instructions, tandis que la démarche théorique étudie la mémoire moyenne observée.

La démarche empirique mesure notamment le temps et la mémoire moyenne, tandis que la démarche théorique étudie la complexité en instructions et en mémoire.

Explication

L’analyse empirique observe notamment le temps de calcul et l’usage moyen de mémoire, alors que l’analyse théorique porte sur la complexité en instructions et en mémoire. Les autres réponses intervertissent ces approches ou attribuent à l’une d’elles des mesures qui relèvent de l’autre.

2. Pour un algorithme donné, une équipe compare les ressources consommées sur différentes entrées. Quel cas correspond à la valeur moyenne des ressources utilisées ?

La complexité moyenne.
L’analyse empirique.
La complexité au pire cas.
La complexité au meilleur cas.

La complexité moyenne.

Explication

La complexité moyenne correspond à la valeur moyenne des ressources utilisées sur les cas considérés. Le pire cas mesure leur maximum, le meilleur cas leur minimum, tandis que l’analyse empirique désigne une démarche de mesure des performances.

3. Un chercheur décrit comment les ressources nécessaires à un algorithme évoluent quand la taille des entrées augmente, sans se limiter à des mesures chronométrées. Que caractérise une analyse asymptotique exprimée en grand O ?

Le temps exact d’exécution pour une machine et une entrée données.
L’ordre de grandeur des ressources en fonction de la taille des entrées.
Le nombre exact d’instructions exécutées pour chaque entrée possible.
La quantité de mémoire disponible avant l’exécution de l’algorithme.

L’ordre de grandeur des ressources en fonction de la taille des entrées.

Explication

Les complexités asymptotiques décrivent l’ordre de grandeur des ressources en fonction de la taille des entrées, souvent à l’aide du grand O. Un temps chronométré est une mesure empirique, tandis que le grand O ne donne ni la mémoire disponible ni un décompte exact pour chaque entrée.

4. Que signifie calculer la complexité au pire cas d’un algorithme ?

Comparer le coût de chaque instruction à celui de l’algorithme optimal.
Mesurer le coût minimal obtenu sur une entrée particulièrement favorable.
Calculer la consommation moyenne de ressources sur l’ensemble des entrées.
Estimer la quantité maximale de ressources consommées sur les entrées possibles.

Estimer la quantité maximale de ressources consommées sur les entrées possibles.

Explication

La complexité au pire cas correspond au maximum de ressources utilisées, obtenu en considérant les entrées qui entraînent le coût le plus élevé. La consommation moyenne décrit plutôt la complexité moyenne, et non le pire cas.

5. Quelle relation de récurrence modélise le coût de la version récursive de Fibonacci pour les cas non terminaux ?

C(n)=C(n−1)+C(n−2)+O(1)
C(n)=C(n−1)+O(1)
C(n)=C(n−2)+O(n)
C(n)=2C(n−1)+O(1)

C(n)=C(n−1)+C(n−2)+O(1)

Explication

Chaque appel récursif de Fibonacci déclenche des calculs pour les deux termes précédents, auxquels s’ajoute un coût constant. La relation avec un seul appel sur n−1 décrit plutôt la récurrence de la factorielle récursive.

6. Quel rôle joue la boucle de la factorielle itérative dans le calcul du résultat ?

Diviser l’intervalle de recherche en deux parties égales
Réduire n de deux unités à chaque appel récursif
Parcourir les nombres afin de calculer leur moyenne
Multiplier successivement l’accumulateur par les entiers jusqu’à n

Multiplier successivement l’accumulateur par les entiers jusqu’à n

Explication

La boucle réalise au plus n itérations et construit la factorielle en multipliant successivement une variable accumulatrice. Le calcul d’une moyenne concerne un autre exemple d’algorithme et ne décrit pas la fonction de cette boucle.

7. En quoi la recherche dichotomique et le calcul de Fibonacci amélioré diffèrent-ils quant à la méthode de réduction du travail ?

La recherche dichotomique réduit le tableau d’un élément à chaque étape, tandis que Fibonacci amélioré examine successivement chaque valeur d’entrée.
La recherche dichotomique recalcule les termes précédents, tandis que Fibonacci amélioré compare une cible à la médiane d’un tableau trié.
La recherche dichotomique écarte une moitié du tableau à chaque étape, tandis que Fibonacci amélioré réduit le coût de calcul à O(n) ou O(log n).
La recherche dichotomique calcule les termes de Fibonacci, tandis que Fibonacci amélioré divise en deux un tableau trié.

La recherche dichotomique écarte une moitié du tableau à chaque étape, tandis que Fibonacci amélioré réduit le coût de calcul à O(n) ou O(log n).

Explication

La recherche dichotomique resserre l’intervalle de recherche en poursuivant dans une moitié du tableau, alors que l’amélioration de Fibonacci concerne la réduction de la complexité de son calcul. Le recalcul récursif des termes précédents caractérise plutôt la version récursive naïve de Fibonacci.

8. Pourquoi l’analyse empirique peut-elle donner des résultats différents d’une analyse théorique des performances d’un algorithme ?

Parce qu’elle compte les instructions abstraites, tandis que l’analyse théorique chronomètre des exécutions réelles.
Parce qu’elle évalue la mémoire utilisée, tandis que l’analyse théorique ignore les besoins en mémoire.
Parce qu’elle mesure l’exécution réelle, tandis que l’analyse théorique étudie les ressources en instructions et en mémoire.
Parce qu’elle mesure le pire cas, tandis que l’analyse théorique ne considère que le cas moyen.

Parce qu’elle mesure l’exécution réelle, tandis que l’analyse théorique étudie les ressources en instructions et en mémoire.

Explication

L’analyse empirique observe notamment les temps de calcul et l’usage moyen de la mémoire lors d’exécutions, alors que l’analyse théorique étudie la complexité en instructions et en mémoire. L’idée que l’analyse théorique ignore la mémoire est erronée, puisqu’elle examine aussi les ressources mémoire.

9. Lorsqu’on simplifie en grand O le coût O(1+n+n2)O(1+n+n^2) d’un algorithme, quelle complexité faut-il retenir ?

O(n)O(n), car le terme linéaire domine les termes constants
O(n2)O(n^2), car le terme dominant détermine l’ordre de grandeur
O(1)O(1), car les coûts constants sont supprimés en premier
O(n3)O(n^3), car les termes de l’expression doivent être multipliés

$$O(n^2)$$, car le terme dominant détermine l’ordre de grandeur

Explication

En grand O, on conserve le terme de croissance dominante et on écarte les termes moins importants, ce qui donne O(n2)O(n^2). Retenir O(n)O(n) négligerait le terme quadratique, qui croît plus rapidement.

Révisez avec les flashcards

Mémorisez les réponses avec 10 flashcards sur Complexité des algorithmes.

Que mesure notamment l’analyse empirique des performances algorithmiques ?

Les temps de calcul et l’usage moyen de la mémoire.

Que mesure la complexité au pire cas d’un algorithme ?

Le maximum de ressources utilisées.

Que mesure la complexité asymptotique en fonction de la taille des entrées ?

L’ordre de grandeur des ressources utilisées.

Voir les flashcards →

Approfondir avec la fiche

Consultez la fiche de révision complète sur Complexité des algorithmes.

Voir la fiche →

Cours similaires

Crée tes propres QCM

Importe ton cours et l'IA génère des QCM avec corrections en 30 secondes.

Générateur de QCM