Numérique et sciences informatiques (spécialité) · Première

Le coût d'un algorithme : cours de NSI en 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 maximale utilisée en même temps).
On l'exprime en fonction de la taille de l'instance, jamais d'une donnée précise : on retient le plus souvent le pire des cas, parfois le meilleur ou le cas moyen.
Un coût linéaire double quand la taille double ; la recherche dichotomique, en temps logarithmique, ajoute seulement une itération quand la taille double.
Si la longueur $l$ vérifie $l < 2^n$ , la dichotomie fait au plus $n$ itérations.
Un algorithme peu coûteux (glouton) ne garantit pas la solution optimale ; la programmation dynamique la garantit, au prix d'un coût plus élevé.

Pourquoi mesurer le coût d'un algorithme

Tu sais déjà écrire des algorithmes qui fonctionnent : trier un tableau, chercher une valeur, rendre la monnaie, classer une donnée avec ses voisins. Une question reste ouverte : combien coûte l'exécution ? Sur un tableau de dix cases, tous ces programmes semblent instantanés. Sur des millions de données, la différence entre deux méthodes peut faire passer le calcul de quelques instants à des heures.

Le programme de NSI le rappelle : de grands volumes de données sont traités par les ordinateurs, et il faut alors des algorithmes efficaces pour des opérations comme la sélection et la récupération des données ³. Pour dire qu'un algorithme est « efficace », il faut un moyen de le mesurer. Ce moyen, c'est le coût.

Dans ce cours, tu vas apprendre à :

distinguer le coût en temps et le coût en mémoire ;
compter des opérations élémentaires sans te perdre dans les détails ;
exprimer un coût en fonction de la taille des données ;
comparer deux algorithmes qui résolvent le même problème ;
comprendre pourquoi un algorithme peu coûteux n'est pas toujours le meilleur.

Le coût en temps : compter des opérations

Étudier le coût en temps d'un algorithme revient à dénombrer les opérations de base qu'il exécute ⁶. Une opération élémentaire est une instruction simple : une addition, une comparaison, une affectation, un test de condition.

Faut-il tout compter ? Non. Les opérations élémentaires n'ont pas toutes le même coût, et vouloir les recenser toutes est à la fois difficile et inutile. On choisit donc celles que l'on veut compter, de façon à obtenir un ordre de grandeur intéressant selon le contexte ⁶.

ExempleCompter dans une boucle simple

Voici une fonction qui calcule la somme des éléments d'un tableau t de $n$ éléments.

def somme(t):
    s = 0
    for x in t:
        s = s + x
    return s

Si l'on compte les additions, la boucle en fait exactement une par élément : $n$ additions. Si l'on comptait aussi les affectations, on en aurait $n + 1$ (une pour s = 0, une par tour de boucle). Les deux décomptes sont différents, mais ils grandissent de la même façon quand $n$ augmente : ils sont proportionnels à $n$ . C'est cette croissance qui nous intéresse.

ExempleDeux boucles imbriquées

Observons maintenant une fonction qui compte les paires d'éléments égaux dans un tableau.

def paires_egales(t):
    n = len(t)
    c = 0
    for i in range(n):
        for j in range(i + 1, n):
            if t[i] == t[j]:
                c = c + 1
    return c

On compte les comparaisons t[i] == t[j]. Pour $i = 0$ , la boucle intérieure en fait $n - 1$ ; pour $i = 1$ , elle en fait $n - 2$ ; et ainsi de suite jusqu'à $0$ pour le dernier indice. Le total vaut

$(n-1) + (n-2) + \dots + 1 + 0 = \frac{n(n-1)}{2}.$

Pour $n = 10$ , cela fait $45$ comparaisons. Pour $n = 20$ , on en trouve $190$ . Quand la taille double, le nombre de comparaisons est multiplié par un peu plus de $4$ : la croissance n'est plus proportionnelle à $n$ .

Taille de l'instance et cas étudiés

Un algorithme travaille sur une instance : une donnée précise, par exemple un tableau particulier. Le coût sur cette instance dépend de son contenu, pas seulement de sa taille. Prenons la recherche d'une valeur dans un tableau en le parcourant du début à la fin : si la valeur est en première case, une seule comparaison suffit ; si elle est absente, il faut les faire toutes.

