Numérique et sciences informatiques (spécialité) · Première
Coût d'un algorithme : quiz de Première NSI
Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur
L'essentiel
- Le coût en temps se mesure en comptant des opérations élémentaires ; le coût en espace est la quantité maximale de mémoire utilisée en même temps 6.
- On exprime le coût en fonction de la taille de l'entrée, le plus souvent dans le pire des cas, parfois dans le meilleur ou en moyenne 6.
- Un algorithme linéaire voit son temps doubler quand la liste double ; la dichotomie sur un tableau trié est logarithmique 32.
- Un algorithme glouton coûte peu mais ne garantit pas toujours la solution optimale 4.
Avant de commencer
Ce quiz porte sur la notion de coût d'un algorithme, vue en Première NSI après les tris, la recherche dichotomique, les algorithmes gloutons et les k plus proches voisins. Il couvre :
- ce que l'on compte quand on analyse un algorithme : des opérations élémentaires pour le temps, de la mémoire pour l'espace 6 ;
- les trois façons de résumer le coût en fonction de la taille de l'entrée : pire cas, meilleur cas, cas moyen 6 ;
- la comparaison entre une recherche linéaire et une recherche dichotomique 3 ;
- le lien entre coût d'exécution et qualité de la solution, avec l'exemple des algorithmes gloutons 4.
Quiz
13 questions · correction immédiate · ton score reste sur ton appareil.
-
Analyser la complexité temporelle, c'est compter les opérations élémentaires effectuées 6. Mesurer des secondes dépend de la machine et du langage, ce n'est donc pas une mesure de l'algorithme lui-même. Le nombre de lignes ne dit rien sur le nombre d'opérations réalisées (une boucle de trois lignes peut s'exécuter un million de fois). La mémoire maximale correspond, elle, au coût spatial 6.
-
Le coût spatial est la quantité maximale de mémoire utilisée simultanément au cours de l'exécution 6. Compter les opérations relève du coût en temps. Le nombre de variables du code n'est pas la bonne mesure : ce qui compte est la mémoire réellement occupée au même moment, par exemple la taille d'un tableau créé pendant le calcul.
-
C'est faux. Le coût peut dépendre de l'instance d'entrée, qui n'est pas fixée par la taille seule 6. C'est pour cela qu'on définit plusieurs fonctions de coût en fonction de la taille : cas le plus défavorable, cas le plus favorable, cas moyen 6. Chercher un élément dans une liste ne demande pas le même travail selon qu'il se trouve en première position ou n'y est pas du tout.
-
C'est le pire des cas qui sert le plus souvent de référence 6. Il donne une garantie : l'algorithme ne fera jamais pire. Le meilleur cas est aussi une mesure possible 6, mais il est trop optimiste pour garantir quoi que ce soit. Un tirage unique ou les seules données de l'énoncé ne constituent pas une mesure en fonction de la taille.
-
On peut choisir le coût dans le cas le plus défavorable, dans le cas le plus favorable ou encore le coût moyen 6. Le « cas le plus esthétique » n'existe pas : une mesure de coût doit être définie par un critère précis et reproductible.
-
C'est faux. Les opérations élémentaires (arithmétiques, booléennes, affectations, branchements) n'ont pas toutes le même coût, et les compter toutes est à la fois difficile et inutile 6. On sélectionne les opérations que l'on veut compter pour obtenir un ordre de grandeur adapté au contexte 6. Par exemple, pour un tri, on peut ne compter que les comparaisons.
-
Avec une complexité linéaire, doubler la longueur de la liste revient à doubler la durée de la recherche 3. Le temps ne reste pas constant : il faut examiner deux fois plus de cases dans le pire cas. L'ajout d'une seule opération serait le comportement d'une complexité logarithmique, pas linéaire. Le facteur quatre correspondrait à une complexité quadratique, comme celle d'une double boucle imbriquée sur toute la liste.
-
Complexité linéaire : le temps est proportionnel à la taille 3. La taille est multipliée par 4, donc le temps aussi : ms. Répondre 9 revient à multiplier par 3 au lieu de 4 : on a compté les 3 000 éléments ajoutés au lieu de la taille totale, qui vaut quatre fois 1 000.
-
La recherche dichotomique permet de chercher un élément dans un tableau trié en temps logarithmique 2. Elle traite efficacement des données représentées dans un tableau de façon ordonnée 3. Sans tri préalable, couper en deux n'aurait aucun sens, puisqu'on ne saurait pas dans quelle moitié continuer. La complexité linéaire est celle de l'algorithme naïf 3.
-
On cherche le plus petit tel que . Comme et , on obtient . La réponse 9 est tentante car s'approche de 1 000 par défaut, mais 512 est inférieur à 1 000 : la condition n'est pas satisfaite. La réponse 500 viendrait de la confusion avec une division par deux unique.
-
Le glouton paie d'abord avec la plus grosse pièce possible 4 et donne ici trois pièces. Pourtant n'en utilise que deux. Une réponse est optimale quand elle emploie le moins de pièces possible, et le glouton ne réussit pas à la trouver en général 4. Commencer par la plus grosse pièce n'est donc pas une preuve d'optimalité. Le glouton sait bien traiter ce système de pièces : il fournit une réponse, simplement pas la meilleure.
-
C'est faux. Pour le système euro, on peut démontrer que le glouton donne toujours la réponse optimale, mais ce n'est pas le cas pour tous les systèmes 4. Les algorithmes gloutons sont souvent moins coûteux en exécution, sans pouvoir garantir une solution optimale 4. Confondre « rapide » et « toujours optimal » est l'erreur classique.
-
Ce programme de programmation dynamique renvoie le nombre minimal de pièces ; la source précise que le glouton avait bien trouvé la réponse optimale dans ce cas 4. Le 5 n'est donc pas un coût d'exécution (ni un nombre d'opérations, ni des secondes) mais la valeur du problème posé : un nombre de pièces. Ne confonds pas le coût de l'algorithme avec le résultat qu'il calcule.
Les questions qu'on se pose
Pourquoi ne mesure-t-on pas simplement le temps d'un algorithme avec un chronomètre ?
Un chronomètre donne un temps qui dépend de la machine, du langage et des données testées. Analyser la complexité revient à compter des opérations élémentaires 6, ce qui donne un ordre de grandeur indépendant de l'ordinateur et exprimé en fonction de la taille de l'entrée 6. Le chronomètre reste utile pour vérifier, mais il ne remplace pas l'analyse.
Faut-il toujours choisir l'algorithme au coût le plus faible ?
Pas toujours. Un algorithme peu coûteux peut ne pas garantir la meilleure solution : c'est le cas du glouton pour le rendu de monnaie avec certains systèmes de pièces 4. Il faut comparer le coût et la qualité de la réponse attendue. Quand une solution optimale est exigée, il existe des méthodes plus coûteuses mais garanties, comme la programmation dynamique que tu verras en Terminale 4.
À l'examen, quel coût dois-je donner : en temps ou en mémoire ?
Lis l'énoncé : certains sujets, comme ceux du concours général, demandent à la fois le coût en temps et le coût en mémoire 5. Pour la mémoire, on considère simplement l'ordre de grandeur du nombre d'entiers stockés, et pour le temps l'ordre de grandeur du nombre d'opérations 5. Précise toujours dans quel cas tu te places (en général le pire cas 6) et ce que tu comptes.
Sources
- Ressources d'accompagnement NSI Première - Page centrale, Éduscol. Consulté le 6 novembre 2026.
- Diviser pour régner - Document d'accompagnement, Éduscol. Consulté le 6 novembre 2026.
- Recherche dichotomique - Analyse de complexité, Éduscol. Consulté le 6 novembre 2026.
- Programmation dynamique - Étude de coût, Éduscol. Consulté le 6 novembre 2026.
- Sujets zéro du concours général NSI - Exemples d'algorithmes, Éduscol. Consulté le 6 novembre 2026.
- Analyse de la complexité des algorithmes, Wikipédia. Consulté le 6 novembre 2026.
Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.