Chapitre 17 — Introduction à la complexité
Évaluer le temps d’exécution, la mémoire utilisée et l’évolution du coût selon la taille des données
Fiche pédagogique du chapitre
Objectifs d’apprentissage
À la fin de ce chapitre, l’étudiant devra être capable de :
- expliquer pourquoi le temps chronométré ne suffit pas pour comparer deux algorithmes ;
- distinguer le coût temporel du coût spatial ;
- identifier la taille pertinente des données, généralement notée n ;
- compter les opérations élémentaires d’un algorithme simple ;
- analyser une suite d’instructions, une condition, une boucle et des boucles imbriquées ;
- interpréter les complexités O(1), O(log n), O(n) et O(n²) ;
- déterminer la complexité des recherches séquentielle et dichotomique ;
- évaluer le coût d’un parcours de tableau ou de matrice ;
- comparer plusieurs solutions selon la taille des données ;
- raisonner sur un compromis entre temps d’exécution, mémoire et lisibilité.
Prérequis
- variables, affectations, expressions et structures conditionnelles ;
- boucles simples et boucles imbriquées ;
- tableaux à une et deux dimensions ;
- fonctions et procédures ;
- algorithmes de recherche et de tri élémentaires.
Plan du chapitre
Section | Contenu principal |
|---|---|
17.1 | Pourquoi analyser un algorithme : temps, mémoire, comparaison et taille des données |
17.2 | Nombre d’opérations : instructions, conditions, boucles simples et imbriquées |
17.3 | Notation asymptotique : O(1), O(log n), O(n) et O(n²) |
17.4 | Exemples : accès, recherches, matrice et tris simples |
17.5 | Compromis temps-mémoire, lisibilité et optimisation raisonnée |
Organisation pédagogique indicative
Activité | Durée indicative | Contenu |
|---|---|---|
Cours | 3 h | Principes, comptage des opérations et ordres de grandeur |
Travaux dirigés | 3 h | Calculs de complexité et comparaison de solutions |
Travaux pratiques | 2 h | Mesures expérimentales et confrontation avec l’analyse théorique |
Évaluation | 1 h | Questions de compréhension et analyse d’algorithmes |
Idée centrale : L’objectif n’est pas de prédire exactement le nombre de millisecondes. Il s’agit surtout de comprendre comment le coût évolue lorsque la quantité de données augmente. |
Introduction
Deux algorithmes peuvent produire exactement le même résultat tout en demandant des ressources très différentes. Pour quelques données, cette différence peut être invisible. Pour des milliers ou des millions de valeurs, elle peut rendre une solution instantanée, lente ou même inutilisable.
L’analyse de complexité fournit un langage commun pour décrire cette évolution. Elle ne dépend pas principalement de la marque du processeur, du langage de programmation ou de la vitesse momentanée de l’ordinateur. Elle cherche à relier le coût d’un algorithme à la taille de son entrée.
Dans ce chapitre, la lettre n représentera généralement le nombre d’éléments à traiter. Pour une matrice, on utilisera parfois L pour le nombre de lignes et C pour le nombre de colonnes. Les résultats seront exprimés à l’aide de la notation asymptotique O, appelée couramment « grand O ».
À retenir : La complexité est un modèle. Elle simplifie certains détails pour faire apparaître le comportement dominant de l’algorithme lorsque les données deviennent grandes. |
17.1 Pourquoi analyser un algorithme ?
17.1.1 Temps d’exécution
Le temps d’exécution correspond à la durée nécessaire pour réaliser un traitement. Une mesure chronométrée est utile pendant les tests, mais elle dépend de nombreux facteurs : processeur, mémoire, système d’exploitation, langage, compilateur, charge de la machine et données utilisées.
L’analyse théorique remplace donc le temps physique par un nombre d’opérations significatives. Elle permet d’étudier la tendance générale sans exiger une machine particulière.
Approche | Question posée | Limite principale |
|---|---|---|
Chronométrage | Combien de secondes ce programme prend-il ici et maintenant ? | Résultat dépendant de la machine et du contexte |
Analyse théorique | Comment le nombre d’opérations évolue-t-il avec n ? | Modèle simplifié qui ne donne pas un temps exact |
17.1.2 Mémoire utilisée
Un algorithme utilise de la mémoire pour stocker ses variables, ses tableaux, ses structures auxiliaires et, dans le cas de la récursivité, les appels en attente. La complexité spatiale décrit la quantité de mémoire supplémentaire nécessaire en fonction de la taille des données.
Il faut distinguer les données d’entrée, déjà fournies au programme, et la mémoire auxiliaire créée par l’algorithme. Par exemple, inverser un tableau sur place utilise peu de mémoire supplémentaire, alors que créer un second tableau de même taille exige un espace proportionnel à n.
Solution | Mémoire auxiliaire | Interprétation |
|---|---|---|
Échange des cases dans le même tableau | Quelques variables | Espace constant : O(1) |
Copie dans un deuxième tableau | n nouvelles cases | Espace linéaire : O(n) |
17.1.3 Comparaison de plusieurs solutions
L’analyse de complexité aide à choisir entre plusieurs algorithmes corrects. Une solution très simple peut être préférable pour une petite quantité de données. Une solution plus élaborée devient intéressante lorsque n augmente ou lorsque l’opération est répétée de nombreuses fois.
Nuance : Une meilleure complexité asymptotique ne garantit pas toujours le meilleur temps pour de petites entrées. Les constantes, la simplicité du code et le coût de préparation peuvent compter. |
17.1.4 Influence de la taille des données
La taille des données est la grandeur qui contrôle le travail à effectuer. Elle doit être choisie en fonction du problème : nombre de valeurs d’un tableau, longueur d’une chaîne, nombre de sommets d’un graphe, dimensions d’une matrice ou nombre de chiffres d’un entier.
Problème | Taille pertinente |
|---|---|
Rechercher une valeur dans un tableau | n = nombre d’éléments |
Parcourir une matrice | L = lignes et C = colonnes |
Comparer deux chaînes | n = longueur de la chaîne la plus courte ou des deux chaînes |
Traiter un réseau | Nombre de sommets et nombre de connexions |
Lorsque n double, un algorithme linéaire effectue approximativement deux fois plus de travail. Un algorithme quadratique peut en effectuer environ quatre fois plus. Cette différence explique pourquoi l’ordre de croissance devient déterminant pour les grandes tailles.
17.2 Nombre d’opérations
17.2.1 Opération élémentaire et modèle de coût
Une opération élémentaire est une action dont le coût est considéré comme constant dans le modèle étudié : affectation, addition, comparaison, accès à une case ou incrémentation. Le détail exact dépend du niveau d’analyse choisi, mais la méthode doit rester cohérente du début à la fin.
Méthode : On peut compter précisément les opérations pour comprendre un algorithme, puis simplifier l’expression afin de conserver uniquement son ordre de croissance. |
17.2.2 Instruction simple
Une instruction simple exécutée une seule fois possède un coût constant. Son nombre d’opérations ne dépend pas de n.
Exemple
x ← 5 |
Même si ces trois lignes ne demandent pas exactement le même travail machine, leur quantité reste bornée par une constante. La complexité temporelle est donc O(1).
17.2.3 Suite d’instructions
Pour une suite d’instructions, les coûts s’additionnent. Si chaque instruction est constante et si leur nombre ne dépend pas de n, l’ensemble reste constant.
Instruction | Nombre approximatif d’exécutions |
|---|---|
a ← 10 | 1 |
b ← 20 | 1 |
c ← a + b | 1 |
Écrire(c) | 1 |
Total | Constante |
17.2.4 Condition
Pour une structure conditionnelle, il faut compter le test et le coût de la branche exécutée. Une seule branche est choisie dans un Si…Sinon. Pour obtenir une borne supérieure, on retient souvent la branche la plus coûteuse.
Si T[i] > maximum Alors |
Le test est effectué une fois. L’affectation est exécutée uniquement si la condition est vraie. Le coût de ce fragment reste O(1).
Analyse | Coût retenu |
|---|---|
Meilleur cas | Branche la moins coûteuse |
Pire cas | Branche la plus coûteuse |
Cas moyen | Coût attendu selon une hypothèse sur les données |
17.2.5 Boucle simple
Le coût d’une boucle dépend du nombre d’itérations et du coût de son corps. Si le corps est constant et répété n fois, le coût total est proportionnel à n.
somme ← 0 |
Élément | Nombre d’exécutions |
|---|---|
Initialisation de somme | 1 |
Lecture de T[i] | n |
Addition et affectation | n |
Contrôle de boucle | Proportionnel à n |
Une expression exacte pourrait être de la forme an + b, où a et b sont des constantes. Pour l’analyse asymptotique, elle devient O(n).
17.2.6 Boucles imbriquées
Lorsque deux boucles sont imbriquées, le nombre total d’exécutions du corps correspond généralement au produit des nombres d’itérations.
Pour i allant de 0 à n - 1 Faire |
La boucle extérieure s’exécute n fois. Pour chacune de ses itérations, la boucle intérieure s’exécute n fois. Le corps est donc exécuté n × n = n² fois. La complexité est O(n²).
Boucles triangulaires
Toutes les boucles imbriquées ne réalisent pas exactement n² opérations. Dans l’exemple suivant, la boucle intérieure effectue 1 + 2 + … + n itérations, soit n(n + 1)/2. Cette quantité reste quadratique.
Pour i allant de 0 à n - 1 Faire |
Simplification : Les constantes multiplicatives et les termes de degré inférieur sont ignorés dans l’ordre de grandeur : n(n + 1)/2 = 0,5n² + 0,5n devient O(n²). |
17.2.7 Boucles successives et boucles imbriquées
Structure | Nombre d’opérations | Complexité |
|---|---|---|
Deux boucles successives de n itérations | n + n = 2n | O(n) |
Deux boucles imbriquées de n itérations | n × n = n² | O(n²) |
Boucle de n puis boucle de m | n + m | O(n + m) |
Boucle imbriquée n par m | n × m | O(nm) |
17.3 Notation asymptotique
17.3.1 Principe de la notation O
La notation O décrit une borne sur la vitesse de croissance du coût. Elle met en évidence le terme dominant lorsque la taille n devient grande. Elle ne représente ni une durée en secondes ni un nombre exact d’instructions.
Pour simplifier une expression de coût :
- on supprime les constantes multiplicatives ;
- on ignore les termes de degré inférieur ;
- on conserve le terme qui croît le plus rapidement.
Expression détaillée | Terme dominant | Notation |
|---|---|---|
7 | Constante | O(1) |
3n + 12 | n | O(n) |
5n² + 4n + 20 | n² | O(n²) |
2 log₂(n) + 8 | log n | O(log n) |
17.3.2 Complexité constante : O(1)
Un algorithme est constant lorsque son nombre d’opérations ne dépend pas de la taille des données. Accéder directement à une case d’un tableau par son indice constitue l’exemple classique.
valeur ← T[k] |
Que le tableau contienne 10, 1 000 ou 1 000 000 d’éléments, une seule case est consultée, à condition que l’indice soit valide.
17.3.3 Complexité logarithmique : O(log n)
Une complexité logarithmique apparaît lorsqu’une étape réduit fortement la partie restante, souvent en la divisant par deux. La recherche dichotomique illustre ce comportement.
Taille initiale n | Divisions par deux approximatives |
|---|---|
8 | 3 |
1 024 | 10 |
1 048 576 | 20 |
Environ 1 milliard | 30 |
La base du logarithme n’est généralement pas indiquée dans la notation O, car changer de base ne modifie qu’un facteur constant.
17.3.4 Complexité linéaire : O(n)
Une complexité linéaire signifie que le travail augmente proportionnellement au nombre d’éléments. Parcourir un tableau entier, calculer sa somme ou rechercher une valeur sans information supplémentaire sont des opérations linéaires.
Pour chaque élément de T Faire |
17.3.5 Complexité quadratique : O(n²)
Une complexité quadratique apparaît souvent lorsqu’il faut comparer chaque élément avec de nombreux autres éléments ou parcourir toutes les paires. Les tris élémentaires et certaines doubles boucles sont quadratiques.
Pour i allant de 0 à n - 1 Faire |
17.3.6 Comparaison des croissances
n | O(1) | O(log₂ n) | O(n) | O(n²) |
|---|---|---|---|---|
10 | 1 | ≈ 4 | 10 | 100 |
100 | 1 | ≈ 7 | 100 | 10 000 |
1 000 | 1 | ≈ 10 | 1 000 | 1 000 000 |
1 000 000 | 1 | ≈ 20 | 1 000 000 | 10¹² |
Conséquence pratique : Lorsque n est grand, la différence entre O(n), O(n log n) et O(n²) domine largement les petites optimisations d’instructions. |
17.3.7 Meilleur, pire et cas moyen
La complexité peut varier selon la disposition des données. La recherche séquentielle trouve parfois la valeur dès la première case, mais peut aussi parcourir tout le tableau.
Cas | Recherche séquentielle |
|---|---|
Meilleur cas | La valeur est en première position : O(1) |
Pire cas | Valeur absente ou en dernière position : O(n) |
Cas moyen | Environ la moitié du tableau est parcourue : O(n) |
Dans un cours d’introduction, on utilise fréquemment la complexité du pire cas parce qu’elle fournit une garantie supérieure et reste souvent plus simple à déterminer.
17.4 Exemples d’analyse
17.4.1 Accès à un élément d’un tableau
x ← T[indice] |
L’adresse de la case est calculée directement à partir de l’indice. Le coût ne dépend pas du nombre total d’éléments. Temps : O(1). Mémoire auxiliaire : O(1).
17.4.2 Recherche séquentielle
Fonction RechercheSequentielle(T, n, valeur) : Entier |
Situation | Cases examinées | Complexité |
|---|---|---|
Valeur en première position | 1 | O(1) meilleur cas |
Valeur en dernière position | n | O(n) pire cas |
Valeur absente | n | O(n) pire cas |
La mémoire auxiliaire est constante : seuls l’indice et quelques variables sont nécessaires.
17.4.3 Recherche dichotomique
La recherche dichotomique exige un tableau trié. À chaque étape, elle compare la valeur recherchée à l’élément du milieu puis conserve une moitié du tableau.
Fonction RechercheDichotomique(T, n, valeur) : Entier |
Le nombre d’étapes correspond au nombre de divisions par deux nécessaires pour réduire l’intervalle à une seule case. Temps : O(log n). Mémoire auxiliaire : O(1) pour la version itérative.
Choix global : Trier un tableau uniquement pour effectuer une seule recherche peut coûter plus cher qu’une recherche séquentielle. En revanche, si de nombreuses recherches sont prévues, le tri initial peut devenir rentable. |
17.4.4 Parcours d’une matrice
somme ← 0 |
Chaque case est visitée exactement une fois. Le nombre d’opérations est proportionnel à L × C. La complexité est O(LC). Pour une matrice carrée de dimension n × n, elle devient O(n²).
17.4.5 Tri simple
Les tris par sélection, à bulles et par insertion effectuent, dans leur version générale, un nombre quadratique de comparaisons dans le pire cas.
Algorithme | Meilleur cas | Pire cas | Mémoire auxiliaire |
|---|---|---|---|
Tri par sélection | O(n²) | O(n²) | O(1) |
Tri à bulles optimisé | O(n) | O(n²) | O(1) |
Tri par insertion | O(n) | O(n²) | O(1) |
Le tri à bulles optimisé et le tri par insertion profitent d’un tableau déjà ou presque trié. Le tri par sélection conserve environ le même nombre de comparaisons, quelle que soit l’organisation initiale.
17.4.6 Exemple complet : maximum et moyenne
somme ← 0 |
La boucle parcourt le tableau une seule fois. Son corps contient un nombre constant d’opérations. Le temps est O(n) et la mémoire auxiliaire est O(1). Calculer la somme et le maximum dans deux boucles distinctes resterait O(n), car n + n = 2n, mais demanderait deux parcours au lieu d’un.
17.4.7 Exemple complet : détection de doublons
doublon ← Faux |
Dans le pire cas, toutes les paires sont comparées. Leur nombre vaut n(n - 1)/2. La complexité est donc O(n²). Une stratégie fondée sur une structure de recherche supplémentaire peut réduire le temps au prix de mémoire additionnelle.
17.5 Compromis temps-mémoire
17.5.1 Utilisation de mémoire supplémentaire
Il est souvent possible d’accélérer un algorithme en stockant des informations intermédiaires. Cette amélioration temporelle exige alors davantage de mémoire. À l’inverse, une solution très économe en mémoire peut recalculer plusieurs fois les mêmes valeurs.
Stratégie | Temps | Mémoire | Exemple |
|---|---|---|---|
Calcul à chaque demande | Peut répéter le travail | Faible | Recalculer une valeur déjà obtenue |
Stockage des résultats | Accès plus rapide | Plus élevée | Mémoïsation de Fibonacci |
17.5.2 Recalcul ou stockage
Le choix dépend du nombre de consultations, du coût du calcul, de la taille des résultats et de la mémoire disponible. Un résultat rarement utilisé n’a pas forcément besoin d’être conservé. Un résultat coûteux demandé très souvent peut avantageusement être mis en cache.
Contexte : Le meilleur compromis dépend du contexte : ordinateur embarqué avec peu de mémoire, serveur disposant de mémoire mais soumis à de nombreuses requêtes, application interactive exigeant une réponse immédiate, etc. |
17.5.3 Optimisation prématurée
Optimiser trop tôt peut rendre un programme complexe sans apporter de bénéfice mesurable. La première priorité reste la correction. Il convient ensuite de choisir une structure et un algorithme adaptés, de mesurer le comportement réel, puis d’optimiser les parties réellement coûteuses.
Une démarche raisonnable suit les étapes suivantes :
- écrire une solution correcte et compréhensible ;
- analyser son ordre de grandeur ;
- tester avec des données représentatives ;
- identifier les véritables goulots d’étranglement ;
- améliorer sans perdre les garanties de correction.
17.5.4 Lisibilité et efficacité
Une optimisation qui réduit légèrement le temps mais rend le code très difficile à comprendre peut augmenter le risque d’erreurs et le coût de maintenance. La lisibilité, la testabilité et la documentation font donc partie de la qualité globale d’une solution.
Situation | Choix conseillé |
|---|---|
Deux solutions de même complexité et performances proches | Préférer la plus lisible |
Une solution simple devient trop lente avec les données réelles | Envisager un algorithme d’un meilleur ordre de croissance |
Une optimisation augmente fortement la mémoire | Vérifier les contraintes de la plateforme |
Le code critique est réutilisé très souvent | Mesurer et documenter l’optimisation |
17.5.5 Synthèse du compromis
Principe de conception : Une bonne solution n’est pas nécessairement celle qui minimise une seule ressource. Elle répond aux contraintes du problème avec un équilibre acceptable entre temps, mémoire, simplicité, robustesse et maintenabilité. |
Applications guidées
Application 1 — Identifier la complexité d’un parcours
On considère un tableau T de n entiers. L’algorithme affiche tous ses éléments une seule fois.
Pour i allant de 0 à n - 1 Faire |
Le corps de la boucle est constant et s’exécute n fois. La complexité temporelle est O(n). Aucune structure proportionnelle à n n’est créée : la mémoire auxiliaire est O(1).
Application 2 — Distinguer boucles successives et imbriquées
Pour i allant de 0 à n - 1 Faire |
Les deux boucles sont successives : n + n = 2n, donc O(n). Si la deuxième boucle était placée à l’intérieur de la première, le coût deviendrait n × n = n², donc O(n²).
Application 3 — Choisir une méthode de recherche
Un tableau non trié contient 200 valeurs et une seule recherche doit être effectuée. Une recherche séquentielle est raisonnable : elle évite le coût du tri. Si le tableau contient plusieurs millions de valeurs et doit recevoir des milliers de recherches, le maintenir trié et utiliser la recherche dichotomique peut devenir préférable.
Contexte | Solution plausible | Justification |
|---|---|---|
Une recherche dans un petit tableau non trié | Séquentielle | Simplicité et absence de préparation |
Nombreuses recherches dans un tableau trié | Dichotomique | O(log n) par recherche |
Ajouts très fréquents et recherches rares | Dépend de la structure globale | Le maintien du tri peut coûter cher |
Application 4 — Comparer temps et mémoire
Pour détecter un doublon, une double boucle utilise O(1) mémoire supplémentaire mais O(n²) temps. Une structure auxiliaire contenant les valeurs déjà vues peut utiliser O(n) mémoire et réduire le temps moyen selon la structure employée. Le choix dépend de la mémoire disponible et de la taille de n.
Application 5 — Analyser une matrice
Pour i allant de 0 à n - 1 Faire |
Cet algorithme ne parcourt que la diagonale principale d’une matrice n × n. Il visite n cases et possède une complexité O(n), contrairement au parcours complet de la matrice qui est O(n²).
Travaux dirigés
Pour chaque exercice, préciser la taille des données, le nombre d’itérations principal, la complexité temporelle et, lorsque cela est pertinent, la complexité spatiale.
Exercice 1 — Instructions constantes
Déterminer la complexité du fragment : a ← T[0] ; b ← T[n - 1] ; résultat ← a + b.
Exercice 2 — Somme d’un tableau
Analyser un algorithme qui additionne les n éléments d’un tableau.
Exercice 3 — Deux parcours
Un algorithme calcule d’abord le minimum dans une boucle, puis le maximum dans une deuxième boucle. Déterminer sa complexité.
Exercice 4 — Toutes les paires
Un algorithme compare chaque élément d’un tableau à tous les éléments suivants. Déterminer le nombre de comparaisons et la complexité.
Exercice 5 — Division répétée
Une variable n est divisée par 2 jusqu’à devenir inférieure à 1. Déterminer la complexité.
Exercice 6 — Matrice rectangulaire
Une matrice possède L lignes et C colonnes. Analyser son parcours complet.
Exercice 7 — Recherche
Comparer la recherche séquentielle et la recherche dichotomique pour un tableau trié de 1 000 000 d’éléments.
Exercice 8 — Diagonale
Analyser le calcul de la somme de la diagonale principale d’une matrice n × n.
Exercice 9 — Tri élémentaire
Expliquer pourquoi le tri par sélection est O(n²), même lorsque le tableau est déjà trié.
Exercice 10 — Temps-mémoire
Proposer deux stratégies pour calculer plusieurs fois une même fonction coûteuse : recalcul et stockage. Comparer leurs ressources.
Exercice 11 — Simplification
Donner la notation O de : 12 ; 4n + 3 ; 7n² + 2n + 1 ; 5 log₂(n) + 20.
Exercice 12 — Analyse critique
Deux algorithmes ont respectivement les coûts 100n et n². Pour quelles tailles l’un peut-il être préférable à l’autre ? Discuter sans se limiter à la notation O.
Corrigés indicatifs des travaux dirigés
Exercice 1
Trois opérations principales, indépendantes de n. Complexité temporelle O(1) et mémoire auxiliaire O(1).
Exercice 2
La boucle visite chaque case une fois. Temps O(n). L’accumulateur et l’indice occupent un espace constant : O(1).
Exercice 3
Les deux boucles sont successives : n + n = 2n. Après simplification, la complexité est O(n), pas O(n²).
Exercice 4
Le nombre de paires vaut n(n - 1)/2. Le terme dominant est n² : complexité O(n²).
Exercice 5
Après k divisions, la valeur est n/2ᵏ. Il faut environ log₂(n) divisions. Complexité O(log n).
Exercice 6
Chaque case est visitée une fois, soit L × C cases. Complexité O(LC). Si L = C = n, elle devient O(n²).
Exercice 7
La recherche séquentielle peut examiner jusqu’à 1 000 000 de cases. La recherche dichotomique nécessite environ 20 comparaisons, car 2²⁰ ≈ 1 000 000. Elle exige toutefois un tableau trié.
Exercice 8
La diagonale contient n cases. Une seule boucle suffit : O(n), avec O(1) mémoire auxiliaire.
Exercice 9
À chaque position, le tri par sélection recherche le minimum dans toute la partie restante. Le nombre de comparaisons reste n(n - 1)/2, même si les valeurs sont déjà dans l’ordre.
Exercice 10
Le recalcul utilise peu de mémoire mais répète le temps de calcul. Le stockage évite les recalculs au prix d’un espace supplémentaire. Le meilleur choix dépend du nombre de demandes, du coût du calcul et de la mémoire disponible.
Exercice 11
12 → O(1) ; 4n + 3 → O(n) ; 7n² + 2n + 1 → O(n²) ; 5 log₂(n) + 20 → O(log n).
Exercice 12
La notation O masque les constantes. 100n est supérieur à n² lorsque n < 100, égal pour n = 100 et inférieur lorsque n > 100. Le seuil réel dépend aussi de la machine, des opérations et des données. Une analyse complète combine ordre de croissance et mesures.
Synthèse du chapitre
Notion | Idée essentielle |
|---|---|
Analyse temporelle | Étudie l’évolution du nombre d’opérations avec la taille des données. |
Analyse spatiale | Étudie la mémoire auxiliaire nécessaire. |
O(1) | Coût indépendant de n. |
O(log n) | Le problème est réduit par un facteur constant à chaque étape. |
O(n) | Le travail est proportionnel au nombre d’éléments. |
O(n²) | Le travail porte souvent sur toutes les paires ou sur deux dimensions de taille n. |
Boucles successives | Les coûts s’additionnent. |
Boucles imbriquées | Les nombres d’itérations se multiplient généralement. |
Compromis | Le choix équilibre temps, mémoire, lisibilité et contraintes réelles. |
Méthode en quatre étapes : Identifier n, compter les répétitions, conserver le terme dominant, puis vérifier la mémoire auxiliaire : cette démarche permet d’analyser la majorité des algorithmes élémentaires. |
Glossaire
Terme | Définition |
|---|---|
Complexité temporelle | Évolution du nombre d’opérations selon la taille de l’entrée. |
Complexité spatiale | Évolution de la mémoire auxiliaire nécessaire. |
Taille n | Mesure principale de la quantité de données traitées. |
Opération élémentaire | Action considérée comme de coût constant dans le modèle. |
Terme dominant | Partie d’une expression qui croît le plus vite. |
Notation O | Notation décrivant une borne asymptotique de croissance. |
Meilleur cas | Configuration qui demande le moins de travail. |
Pire cas | Configuration qui demande le plus de travail. |
Mémoire auxiliaire | Mémoire supplémentaire créée par l’algorithme. |
Optimisation | Modification visant à améliorer l’utilisation des ressources. |
Auto-évaluation
Cochez les affirmations que vous êtes capable de réaliser sans aide :
✓ | Compétence |
|---|---|
☐ | Je sais définir la taille pertinente d’un problème. |
☐ | Je sais distinguer temps mesuré et complexité théorique. |
☐ | Je sais analyser une instruction, une condition et une suite d’instructions. |
☐ | Je sais calculer le coût d’une boucle simple. |
☐ | Je sais distinguer boucles successives et imbriquées. |
☐ | Je sais reconnaître O(1), O(log n), O(n) et O(n²). |
☐ | Je sais simplifier une expression pour conserver son terme dominant. |
☐ | Je sais analyser les recherches séquentielle et dichotomique. |
☐ | Je sais déterminer le coût d’un parcours de matrice. |
☐ | Je sais expliquer un compromis temps-mémoire. |
☐ | Je sais justifier une optimisation par des mesures et par l’analyse. |
Conseil final : Avant d’optimiser un programme, vérifier sa correction, analyser son ordre de grandeur et mesurer son comportement avec des données représentatives. |