Questions à choix multiples gratuites sur Algorithmes et complexité, avec indices et explications, à trois niveaux : termes et faits clés, appliquer les notions, cas et analyse.
Quelle classe de complexité croît le plus vite pour de grandes valeurs de n ?
Bien joué. Envie du suivant ?Prêt pour le suivant ? 5 nouveaux exercices chaque jour, dans tous les thèmes.
Un algorithme est une liste finie d’étapes précises qui résout un problème, comme trier une liste ou trouver un nom dans un annuaire.
Deux algorithmes peuvent résoudre le même problème mais prendre des temps très différents. La complexité décrit comment le travail croît quand l’entrée grandit.
La taille de l’entrée se note n : le nombre d’éléments à trier, la longueur d’une liste, le nombre de nœuds d’un graphe.
Imaginez que vous cherchez un nom dans un annuaire de 1000 pages. Lire chaque page demande jusqu’à 1000 étapes. L’ouvrir au milieu et diviser par deux à chaque fois demande environ 10 étapes.
La complexité en temps compte les étapes. La complexité en espace compte la mémoire supplémentaire. Toutes deux s’écrivent comme une fonction de n.
En général, on regarde le pire cas : le plus de travail sur toutes les entrées de taille n. Parfois, c’est le cas moyen ou le meilleur cas qui est demandé.
Réponse: 4 secondes. Doubler n multiplie n² par 2² = 4, donc le temps passe d’environ 1 à environ 4 secondes. 2 secondes serait la réponse pour une croissance linéaire, et 8 pour n³.
La notation grand O ne garde que ce qui compte pour de grands n. Vous supprimez les facteurs constants et ne gardez que le terme qui croît le plus vite.
Pour n = 1000, le terme en n² vaut 3 000 000, alors que 5n n’est que 5000. Les termes plus petits changent à peine le total.
Ces classes reviennent sans cesse, de la croissance la plus lente à la plus rapide :
Le grand O est une borne supérieure : le travail croît au plus à cette vitesse. Ω (grand Oméga) est une borne inférieure, et Θ (Thêta) est une borne serrée, à la fois supérieure et inférieure.
La base d’un logarithme n’a pas d’importance en grand O, car des logarithmes de bases différentes ne diffèrent que d’un facteur constant.
Réponse: O(n²). Pour de grands n, le terme en n² domine, et le facteur constant 2 est supprimé. O(n) garde le mauvais terme, et O(2n²) oublie de supprimer la constante.
Quelques algorithmes reviennent dans presque tous les cours. Apprenez leurs complexités comme des faits.
Une fonction récursive s’appelle elle-même sur une entrée plus petite jusqu’à atteindre un cas de base auquel elle répond directement. Son temps d’exécution s’écrit sous forme de récurrence :
Trois idées de conception méritent d’être connues. Diviser pour régner découpe, résout et combine. Le glouton prend à chaque étape le meilleur choix local. La programmation dynamique mémorise les réponses aux sous-problèmes qui se recoupent pour qu’elles soient calculées une seule fois.
Réponse: O(n²). Avec de mauvais pivots, chaque découpage laisse n − 1 éléments d’un côté, ce qui donne O(n²). O(n log n) est son cas moyen, et le pire cas du tri fusion.
Pour trouver la complexité en temps d’un morceau de code :
Pour une question de théorie, nommez d’abord l’algorithme ou l’idée décrits, puis rappelez sa complexité et ses conditions (entrée triée, poids positifs, sous-problèmes qui se recoupent).
Suivez chaque étape. Essayez de deviner la suivante avant de l’ouvrir.
Quelle est la complexité en temps de ce code ? for i = 1 to n: (j = 1; while j < n: j = j × 2)
n est le nombre jusqu’auquel les boucles s’exécutent.
i va de 1 à n par pas de 1, donc la boucle extérieure s’exécute n fois.
j prend les valeurs 1, 2, 4, 8, … et s’arrête quand il atteint n. Après k tours, j = 2k, donc la boucle s’arrête après environ log₂ n tours.
La boucle intérieure est à l’intérieur de la boucle extérieure, donc les nombres se multiplient.
Pour n = 1024, la boucle intérieure s’exécute log₂ 1024 = 10 fois, donc le corps s’exécute 1024 · 10 = 10 240 fois. C’est bien moins que n² = 1 048 576.
O(n log n)
Réponse: O(n). Les boucles qui se suivent s’additionnent : n + n = 2n, et la constante est supprimée, donc O(n). O(n²) ne serait juste que si une boucle était à l’intérieur de l’autre.
P contient les problèmes qui peuvent être résolus en temps polynomial. NP contient les problèmes dont les solutions peuvent être vérifiées en temps polynomial. Tout problème de P est dans NP ; on ne sait toujours pas si P = NP.
Apprenez pas à pas dans l’applicationApprenez pas à pas dans l’application
Quelle notation décrit une borne supérieure de la croissance ?
O donne une borne supérieure, Ω une borne inférieure et Θ une borne exacte (asymptotiquement serrée).
Dans un tableau trié, vous cherchez deux éléments dont la somme vaut une cible en déplaçant un pointeur depuis chaque extrémité vers l'intérieur. Quelle est la complexité temporelle ?
Si la somme est trop petite, le pointeur gauche avance vers la droite ; si elle est trop grande, le pointeur droit recule vers la gauche : il y a donc au plus n étapes.
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 ?
Avec a = 7 et b = 2, nlog₂ 7 domine le travail d'addition en O(n²), ce qui donne environ n2,81.
Un algorithme est une liste finie d’étapes précises qui résout un problème, comme trier une liste ou trouver un nom dans un annuaire.
Deux algorithmes peuvent résoudre le même problème mais prendre des temps très différents. La complexité décrit comment le travail croît quand l’entrée grandit.
Chaque question propose quatre réponses, et une seule est juste. Bloqué ? Ouvrez d’abord un petit indice, et l’explication complète seulement si vous en avez besoin.