Un cap pour ce chapitre
Ce que vous saurez faire
- Définir une taille et une opération comptée.
- Comparer des ordres de croissance.
- Analyser la mémoire et les hypothèses de structure.
Dire ce que l’on compte
La taille peut être le nombre d’éléments d’une liste, de sommets et d’arêtes d’un graphe ou de caractères d’un texte. Un algorithme ne possède pas un coût « en n » tant que n n’est pas défini. L’opération étudiée doit aussi être précisée : comparaison de clés, accès à une case ou étape de boucle, par exemple.
Le temps mesuré en secondes dépend du matériel, de l’environnement et des données. Un modèle de comptage permet d’expliquer une tendance sans prédire directement un chronométrage. Deux implémentations du même ordre de croissance peuvent avoir des constantes très différentes.
Reconnaître quelques croissances
Un parcours complet de n éléments donne souvent un coût linéaire. Deux boucles parcourant chacune toute la liste peuvent donner un coût quadratique, si le corps s’exécute pour chaque paire. Diviser la zone de recherche par deux à chaque étape donne une progression logarithmique : on compte combien de divisions sont nécessaires pour atteindre une taille élémentaire.
Un tri fusion combine une quantité linéaire de travail à chaque niveau d’un découpage équilibré, d’où n log₂ n. Pour n=1024, log₂ n vaut dix, n log₂ n vaut 10 240 et n² vaut 1 048 576. Ces expressions sont des repères de croissance, pas toutes des nombres exacts de comparaisons.
Deux boucles successives de n tours donnent 2n opérations de corps, donc un coût linéaire. Deux boucles imbriquées de n tours donnent n×n opérations. Le nombre de mots for dans un programme ne suffit pas : dessinez les répétitions réellement effectuées et exprimez leur total.
Préciser meilleur cas, pire cas et structure
Une recherche séquentielle peut trouver sa cible dès la première case ou ne conclure qu’après n comparaisons. Une recherche dans un ABR dépend de sa hauteur : logarithmique si l’arbre reste suffisamment équilibré, linéaire dans une chaîne. Il faut donc associer le coût annoncé aux hypothèses qui le rendent vrai.
Parler du pire cas signifie majorer le travail pour toute entrée de la taille considérée selon le modèle. Une moyenne demanderait une hypothèse sur la distribution des entrées. On ne peut pas annoncer un cas moyen rigoureux uniquement à partir de quelques exemples choisis.
Compter aussi ce qui reste en mémoire
La mémoire d’entrée et la mémoire auxiliaire répondent à des questions différentes. Une fonction qui parcourt une liste avec deux variables supplémentaires peut utiliser une mémoire auxiliaire constante, même si la liste reçue grandit. Une fonction qui construit une copie de n éléments utilise une mémoire auxiliaire linéaire.
La récursion conserve les contextes actifs. Pour un arbre, le nombre total de nœuds visités peut être n tandis que la profondeur active vaut sa hauteur. Une table dynamique échange souvent davantage de mémoire contre moins de recalculs. Le bon choix dépend des contraintes et des résultats à conserver, pas d’une préférence systématique pour le moins de variables.
Exemple suivi : compter une boucle triangulaire
Considérons une boucle extérieure i de 0 à n-1 et une boucle intérieure j de 0 à i-1. Les nombres d’exécutions du corps intérieur sont 0,1,2,...,n-1. Leur somme vaut n(n-1)/2 : pour n=5, on compte dix passages. La moitié de n² reste de croissance quadratique ; on ne peut pas la qualifier de linéaire parce que la seconde boucle ne parcourt pas toujours toute la liste.
Cette formule peut compter les paires non ordonnées de positions distinctes : chaque paire est prise une seule fois avec j<i. Si le programme compare toutes les paires ordonnées, y compris une case avec elle-même, le total devient n². Les deux algorithmes ont le même ordre de croissance mais réalisent des tâches de comptage différentes. Une formule exacte exige de lire les bornes ; un ordre de grandeur gomme certaines constantes sans autoriser à ignorer le contrat.
Exemple suivi : doubler les données et distinguer les mémoires
Pour n=256, les repères log₂ n, n, n log₂ n et n² valent 8,256,2048,65536. En doublant à 512, ils deviennent 9,512,4608,262144. Le logarithme augmente de un, le linéaire double, le quadratique quadruple ; n log n est ici multiplié par 2,25. Dire que tout algorithme prend deux fois plus de temps sur deux fois plus de données serait donc injustifié, même dans un modèle simple.
Une recherche qui garde deux indices peut utiliser une mémoire auxiliaire constante. Si elle crée une nouvelle tranche à chaque réduction, elle ajoute des allocations à analyser. Une récursion qui garde tous les cadres en attente ajoute également de la mémoire, même si le source contient peu de noms. Enfin, compter un nombre d’entiers comme des cases de coût fixe est un modèle pédagogique : des entiers arbitrairement grands demanderaient une analyse en bits plus fine, hors de ces comparaisons usuelles.
À vous de faire varier les choses
Agrandissez les données et comparez les modèles
Choisissez une puissance de deux. Les valeurs sont des modèles de croissance, pas des mesures en secondes ni des comparaisons exactes d’un code particulier.
Lire le résultat de l’expérience initiale
n = 1 024.
Comparez l’effet d’un incrément de k : la taille double. Le logarithme augmente seulement de un.
| Modèle | Valeur pour n | Valeur pour 2n |
|---|---|---|
| log₂ n | 10 | 11 |
| n | 1024 | 2048 |
| n log₂ n | 10240 | 22528 |
| n² | 1048576 | 4194304 |
Les ordres de croissance expliquent la montée en charge ; les performances mesurées demandent en plus un contexte concret.
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.
Définir une variable de taille
On analyse un parcours de graphe par listes d’adjacence. Pourquoi une unique lettre n non définie rend-elle l’annonce « coût linéaire » ambiguë ?
Indice 1
Deux quantités décrivent la taille du graphe.
Indice 2
Une liste de voisins peut être longue même avec peu de sommets.
Comprendre la correction
Il faut distinguer le nombre de sommets et le nombre d’arêtes. Le travail d’un parcours dépend généralement des deux, souvent sous la forme V+E. Dire linéaire sans définir la quantité mesurée ne permet pas de vérifier l’annonce.
Doubler l’entrée
Dans les modèles n et n², par quel facteur le coût est-il multiplié quand n double ?
Indice 1
Remplacez n par 2n.
Indice 2
Développez (2n)².
Comprendre la correction
Le modèle linéaire est multiplié par deux. Le modèle quadratique est multiplié par quatre, car (2n)²=4n². Ce contraste devient très important lorsque la taille augmente plusieurs fois.
Corriger une affirmation sur l’ABR
Un élève affirme : « Une recherche dans tout ABR de mille nœuds prend environ dix comparaisons. » Quelle hypothèse manque ?
Indice 1
L’arbre peut-il être une chaîne ?
Indice 2
Le logarithme décrit une hauteur équilibrée.
Comprendre la correction
Il manque une condition de hauteur équilibrée. Un ABR construit par insertions triées peut former une chaîne de mille nœuds et demander mille comparaisons pour une clé à son extrémité. La propriété d’ordre seule ne garantit pas la forme.
Analyser une copie
Une fonction crée une nouvelle liste de n éléments puis la parcourt avec deux indices. Sa mémoire auxiliaire est-elle constante parce qu’elle n’utilise que trois noms de variables ?
Indice 1
Un nom peut référencer un objet de taille variable.
Indice 2
Comptez les données stockées, pas seulement les noms.
Comprendre la correction
Non. La liste supplémentaire contient n éléments et domine la mémoire auxiliaire, qui est linéaire. Les deux indices ajoutent seulement une quantité constante. Le nombre de noms dans le code ne mesure pas le volume des objets qu’ils désignent.
Problème : compter trois organisations
Trois programmes exécutent respectivement deux boucles successives de n tours, deux boucles imbriquées de n tours et une boucle triangulaire j<i. Donnez leurs comptes pour n=6 puis leurs formules. Les trois ont-ils le même ordre de croissance ?
Indice 1
Additionnez les boucles successives.
Indice 2
Pour la dernière, additionnez 0+1+2+3+4+5.
Comprendre la correction
Les comptes valent 12,36,15. Les formules sont 2n, n² et n(n-1)/2. La première est linéaire, les deux autres quadratiques. L’organisation de l’exécution, et pas le nombre de boucles écrites, explique la différence. Une borne variable peut réduire le compte exact sans changer l’ordre dominant.
Problème : interpréter une mesure
Deux programmes ont des modèles 20n et n² opérations. Comparez-les pour n=10,20,100. Trouvez le seuil d’égalité. Peut-on en déduire des secondes sans autre donnée ? Expliquez pourquoi le meilleur ordre asymptotique ne gagne pas sur toutes les petites entrées.
Indice 1
Résolvez 20n=n² avec n positif.
Indice 2
Les coefficients représentent aussi du travail.
Comprendre la correction
Les couples de comptes sont (200,100),(400,400),(2000,10000). L’égalité positive est à n=20. Le modèle quadratique est plus petit à n=10, mais le linéaire gagne au-delà du seuil. Les comptes ne sont pas des secondes sans coût concret des opérations. L’analyse de croissance guide les grandes tailles sans effacer les constantes ni le contexte de mesure.
Problème : examiner mémoire et profondeur
A calcule une somme avec un accumulateur ; B copie la liste avant le même calcul ; C utilise une récursion qui retire une valeur par appel sans copier l’entrée. Pour une liste de n valeurs, comparez leur temps et mémoire auxiliaire. Pourquoi la correction de C ne suffit-elle pas à garantir une exécution sur une très longue liste ?
Indice 1
B stocke n cases supplémentaires.
Indice 2
C conserve jusqu’à n cadres actifs dans le modèle.
Comprendre la correction
Les trois calculs ont un temps linéaire dans le modèle usuel, avec une copie supplémentaire pour B. A utilise une mémoire auxiliaire constante, B une mémoire linéaire et C une pile de profondeur linéaire. Même si C termine mathématiquement, l’environnement peut imposer une profondeur maximale de récursion. Les garanties de résultat et les limites pratiques de ressources sont distinctes.
Les erreurs qui méritent un détour
- Transformer une expression de coût en secondes.
- Il manque le coût concret des opérations et les conditions de mesure.
- Compter uniquement les variables nommées.
- Les objets et les contextes d’appels peuvent avoir une taille variable.
La fiche à garder
L’essentiel à retenir
- Définissez la taille, l’opération et le cas étudié.
- Une meilleure croissance devient décisive lorsque l’entrée augmente.
- Le coût mémoire comprend les structures auxiliaires et la pile.
Cette notion au bac
Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.
- Bac 2026 · Centres étrangers groupe 1 · Jour 1 : Classement d’athlètes : tri par sélection et ABR
- Bac 2026 · Amérique du Nord · Jour 1 : Puissance 4 : scores, arbre de coups et min-max
- Bac 2026 · Antilles-Guyane · Jour 1 : Plus longue sous-séquence commune : de l’exhaustif au dynamique
- Bac 2026 · Antilles-Guyane · Jour 2 : Scierie : valoriser le stock et optimiser les découpes
Le prochain pas
Retrouver le catalogue de Terminale
Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.