Pourtant, on souhaite évaluer le coût en fonction de la taille de l'instance, et non en fonction des instances elles-mêmes ⁶. Comme plusieurs instances de même taille peuvent avoir des coûts différents, il faut se donner une règle de mesure. Le plus souvent, on retient le coût du cas le plus défavorable ; on peut toutefois préférer le cas le plus favorable, ou bien une moyenne ⁶.

ExempleLe tri par insertion selon les données

Reprenons le tri par insertion vu l'an dernier. À chaque étape, on insère l'élément courant dans la partie déjà triée en le comparant à ses prédécesseurs, jusqu'à trouver sa place.

Meilleur des cas : le tableau est déjà trié. Chaque élément n'est comparé qu'une seule fois (au précédent), soit $n - 1$ comparaisons.
Pire des cas : le tableau est trié à l'envers. Chaque élément doit être comparé à tous ceux qui le précèdent : $1 + 2 + \dots + (n-1) = \frac{n(n-1)}{2}$ comparaisons.

Pour $n = 1000$ , on passe de $999$ comparaisons à $499\,500$ . Le même algorithme, sur des tableaux de même taille, peut donc coûter $500$ fois plus cher.

Un exemple complet : chercher dans un tableau

Comparons deux façons de chercher une valeur x dans un tableau t de $l$ éléments. Nous allons compter les comparaisons t[i] == x ou t[m] == x dans le pire des cas.

MéthodeLa recherche séquentielle (naïve)

On parcourt le tableau case par case.

def recherche(t, x):
    for i in range(len(t)):
        if t[i] == x:
            return i
    return None

Dans le pire des cas (valeur absente ou en dernière case), on fait $l$ comparaisons. Le nombre de tours de boucle ne peut pas dépasser la taille de départ du tableau : c'est une complexité linéaire ³. Concrètement, le temps de recherche double quand la longueur de la liste double ³.

MéthodeLa recherche dichotomique

Elle suppose le tableau trié. Le mot vient du grec dikha (en deux) et tomos (couper) ³. À chaque tour, on regarde la case du milieu, ce qui permet d'éliminer la moitié des cases restantes.

def dicho(t, x):
    g, d = 0, len(t) - 1
    while g <= d:
        m = (g + d) // 2
        if t[m] == x:
            return m
        elif t[m] < x:
            g = m + 1
        else:
            d = m - 1
    return None

La recherche dichotomique permet de retrouver un élément dans un tableau trié en temps logarithmique ².

Voyons pourquoi, avec un raisonnement que tu peux refaire. Notons $l$ la longueur du tableau. Après un tour, il reste au plus la moitié des cases à examiner ; après deux tours, au plus un quart ; après $k$ tours, environ $l / 2^k$ . La recherche s'arrête au plus tard quand il ne reste plus rien à examiner. Le résultat à retenir, pour le code ci-dessus : si l'entier $n$ vérifie $l < 2^n$ , alors l'algorithme effectue au plus $n$ itérations ³.

Comparaison des itérations au pire
Taille l du tableau	Séquentielle (pire cas)	Dichotomie (au plus)
1 000	1 000	10
1 000 000	1 000 000	20
1 000 000 000	1 000 000 000	30

Comparaison des itérations au pire · Valeurs calculées avec la propriété : si l < 2^n, au plus n itérations.

Comment le coût grandit : les ordres de grandeur

Compter exactement $\frac{n(n-1)}{2}$ comparaisons est précis, mais ce qui compte pour comparer deux algorithmes, c'est la manière dont le coût croît quand $n$ grandit. Pour cela, on observe ce qui se passe quand on double la taille des données.

Effet du doublement de la taille
Type de coût	Exemple	Quand la taille double
Logarithmique	Recherche dichotomique	Une itération de plus
Linéaire	Recherche séquentielle	Le coût double
Quadratique	Paires comparées : n(n-1)/2	Le coût est multiplié par environ 4

