Comprendre le coût d’un algorithme

Définir ce que l’on mesure

La taille n d’une entrée dépend du problème : nombre de valeurs d’un tableau, longueur d’un texte ou nombre de sommets d’un graphe. Elle n’est pas forcément la valeur d’un nombre contenu dans le tableau. On choisit ensuite une opération pertinente, comme une comparaison entre valeurs ou une addition.

Ce modèle de coût simplifie la machine réelle. Il rend les comparaisons possibles à condition de conserver les mêmes conventions. Compter les comparaisons d’un programme et les secondes d’un autre ne permet pas une conclusion directe. On précise aussi les hypothèses, par exemple l’accès direct à une case d’un tableau.

Le résultat d’un comptage dépend du code retenu. Une somme initialisée à zéro puis alimentée par toutes les cases réalise n additions. Une autre réalisation, initialisée à la première case puis parcourant les suivantes, en réalise n-1 mais exige un tableau non vide. Les deux coûts sont linéaires : l’ordre de croissance n’efface pas cette différence lorsque la question demande un compte exact.

Reconnaître un parcours linéaire

Calculer une somme examine chacune des n valeurs et réalise n additions dans la version avec accumulateur initialisé à zéro. Doubler n double ce compteur. On parle d’un coût linéaire. Des instructions supplémentaires avant et après la boucle n’en changent pas l’ordre de croissance.

Deux boucles successives de n étapes effectuent environ 2n étapes : leur coût reste linéaire. Le nombre de boucles écrites ne suffit donc pas à identifier une croissance quadratique. Il faut regarder combien de fois chaque opération est réellement exécutée et comment les parcours se combinent.

s = 0
for valeur in t:
    s += valeur
compteur = 0
for valeur in t:
    if valeur > 0:
        compteur += 1

Comprendre les combinaisons quadratiques

Si, pour chacune des n valeurs, on parcourt de nouveau les n valeurs, le nombre de couples examinés vaut n². Dans un tri par sélection, la zone restante diminue : le nombre de comparaisons vaut (n - 1) + (n - 2) + … + 1 = n(n - 1)/2. Cette expression a aussi une croissance quadratique.

Pour de grandes tailles, doubler n multiplie approximativement ce dernier compteur par quatre. Le coefficient et les termes secondaires comptent pour un nombre exact d’opérations, mais la croissance dominante explique ce qui devient coûteux quand les données augmentent fortement.

Comparer des cas et des mesures

Une recherche séquentielle trouve parfois immédiatement sa cible : meilleur cas constant. Dans le pire cas, elle parcourt tout le tableau : coût linéaire. Le tri par insertion possède également un meilleur cas différent de son pire cas. Toute affirmation de coût doit donc annoncer le cas concerné.

Un chronométrage dépend du matériel, du langage, des autres activités et des données choisies. Il complète une analyse, mais ne prouve pas une loi générale. Une dichotomie illustre une autre croissance : diviser la zone par deux conduit à un nombre de visites logarithmique, sous la précondition que le tableau soit déjà trié.

Un temps deux fois plus court sur une petite entrée ne démontre pas que l’ordre de croissance est meilleur. Les constantes et les frais fixes peuvent dominer. Comparez plusieurs tailles en conservant les mêmes conditions, puis reliez les rapports observés au modèle. Si le compteur suit n², une multiplication de la taille par dix produit cent fois plus d’opérations du type étudié.

Exemple suivi : boucles successives, imbriquées et triangulaires

Pour n=4, deux parcours successifs de quatre valeurs font 4+4=8 examens. Deux parcours imbriqués complets produisent quatre examens pour chacune des quatre valeurs, soit 16. Un parcours de toutes les paires d’indices i < j produit 3+2+1=6 paires. Les trois programmes peuvent tous contenir deux boucles écrites, mais leur organisation change le compte.

La formule triangulaire vaut n*(n-1)/2. Elle compte chaque paire d’indices distincts une seule fois, sans compter (i,i) ni compter à la fois (i,j) et (j,i). Sur n=5, elle donne 10 ; sur n=10, elle donne 45. Le rapport exact est 4,5, pas 4. Le facteur quatre caractérise la tendance quadratique pour de grandes tailles, pas nécessairement le rapport exact de petites valeurs.

Combiner préparation et recherches répétées

Supposons un modèle fictif où préparer un catalogue coûte n² unités, puis chaque requête sur le catalogue préparé coûte 10 unités. Sans préparation, chaque requête coûte n unités. Pour n=100 et q requêtes, les coûts sont 10000+10*q et 100*q. L’avantage dépend de q : pour une seule requête, préparer est très coûteux ; pour mille, le total préparé devient 20 000 contre 100 000.

Ce calcul ne prétend pas mesurer un moteur réel ni donner le coût de tous les tris. Il montre comment additionner un investissement initial et un travail répété. Avant une comparaison, écrivez les hypothèses, l’opération comptée et le nombre de répétitions. Deux méthodes doivent résoudre le même problème, sur les mêmes données et avec les mêmes garanties, pour que leur coût soit interprétable.

De la compréhension à l’autonomie

À vous de résoudre

Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.

Les erreurs qui méritent un détour

Identifier n à la plus grande valeur du tableau.

Pour ces parcours, n est le nombre de cases. Changer 7 en 700 ne change pas le nombre de cases examinées.

Annoncer des secondes à partir d’un compteur abstrait.

Le compteur mesure du travail dans un modèle. Une durée nécessite des hypothèses matérielles et une mesure appropriée.

Le prochain pas

• Coûts en temps et en mémoire

Retrouver le catalogue de Première

Ce chapitre s’appuie sur le programme officiel de Première (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.