Coût d'un algorithme : exercices corrigés de Première NSI

On choisit l'opération à compter : ici, la comparaison x > m, comme l'énoncé le précise. ⁶

On repère la taille de l'entrée : le tableau contient 250 éléments.

On regarde la boucle : elle fait un passage par élément, donc 250 passages.

À chaque passage, il y a exactement une comparaison, que le test soit vrai ou faux : on obtient 250 comparaisons.

On répond à la seconde question : le nombre de comparaisons ne dépend pas du contenu du tableau, seulement de sa longueur. Les affectations m = x, elles, dépendent du contenu, mais on ne les compte pas ici.

On identifie le type de coût : linéaire, donc le temps est proportionnel à la longueur. ³

On calcule le rapport des tailles : 4 000 divisé par 1 000 donne 4.

On applique le même rapport au temps : 3 ms multipliées par 4 donnent 12 ms.

On vérifie la cohérence : 2 000 éléments donneraient 6 ms (double), et 4 000 éléments le double de 6 ms, soit 12 ms.

On écrit la condition à satisfaire : $1\,000\,000 \le 2^n$. ³

On encadre : $2^{10} = 1\,024$, donc $2^{20} = 1\,024^2 = 1\,048\,576$.

On compare : $2^{19} = 524\,288$ est inférieur à 1 000 000, donc 19 ne convient pas ; $2^{20} = 1\,048\,576$ est supérieur, donc 20 convient.

On conclut : le plus petit n est 20, donc au plus 20 itérations.

On compare avec la recherche séquentielle : dans le pire des cas, il faut parcourir tout le tableau, soit 1 000 000 de comparaisons, contre 20 itérations pour la dichotomie.

On repère les deux boucles : i prend les valeurs de 0 à 39, et pour chaque i, j prend les valeurs de 0 à i − 1, soit i passages.

On écrit le total : $0 + 1 + 2 + \dots + 39$.

On applique la formule de la somme des entiers de 1 à 39 : $\frac{39 \times 40}{2} = 780$. Le terme 0 n'ajoute rien.

On refait le calcul pour 80 éléments : $0 + 1 + \dots + 79 = \frac{79 \times 80}{2} = 3\,160$.

On compare : 3 160 divisé par 780 vaut un peu plus de 4. Le coût a été multiplié par environ 4 quand la taille a doublé : il n'est pas linéaire.

On compte les pièces du glouton : 30 + 12 + 6 donne trois pièces. ⁴

On cherche mieux : 48 = 24 × 2, soit 24 + 24, deux pièces.

On vérifie qu'on ne peut pas faire avec une seule pièce : la plus grande pièce vaut 30, qui est inférieur à 48, donc une seule pièce ne suffit pas. Le minimum est donc 2.

On calcule la différence : 3 − 2 = 1 pièce de moins.

On rappelle les trois mesures possibles : cas le plus défavorable, cas le plus favorable, coût moyen. ⁶

Cas le plus favorable : la valeur est en première position, donc 1 comparaison.

Cas le plus défavorable : la valeur est en dernière position, donc 200 comparaisons.

Pour la moyenne, si la valeur est en position k, il faut k comparaisons. Chaque position a la probabilité $\frac{1}{200}$.

On calcule la somme : $1 + 2 + \dots + 200 = \frac{200 \times 201}{2} = 20\,100$.

On divise : $\frac{20\,100}{200} = 100{,}5$ comparaisons en moyenne.

On choisit l'opération comptée : la multiplication x * x. ⁶

Dans somme_a, la multiplication est faite une fois par élément dans la première boucle : n multiplications. Dans somme_b, elle est faite une fois par élément : n multiplications également. Le coût en temps est du même ordre.

On examine la mémoire. Le coût spatial est la quantité maximale de mémoire utilisée en même temps. ⁶ somme_a stocke n valeurs dans carres, donc mémoire supplémentaire proportionnelle à n.

somme_b ne conserve que la variable total (et la variable de boucle) : mémoire supplémentaire constante, quelle que soit la taille de la liste.

On conclut : à coût en temps comparable, somme_b est préférable car elle utilise beaucoup moins de mémoire. somme_a ne se justifierait que si l'on avait besoin de réutiliser la liste des carrés.