Effet du doublement de la taille · Exemples calculés dans le cours.

Dans les sujets du concours général, on demande souvent de donner le coût en temps et en mémoire d'un algorithme, avec un simple ordre de grandeur : on regarde par exemple le nombre d'entiers stockés pour la mémoire, et l'ordre de grandeur du nombre d'opérations pour le temps, sans chercher la valeur exacte ⁵. Cette approche est exactement celle de ce cours.

Le coût en mémoire

Le temps n'est pas la seule ressource. Un programme occupe aussi de la mémoire : variables, tableaux, listes créés au cours de l'exécution. Le coût spatial d'une exécution est la quantité maximale de mémoire utilisée simultanément par l'algorithme au cours de son exécution ⁶.

Le mot « simultanément » est important. Si ton programme crée un grand tableau puis le libère avant d'en créer un autre, il ne faut pas additionner les deux tailles : on retient le maximum présent en même temps. Dans les exercices de concours général, on se contente d'un ordre de grandeur du nombre d'entiers stockés ⁵.

ExempleDeux façons de calculer les carrés

def carres_liste(n):
    res = []
    for i in range(n):
        res.append(i * i)
    return res

def somme_carres(n):
    s = 0
    for i in range(n):
        s = s + i * i
    return s

Les deux fonctions font $n$ multiplications : même coût en temps. Mais carres_liste stocke $n$ entiers en mémoire, alors que somme_carres n'en garde que quelques-uns (s, i). Le coût en mémoire est donc très différent : de l'ordre de $n$ pour la première, constant pour la seconde.

Coût faible ou solution optimale ? Le rendu de monnaie

Un algorithme peu coûteux est-il pour autant le meilleur ? Pas forcément, car certains problèmes demandent une solution optimale, et un algorithme rapide peut se contenter d'une solution seulement correcte. Le rendu de monnaie en donne un exemple frappant.

Le problème : payer une somme avec le moins de pièces possible. Une réponse est dite optimale quand elle emploie le plus petit nombre de pièces possible ⁴. L'algorithme glouton, vu en classe de Première, consiste à payer d'abord avec la plus grosse pièce possible ⁴. Avec le système euro, on peut démontrer que cet algorithme donne toujours la réponse optimale ⁴.

Pour garantir l'optimalité, on utilise la programmation dynamique : on calcule le nombre minimal de pièces pour toutes les petites sommes, en mémorisant les résultats pour ne pas les recalculer. Avec les pièces de l'euro, l'appel de la version avec mémoïsation sur la somme $48$ répond immédiatement $5$ , et confirme que le glouton avait bien trouvé l'optimum dans ce cas ⁴.

Quel prix paye-t-on ? La version dynamique est de coût tout à fait raisonnable : elle utilise deux boucles imbriquées, ce qui donne un temps d'exécution qui grandit comme le produit des deux tailles en jeu ⁴. Elle utilise aussi de la mémoire pour stocker les résultats intermédiaires. À l'inverse, les algorithmes gloutons sont souvent moins coûteux à l'exécution, mais ils ne peuvent pas garantir une solution optimale ⁴.

Méthode : évaluer le coût d'un algorithme

Voici une démarche qui fonctionne pour la plupart des questions de cours et d'exercices.

ChoisirDécider quelle opération on compte (comparaisons, additions).
Définir la tailleNommer n : le nombre d'éléments de la donnée.
Choisir le casPire des cas, sauf indication contraire.
CompterDénombrer les opérations selon les boucles.
ConclureDire comment le coût grandit quand n double.

Évaluer le coût d'un algorithme

ExempleApplication à la recherche du maximum

def maximum(t):
    m = t[0]
    for x in t:
        if x > m:
            m = x
    return m

Ce qu'on compte : les comparaisons x > m.
Taille : $n$ = nombre d'éléments de t.
Compte : la boucle parcourt tout le tableau, donc exactement $n$ comparaisons, quel que soit le contenu. Meilleur et pire des cas coïncident.
Conclusion : coût en temps linéaire (il double si $n$ double).
Mémoire : deux variables, m et x, en plus du tableau : coût en espace constant.

