Numérique et sciences informatiques (spécialité) · Première
Coût d'un algorithme : fiche de révision NSI Première
Publié le 6 novembre 2026 · Mis à jour le 6 novembre 2026 · Signaler une erreur
L'essentiel
- Le coût d'un algorithme se mesure en temps (nombre d'opérations élémentaires comptées) ou en espace (mémoire utilisée).
- On l'exprime en fonction de la taille de l'entrée, pas d'une entrée particulière : cas le plus défavorable, le plus favorable ou moyen.
- Le pire des cas est la mesure la plus utilisée.
- Un parcours complet est linéaire : le temps double quand la taille double. La recherche dichotomique est logarithmique.
- Un algorithme glouton coûte peu mais ne garantit pas toujours la solution optimale.
Ce que l'on mesure
Quand tu as deux programmes qui résolvent le même problème, comment savoir lequel est le meilleur ? Chronométrer ne suffit pas : le résultat dépend de l'ordinateur. On préfère compter ce que l'algorithme fait. C'est l'étude de son coût, aussi appelé complexité.
Du coût d'une exécution au coût en fonction de la taille
Le coût peut varier d'une entrée à l'autre, même pour une taille identique. Ce qui nous intéresse est donc le coût en fonction de la taille de l'entrée, par exemple la longueur du tableau 6.
Complexité linéaire et logarithmique
Coût et qualité de la solution
Un algorithme peu coûteux n'est pas toujours le meilleur : il peut ne pas donner la meilleure solution. Les algorithmes gloutons sont souvent moins coûteux en exécution, mais sans garantie de solution optimale 4.
Pièges et méthode
Questions flash
4 questions · correction immédiate · ton score reste sur ton appareil.
-
Le coût spatial est la mémoire maximale utilisée en même temps. Le nombre d'opérations correspond au coût en temps, et un chronomètre dépend de la machine, donc ne mesure pas le coût de l'algorithme.
-
Le pire des cas est la mesure la plus courante car il donne une garantie. Le cas favorable est trompeur : un exemple chanceux ne dit rien de général.
-
C'est la définition de la complexité linéaire. Ce n'est pas le cas de la dichotomie, dont le coût n'augmente que d'une étape quand la taille double.
-
Faux : avec les pièces 30, 24, 12, 6, 3, 1, le glouton paie 48 en 3 pièces alors que 24 + 24 en demande 2. Il n'est garanti optimal que pour certains systèmes, comme l'euro.
Les questions qu'on se pose
Pourquoi ne pas simplement chronométrer le programme ?
Le temps mesuré dépend de l'ordinateur et de la machine utilisée. Compter les opérations élémentaires donne une mesure indépendante de la machine, qui permet de comparer deux algorithmes 6.
Faut-il compter toutes les opérations ?
Non. Elles n'ont pas toutes le même coût, et les compter toutes est difficile et inutile. On choisit celles qui comptent dans le contexte, par exemple les comparaisons 6.
Pourquoi la dichotomie demande-t-elle un tableau trié ?
Parce qu'elle décide de garder une moitié du tableau en comparant avec l'élément du milieu. Cela n'a de sens que si les données sont ordonnées 3.
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.