Exercices corrigés

Exercice 1 Compter des comparaisons dans deux boucles imbriquées

★☆☆Environ 10 min

On considère la fonction suivante, appelée avec un tableau t de $10$ éléments.

def doublons(t):
    n = len(t)
    for i in range(n):
        for j in range(i + 1, n):
            if t[i] == t[j]:
                return True
    return False

On compte les comparaisons t[i] == t[j].

Dans quel cas la fonction fait-elle le plus de comparaisons ?
Combien de comparaisons fait-elle dans ce cas pour $n = 10$ ?
Que devient ce nombre si l'on double la taille du tableau ?

Indice 1

Pour $i = 0$ , combien de valeurs de $j$ y a-t-il ? Et pour $i = 1$ ?

Indice 2

Additionne $9 + 8 + \dots + 1 + 0$ , ou utilise la formule $\frac{n(n-1)}{2}$ .

Voir la correction pas à pas

Le pire des cas : la fonction ne s'arrête que si elle trouve deux éléments égaux. Si tous les éléments sont distincts, elle parcourt toutes les paires sans jamais rendre True.
Pour $i = 0$ , $j$ prend $9$ valeurs ; pour $i = 1$ , $8$ valeurs ; ... ; pour $i = 9$ , aucune. Le total est $9 + 8 + \dots + 1 = 45$ , ce qui est bien $\frac{10 \times 9}{2}$ .
Pour $n = 20$ , on obtient $\frac{20 \times 19}{2} = 190$ . Le nombre est multiplié par un peu plus de $4$ : le coût est quadratique, il ne double pas.

Dans le pire des cas (éléments tous distincts), la fonction fait $\frac{n(n-1)}{2}$ comparaisons, soit $45$ pour $n = 10$ . Doubler la taille multiplie ce nombre par environ $4$ .

Exercice 2 Itérations d'une recherche dichotomique

★★☆Environ 10 min

Un annuaire trié contient $l = 1\,000\,000$ numéros. On y cherche un numéro par recherche dichotomique.

Rappelle la propriété qui lie $l$ et le nombre maximal d'itérations $n$ .
Détermine le plus petit entier $n$ qui convient.
Si l'annuaire contenait deux fois plus de numéros, combien d'itérations au plus faudrait-il ? Compare avec la recherche séquentielle.

Indice 1

Tu cherches le plus petit $n$ tel que $2^n > 1\,000\,000$ .

Indice 2

Retiens que $2^{10} = 1024$ et calcule $2^{20}$ .

Voir la correction pas à pas

Si $l < 2^n$ , la dichotomie effectue au plus $n$ itérations.
On sait que $2^{10} = 1024$ , donc $2^{20} = 1\,048\,576 > 10^6$ . Comme $2^{19} = 524\,288 < 10^6$ , le plus petit entier qui convient est $n = 20$ .
Avec $2 \times 10^6$ numéros : $2\,000\,000 < 2^{21} = 2\,097\,152$ . Il faut donc $21$ itérations au plus, soit une seule de plus.
La recherche séquentielle passerait, elle, de $1\,000\,000$ comparaisons à $2\,000\,000$ au pire.

La dichotomie fait au plus $20$ itérations sur $10^6$ numéros, et seulement $21$ si l'on double la taille. Un coût logarithmique grandit très lentement comparé à un coût linéaire.

Exercice 3 Glouton ou optimal ?

★★★Environ 15 min

Un distributeur utilise des pièces de valeurs $30, 24, 12, 6, 3, 1$ . Il doit rendre $48$ .

Applique l'algorithme glouton et donne le nombre de pièces rendues.
Trouve une solution qui utilise moins de pièces.
De combien de pièces la solution optimale améliore-t-elle le glouton ?
Pourquoi ce résultat montre-t-il qu'un algorithme de faible coût peut ne pas suffire ?

Indice 1

Le glouton prend toujours la plus grande pièce qui ne dépasse pas la somme restante.

Indice 2

Observe que $48$ est un multiple d'une des valeurs de pièce.

Voir la correction pas à pas

Glouton : la plus grande pièce $\leq 48$ est $30$ , il reste $18$ . La plus grande pièce $\leq 18$ est $12$ , il reste $6$ . Puis $6$ : il reste $0$ . Total : $30 + 12 + 6$ , soit $3$ pièces.
Solution meilleure : $24 + 24 = 48$ , soit $2$ pièces. On ne peut pas faire avec une seule pièce, car aucune pièce ne vaut $48$ .
Le gain est de $3 - 2 = 1$ pièce.
Le glouton est peu coûteux, mais il choisit sans jamais revenir en arrière : prendre $30$ l'empêche de trouver $24 + 24$ . Pour garantir le minimum, il faut un algorithme de programmation dynamique, plus coûteux en temps et en mémoire.

Le glouton rend $3$ pièces, alors que l'optimum en demande $2$ . Le faible coût d'un algorithme ne garantit pas une solution optimale.

Les questions qu'on se pose

Pourquoi ne mesure-t-on pas simplement le temps en secondes ?

Le temps en secondes dépend de l'ordinateur, du langage et des programmes qui tournent en même temps. Deux élèves obtiendraient des résultats différents pour le même algorithme. Compter des opérations élémentaires donne un résultat qui dépend seulement de l'algorithme et de la taille des données, donc comparable partout.

Faut-il compter toutes les instructions d'un programme ?

Non. Les opérations élémentaires n'ont pas toutes le même coût, et les recenser toutes est à la fois difficile et inutile ; on sélectionne celles qui donnent un ordre de grandeur intéressant ⁶. En pratique, on compte l'opération qui se répète le plus, souvent une comparaison dans la boucle la plus intérieure. Annonce toujours ce que tu comptes.

Pourquoi étudie-t-on surtout le pire des cas ?

Parce qu'il donne une garantie : quelle que soit l'instance de taille $n$ , le coût ne dépassera pas cette valeur. C'est le choix le plus courant, même si l'on peut aussi étudier le meilleur des cas ou le coût moyen ⁶. Le meilleur des cas est trop optimiste pour juger un algorithme.

Pourquoi la dichotomie est-elle bien plus rapide que la recherche séquentielle ?

Parce qu'à chaque tour elle écarte la moitié des cases restantes, alors que la recherche séquentielle n'en écarte qu'une. Son coût est logarithmique ² : si $l < 2^n$ , elle fait au plus $n$ itérations ³. Sur un million de cases, cela fait au plus $20$ itérations contre un million de comparaisons au pire pour la recherche séquentielle. Attention : il faut que le tableau soit trié.

Un algorithme glouton est-il toujours à éviter puisqu'il n'est pas toujours optimal ?

Non. Les algorithmes gloutons sont souvent moins coûteux à l'exécution, mais sans garantie d'optimalité ⁴. Pour certains problèmes, comme le rendu de monnaie avec les pièces de l'euro, on peut démontrer qu'il donne toujours l'optimum ⁴. Le choix dépend de ce qu'on exige : une réponse rapide et correcte, ou la meilleure réponse à coup sûr.

Que demande-t-on sur le coût aux évaluations de NSI ?

On demande typiquement de donner le coût en temps et en mémoire d'un algorithme, en ordre de grandeur, et parfois de concevoir un algorithme dont le coût ne dépasse pas une limite imposée, en expliquant son idée en français ⁵. Prépare-toi à justifier : ce que tu comptes, la taille choisie, le cas étudié.

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.

Signaler une erreur sur cette page

Le coût d'un algorithme : cours de NSI en Première

L'essentiel

Pourquoi mesurer le coût d'un algorithme

Le coût en temps : compter des opérations

Taille de l'instance et cas étudiés

Un exemple complet : chercher dans un tableau

Comment le coût grandit : les ordres de grandeur

Le coût en mémoire

Coût faible ou solution optimale ? Le rendu de monnaie

Méthode : évaluer le coût d'un algorithme

Exercices corrigés

Exercice 1 Compter des comparaisons dans deux boucles imbriquées

Exercice 2 Itérations d'une recherche dichotomique

Exercice 3 Glouton ou optimal ?

Quiz

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur