Mesurer les ressources, maîtriser les notations asymptotiques et comparer les ordres de grandeur

Fiche pédagogique du chapitre

Objectifs d’apprentissage

À la fin de ce chapitre, l’étudiant devra être capable de :

• identifier la taille pertinente des données d’un problème et les ressources à mesurer ;
• distinguer le temps d’exécution mesuré du coût théorique d’un algorithme ;
• évaluer la mémoire auxiliaire et la profondeur de la pile récursive ;
• compter les comparaisons, les affectations et les appels récursifs ;
• interpréter les notations O, Ω et Θ sans les confondre ;
• distinguer meilleur cas, cas moyen et pire cas ;
• appliquer les règles de somme et de produit des complexités ;
• analyser des boucles successives, imbriquées et dépendantes ;
• déterminer le coût d’une condition et d’un appel de fonction ;
• comparer O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) et O(n!) ;
• estimer la faisabilité pratique d’un algorithme selon la taille des données ;
• justifier le choix d’un algorithme de recherche selon le contexte.

Prérequis

• variables, affectations, expressions et structures conditionnelles ;
• boucles Pour, TantQue et boucles imbriquées ;
• tableaux à une et deux dimensions ;
• fonctions, procédures et récursivité élémentaire ;
• recherche séquentielle et recherche dichotomique ;
• notions introductives de complexité O(1), O(log n), O(n) et O(n²).

Plan du chapitre

Organisation pédagogique indicative

Introduction

Au niveau débutant, la complexité a été présentée comme une manière de décrire l’évolution du coût d’un algorithme lorsque la taille des données augmente. Au niveau intermédiaire, cette idée doit être affinée : il ne suffit plus d’annoncer une notation O(n) ou O(n²). Il faut préciser la ressource mesurée, le cas étudié, le modèle de coût utilisé et la justification du résultat.

Deux programmes peuvent résoudre le même problème, produire exactement le même résultat et pourtant présenter des comportements très différents. L’un peut être plus rapide mais utiliser davantage de mémoire ; un autre peut être plus simple à lire, mais effectuer de nombreuses comparaisons inutiles. L’analyse algorithmique aide à rendre ces compromis explicites.

Dans ce chapitre, la taille des données sera généralement notée n. Pour une matrice, on pourra utiliser L pour le nombre de lignes et C pour le nombre de colonnes. Pour un graphe, les chapitres ultérieurs utiliseront V pour le nombre de sommets et E pour le nombre d’arêtes.

1.1 Mesure des ressources

Analyser un algorithme consiste d’abord à choisir les ressources pertinentes. Le temps et la mémoire sont les deux ressources principales, mais certaines opérations peuvent également être comptées séparément : comparaisons, affectations, échanges, accès à un tableau ou appels récursifs. Le choix dépend du problème et de l’algorithme étudié.

1.1.1 Temps d’exécution

Le temps d’exécution est la durée nécessaire à un programme pour terminer son traitement. Une mesure chronométrée est utile pour comparer des implémentations dans un environnement donné, mais elle dépend du processeur, du langage, du compilateur, du système d’exploitation, de la charge de la machine et des données utilisées.

L’analyse théorique remplace donc les secondes par un nombre d’opérations significatives. Pour une recherche, on compte souvent les comparaisons. Pour un tri, on peut compter les comparaisons et les échanges. Pour un calcul matriciel, on compte généralement les opérations arithmétiques.

1.1.2 Mémoire utilisée

La complexité spatiale décrit la quantité de mémoire nécessaire. Il convient de distinguer la mémoire contenant les données d’entrée de la mémoire auxiliaire créée par l’algorithme. Un algorithme dit « en place » utilise une quantité faible et souvent constante de mémoire supplémentaire.

• variables simples : quelques cases mémoire, généralement O(1) ;
• tableau auxiliaire de n éléments : O(n) ;
• matrice auxiliaire de L × C cases : O(LC) ;
• pile de récursion de profondeur n : O(n) ;
• pile de récursion de profondeur log n : O(log n).

Exemple : copie avec mémoire auxiliaire

Algorithme CopierTableau(T, n)
Variables
    C : tableau[0..n-1]
    i : entier
Début
    Pour i allant de 0 à n-1 Faire
        C[i] ← T[i]
    FinPour
    Retourner C
Fin

La boucle est linéaire en temps, et le tableau C demande une mémoire auxiliaire O(n). Une simple lecture du tableau sans copie aurait une mémoire auxiliaire O(1).

1.1.3 Nombre de comparaisons

Une comparaison vérifie une relation entre deux valeurs : égalité, ordre ou appartenance à un intervalle. Le nombre de comparaisons est souvent la mesure dominante dans les algorithmes de recherche et de tri.

Recherche séquentielle avec arrêt anticipé

trouvé ← Faux
i ← 0
TantQue i < n ET NON trouvé Faire
    Si T[i] = valeur Alors
        trouvé ← Vrai
    Sinon
        i ← i + 1
    FinSi
FinTantQue

1.1.4 Nombre d’affectations

Une affectation modifie la valeur d’une variable ou d’une case mémoire. Elle est généralement considérée comme une opération constante, mais son comptage permet de comparer des variantes d’un même algorithme. Dans les tris, les déplacements et les échanges peuvent représenter une part importante du coût.

Échange de deux éléments

temp ← T[i]
T[i] ← T[j]
T[j] ← temp

L’échange classique utilise trois affectations. Si un tri effectue e échanges, ces échanges représentent 3e affectations, auxquelles s’ajoutent les mises à jour des indices et des variables auxiliaires.

1.1.5 Nombre d’appels récursifs

Pour un algorithme récursif, le nombre d’appels et la profondeur maximale de la récursion doivent être étudiés séparément. Le nombre total d’appels influence le temps ; la profondeur maximale détermine la mémoire occupée par la pile d’exécution.

Exemple : factorielle récursive

Fonction Factorielle(n : entier) : entier
Début
    Si n = 0 Alors
        Retourner 1
    Sinon
        Retourner n × Factorielle(n - 1)
    FinSi
Fin

À l’inverse, une fonction de Fibonacci récursive naïve crée deux appels pour de nombreuses valeurs. Son arbre d’appels contient un nombre exponentiel de nœuds, alors que sa profondeur reste linéaire.

1.1.6 Choix de la taille des données

La variable n doit représenter la dimension qui explique réellement le travail. Dans certains problèmes, une seule taille suffit ; dans d’autres, plusieurs paramètres sont nécessaires.

Synthèse de la section 1.1

1.2 Notations asymptotiques

Les notations asymptotiques comparent la croissance de fonctions lorsque n devient grand. Elles ignorent les constantes multiplicatives et les termes de plus faible degré afin de retenir le comportement dominant. Elles ne doivent pas être utilisées comme de simples étiquettes : chacune exprime un type de borne différent.

1.2.1 Notation O : borne asymptotique supérieure

Dire que f(n) est en O(g(n)) signifie qu’à partir d’une certaine taille, f(n) ne dépasse pas une constante multipliée par g(n). La notation O fournit donc une borne supérieure. Elle est souvent utilisée pour exprimer un pire cas, mais O et pire cas ne sont pas synonymes : O décrit une borne, tandis que le pire cas décrit le choix des données les plus défavorables.

f(n) ∈ O(g(n)) si f(n) ≤ c · g(n) à partir d’un certain rang

Par exemple, 3n + 7 appartient à O(n), mais aussi à O(n²). La première borne est plus précise. En pratique, on recherche généralement la borne asymptotique la plus serrée.

1.2.2 Notation Ω : borne asymptotique inférieure

Dire que f(n) est en Ω(g(n)) signifie qu’à partir d’une certaine taille, f(n) est au moins égale à une constante multipliée par g(n). Cette notation garantit qu’un certain niveau de travail est inévitable.

f(n) ∈ Ω(g(n)) si f(n) ≥ c · g(n) à partir d’un certain rang

Une recherche séquentielle a un meilleur cas Ω(1), car au moins une comparaison est nécessaire. Dans le pire cas, elle effectue n comparaisons.

1.2.3 Notation Θ : borne asymptotique exacte

La notation Θ encadre la fonction entre deux multiples constants de g(n). Elle indique que g(n) décrit exactement l’ordre de croissance de f(n), à un facteur constant près.

f(n) ∈ Θ(g(n)) si c₁ · g(n) ≤ f(n) ≤ c₂ · g(n)

1.2.4 Meilleur cas, cas moyen et pire cas

Pour une même taille n, le comportement peut varier selon les données. Il faut donc préciser le scénario étudié.

Le cas moyen exige une hypothèse sur la distribution des entrées. Sans modèle probabiliste clairement défini, une « moyenne » n’a pas de signification rigoureuse. Le pire cas est souvent privilégié, car il fournit une garantie indépendante des données.

1.2.5 Exemple complet : recherche dichotomique

La recherche dichotomique élimine approximativement la moitié de la zone restante à chaque comparaison. Elle nécessite un tableau trié.

gauche ← 0
droite ← n - 1
TantQue gauche ≤ droite Faire
    milieu ← (gauche + droite) DIV 2
    Si T[milieu] = valeur Alors
        Retourner milieu
    SinonSi T[milieu] < valeur Alors
        gauche ← milieu + 1
    Sinon
        droite ← milieu - 1
    FinSi
FinTantQue
Retourner -1

1.2.6 Erreurs fréquentes

• confondre O avec une égalité exacte : O(n) ne signifie pas exactement n opérations ;
• annoncer O(n²) pour une fonction linéaire : la borne est vraie mais inutilement large ;
• confondre notation O et pire cas ;
• oublier de préciser la taille n et le scénario étudié ;
• utiliser Θ sans avoir établi une borne supérieure et une borne inférieure de même ordre ;
• comparer uniquement les constantes pour conclure sur de très grandes tailles ;
• ignorer le coût du prétraitement, par exemple le tri nécessaire avant une recherche dichotomique.

1.3 Règles de calcul

L’analyse d’un algorithme complexe repose sur quelques règles simples. Il faut découper le programme en blocs, calculer le coût de chaque bloc, puis les combiner selon la structure de contrôle utilisée.

1.3.1 Simplification des expressions de coût

Une expression exacte comme 4n² + 7n + 12 contient plusieurs termes. Lorsque n devient grand, n² domine n et les constantes. On retient donc Θ(n²).

1.3.2 Somme de complexités

Lorsque deux blocs sont exécutés successivement, leurs coûts s’additionnent. Asymptotiquement, le terme dominant l’emporte.

T(n) = T₁(n) + T₂(n)  ⇒ complexité dominée par max(T₁, T₂)

Deux boucles successives

Pour i allant de 0 à n-1 Faire
    Afficher T[i]
FinPour

Pour i allant de 0 à n-1 Faire
    somme ← somme + T[i]
FinPour

Chaque boucle est Θ(n). Le total vaut Θ(n) + Θ(n) = Θ(2n) = Θ(n). Deux boucles successives ne produisent donc pas automatiquement une complexité quadratique.

1.3.3 Produit de complexités

Lorsque l’exécution d’un bloc est répétée à l’intérieur d’un autre bloc, les coûts se multiplient. Cette règle explique les boucles imbriquées.

T(n) = nombre d’itérations externes × coût de chaque itération

Deux boucles imbriquées indépendantes

Pour i allant de 0 à n-1 Faire
    Pour j allant de 0 à n-1 Faire
        Afficher T[i], T[j]
    FinPour
FinPour

La boucle externe effectue n itérations. Pour chacune, la boucle interne effectue n itérations. Le corps est donc exécuté n × n = n² fois : Θ(n²).

1.3.4 Boucles successives

1.3.5 Boucles imbriquées

Le produit n’est valable directement que si le nombre d’itérations de la boucle interne est connu pour chaque itération externe. Lorsque les bornes dépendent de l’indice externe, il faut utiliser une somme.

Boucle triangulaire

Pour i allant de 0 à n-1 Faire
    Pour j allant de 0 à i Faire
        compteur ← compteur + 1
    FinPour
FinPour

1 + 2 + 3 + … + n = n(n + 1)/2 = Θ(n²)

1.3.6 Conditions

Pour une condition, le test est toujours exécuté, mais une seule branche est choisie. Dans le pire cas, on additionne le coût du test et celui de la branche la plus coûteuse.

Si condition Alors
    ParcourirTableau(T, n)      // Θ(n)
Sinon
    Afficher "Aucun traitement" // Θ(1)
FinSi

Dans le pire cas, la complexité est Θ(n). Dans le meilleur cas, elle peut être Θ(1). Une analyse de cas moyen nécessiterait de connaître la probabilité de chaque branche.

1.3.7 Appels de fonctions

Le coût d’un appel de fonction ne se limite pas à l’instruction d’appel. Il faut remplacer l’appel par la complexité de la fonction appelée, puis tenir compte du nombre de fois où elle est invoquée.

Appel d’une recherche linéaire dans une boucle

Pour i allant de 0 à n-1 Faire
    position ← Rechercher(T, n, i)
FinPour

Si Rechercher est Θ(n) et qu’elle est appelée n fois, le coût total est Θ(n × n) = Θ(n²). L’appel n’est donc pas une opération constante dans ce contexte.

1.3.8 Premières relations de récurrence

Une fonction récursive est souvent décrite par une relation de récurrence. L’étude détaillée des récurrences sera reprise au niveau avancé, mais quelques formes doivent déjà être reconnues.

Méthode générale d’analyse

1. Définir la taille des données et la ressource mesurée.

2. Identifier les instructions et opérations dominantes.

3. Découper l’algorithme en blocs successifs, conditionnels et répétitifs.

4. Déterminer le nombre d’exécutions de chaque bloc.

5. Additionner ou multiplier les coûts selon la structure.

6. Simplifier l’expression en conservant le terme dominant.

7. Préciser le cas étudié et la mémoire auxiliaire.

8. Vérifier la cohérence du résultat par un exemple ou une mesure.

1.4 Comparaison des ordres de grandeur

Les ordres de grandeur permettent de prévoir la capacité de passage à l’échelle. Une faible différence sur de petites données peut devenir considérable lorsque n augmente. Les constantes et les caractéristiques de la machine comptent en pratique, mais elles ne compensent généralement pas une différence majeure de croissance.

1.4.1 Complexité constante : O(1)

Le nombre d’opérations ne dépend pas de n. L’accès direct à une case de tableau par son indice, l’échange de deux variables ou la consultation du sommet d’une pile sont des exemples courants.

valeur ← T[indice]

Même si le tableau contient un million d’éléments, l’accès direct à une case reste constant dans le modèle RAM.

1.4.2 Complexité logarithmique : O(log n)

La taille du problème est divisée par un facteur constant à chaque étape. La base du logarithme n’a pas d’importance asymptotique, car deux logarithmes de bases différentes ne diffèrent que par un facteur constant.

• recherche dichotomique ;
• hauteur d’un arbre équilibré ;
• nombre de divisions successives par deux ;
• certaines opérations sur les tas et les arbres équilibrés.

1.4.3 Complexité linéaire : O(n)

Le travail augmente proportionnellement au nombre d’éléments. Les parcours complets, les calculs de somme et les recherches séquentielles en pire cas sont linéaires.

somme ← 0
Pour i allant de 0 à n-1 Faire
    somme ← somme + T[i]
FinPour

Lorsque n double, le travail est approximativement multiplié par deux.

1.4.4 Complexité quasi linéaire : O(n log n)

Cet ordre apparaît souvent lorsqu’un problème est divisé en niveaux logarithmiques et que chaque niveau traite au total n éléments. Les tris fusion, rapide en moyenne et par tas appartiennent à cette famille.

Pour de grandes tailles, O(n log n) reste nettement plus favorable que O(n²), tout en étant plus coûteux qu’un simple parcours linéaire.

1.4.5 Complexité quadratique : O(n²)

Une complexité quadratique apparaît fréquemment avec deux dimensions de taille n ou deux boucles imbriquées. Les tris élémentaires ont souvent un pire cas quadratique.

Pour i allant de 0 à n-1 Faire
    Pour j allant de 0 à n-1 Faire
        Traiter(T[i], T[j])
    FinPour
FinPour

Lorsque n double, n² est multiplié par quatre. Pour n multiplié par dix, le coût est multiplié par cent.

1.4.6 Complexité exponentielle : O(2ⁿ)

Une complexité exponentielle apparaît lorsqu’un algorithme explore de nombreuses combinaisons binaires ou crée deux sous-appels presque aussi grands à chaque niveau. Elle devient rapidement impraticable.

• Fibonacci récursif naïf ;
• exploration de tous les sous-ensembles ;
• certaines solutions par retour sur trace sans élagage ;
• problèmes combinatoires résolus par énumération exhaustive.

1.4.7 Complexité factorielle : O(n!)

La complexité factorielle correspond souvent à l’exploration de toutes les permutations de n éléments. Elle croît encore plus vite qu’une exponentielle de base fixe.

• énumération de tous les ordres possibles ;
• version exhaustive du problème du voyageur de commerce ;
• génération complète des permutations ;
• affectations combinatoires sans réduction de l’espace de recherche.

1.4.8 Tableau comparatif

1.4.9 Hiérarchie des croissances

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

Cette hiérarchie est asymptotique. Pour de petites tailles, un algorithme de meilleur ordre peut être plus lent à cause de constantes importantes ou d’une implémentation complexe. Cependant, lorsque n devient grand, l’ordre de croissance finit généralement par dominer.

1.4.10 Estimation sur une machine hypothétique

Supposons, uniquement pour illustrer les ordres de grandeur, qu’une machine exécute 100 millions d’opérations élémentaires par seconde. Les durées suivantes sont des estimations théoriques et ne représentent pas un programme réel.

Applications détaillées

Application 1 — Comparer plusieurs algorithmes de recherche

On souhaite rechercher plusieurs valeurs dans un tableau de n éléments. Deux stratégies sont envisagées :

• stratégie A : recherche séquentielle dans le tableau non trié ;
• stratégie B : tri initial du tableau, puis recherches dichotomiques.

Pour une seule recherche, le tri préalable peut être plus coûteux que la recherche séquentielle. Pour un grand nombre q de recherches sur le même tableau, le coût du tri est amorti et la stratégie B devient souvent préférable.

Application 2 — Analyse d’une double boucle

compteur ← 0
Pour i allant de 1 à n Faire
    Pour j allant de 1 à i Faire
        compteur ← compteur + 1
    FinPour
FinPour

La boucle interne s’exécute 1 fois pour i = 1, 2 fois pour i = 2, puis jusqu’à n fois. Le nombre exact d’incrémentations est :

1 + 2 + … + n = n(n + 1)/2

Le terme dominant est n²/2. La complexité est donc Θ(n²). Le facteur 1/2 n’est pas conservé dans la notation asymptotique.

Application 3 — Analyse d’un algorithme récursif simple

Fonction SommeRec(n : entier) : entier
Début
    Si n = 0 Alors
        Retourner 0
    Sinon
        Retourner n + SommeRec(n - 1)
    FinSi
Fin

Chaque appel crée un seul appel sur n - 1 et effectue un travail constant. La récurrence est T(n) = T(n - 1) + Θ(1). Elle se développe en n étapes : T(n) = Θ(n).

La comparaison montre que deux solutions peuvent avoir la même complexité temporelle tout en différant par leur consommation mémoire.

Application 4 — Estimer le temps pour différentes tailles

On compare trois algorithmes qui effectuent respectivement n, n log₂ n et n² opérations. On suppose un débit théorique de 10⁸ opérations par seconde.

Ces valeurs restent hypothétiques, mais elles illustrent la différence d’échelle. À n = 10⁷, le coût quadratique n’est plus raisonnable, tandis que le coût quasi linéaire reste de l’ordre de quelques secondes dans le modèle choisi.

Travaux dirigés

Pour chaque exercice, préciser la taille des données, la ressource mesurée, le cas étudié et la justification de la complexité.

Exercice 1 — Compter les opérations

Analyser le fragment suivant et donner le nombre exact d’additions et d’affectations en fonction de n.

• somme ← 0 ;
• pour i de 0 à n - 1 : somme ← somme + T[i].

Exercice 2 — Boucles successives ou imbriquées

Comparer deux algorithmes : le premier contient deux parcours successifs de n éléments ; le second contient deux boucles imbriquées de n itérations. Donner leur complexité et expliquer la différence.

Exercice 3 — Boucle logarithmique

Déterminer le nombre d’itérations et la complexité d’une boucle qui initialise i à 1 puis remplace i par 2 × i tant que i < n.

Exercice 4 — Condition et cas

Un algorithme effectue soit un affichage constant, soit un parcours complet d’un tableau selon une condition. Donner son meilleur cas et son pire cas.

Exercice 5 — Appels de fonctions

Une boucle de n itérations appelle à chaque tour une fonction de complexité Θ(log n). Déterminer la complexité totale.

Exercice 6 — Recherche répétée

On effectue q recherches dans un tableau de n éléments. Comparer la recherche séquentielle et la stratégie tri + dichotomie. Donner une condition qualitative pour préférer la seconde.

Exercice 7 — Récursivité

Analyser une fonction récursive qui appelle une seule fois F(n - 1) jusqu’à n = 0. Donner le nombre d’appels, le temps et la mémoire.

Exercice 8 — Identifier l’ordre dominant

Simplifier les expressions suivantes : 7n + 20 ; 3n² + 5n + 1 ; n log n + 100n ; 2ⁿ + n⁵.

Exercice 9 — Comparer les croissances

Classer O(n!), O(n), O(1), O(n²), O(log n), O(2ⁿ) et O(n log n) de la plus faible à la plus forte croissance.

Exercice 10 — Analyse à deux paramètres

Une matrice possède L lignes et C colonnes. Un algorithme visite chaque case une fois. Donner la complexité générale, puis le résultat lorsque L = C = n.

Corrigés indicatifs des travaux dirigés

Correction 1 — Compter les opérations

L’initialisation somme ← 0 produit une affectation. À chaque itération, somme ← somme + T[i] contient une addition et une affectation. Pour n itérations : n additions et n + 1 affectations pour somme, sans compter les opérations de contrôle de la boucle. L’ordre de grandeur est Θ(n).

Correction 2 — Boucles successives ou imbriquées

Deux parcours successifs coûtent Θ(n) + Θ(n) = Θ(n). Deux boucles imbriquées exécutent le corps n × n fois, donc Θ(n²). La différence vient de la composition : addition pour les blocs successifs, multiplication pour l’imbrication.

Correction 3 — Boucle logarithmique

i ← 1
TantQue i < n Faire
    i ← 2 × i
FinTantQue

Après k itérations, i = 2ᵏ. La boucle s’arrête lorsque 2ᵏ ≥ n, donc k ≥ log₂ n. Le nombre d’itérations est Θ(log n).

Correction 4 — Condition et cas

Si la branche constante est choisie, le meilleur cas est Θ(1). Si le parcours complet est exécuté, le pire cas est Θ(n). Le cas moyen dépend de la probabilité d’exécution de chaque branche.

Correction 5 — Appels de fonctions

La fonction Θ(log n) est appelée n fois. La règle du produit donne n × log n, soit Θ(n log n).

Correction 6 — Recherche répétée

La recherche séquentielle coûte Θ(qn). Le tri suivi de dichotomies coûte Θ(n log n + q log n). La seconde stratégie devient intéressante lorsque le tableau est réutilisé pour de nombreuses recherches et que le coût initial du tri peut être amorti.

Correction 7 — Récursivité

La chaîne d’appels est F(n), F(n - 1), …, F(0), soit n + 1 appels. Avec un travail constant par appel, le temps est Θ(n). La profondeur de pile est également n + 1, donc la mémoire auxiliaire est Θ(n).

Correction 8 — Ordre dominant

Correction 9 — Croissances

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

Correction 10 — Deux paramètres

Le nombre de cases est L × C, donc le parcours coûte Θ(LC). Si la matrice est carrée avec L = C = n, le coût devient Θ(n²). Il est préférable de conserver Θ(LC) lorsque les deux dimensions peuvent évoluer indépendamment.

Travail pratique proposé

Mesure expérimentale et validation d’une complexité

Le but est de comparer expérimentalement trois algorithmes : accès direct, recherche séquentielle et recherche dichotomique. Les mesures doivent être réalisées pour plusieurs tailles de tableaux et répétées afin de réduire les variations.

Étapes

1. Générer des tableaux de tailles croissantes, par exemple 10³, 10⁴, 10⁵ et 10⁶.

2. Mesurer un accès direct à une case, en répétant l’opération suffisamment de fois.

3. Mesurer une recherche séquentielle dans un cas favorable et un cas défavorable.

4. Trier les tableaux puis mesurer une recherche dichotomique.

5. Répéter chaque mesure et calculer une moyenne ou une médiane.

6. Présenter les résultats dans un tableau et éventuellement un graphique.

7. Comparer les tendances observées aux complexités théoriques.

8. Expliquer les écarts dus aux constantes, au cache, au langage et au bruit de mesure.

Synthèse du chapitre

• La taille des données doit être clairement définie avant toute analyse.
• Le temps, la mémoire, les comparaisons, les affectations et les appels récursifs sont des mesures complémentaires.
• La notation O donne une borne supérieure, Ω une borne inférieure et Θ un ordre exact à facteur constant près.
• Meilleur cas, cas moyen et pire cas décrivent des familles d’entrées, pas des notations asymptotiques.
• Les coûts des blocs successifs s’additionnent ; les coûts des répétitions imbriquées se multiplient ou se somment selon leurs bornes.
• Le coût d’une fonction appelée doit être intégré à celui de l’algorithme appelant.
• Les complexités logarithmiques et quasi linéaires passent bien à l’échelle ; les complexités exponentielles et factorielles deviennent rapidement impraticables.
• Une analyse complète précise la ressource, la taille, le cas, le temps et la mémoire auxiliaire.
• L’expérimentation complète l’analyse théorique, mais ne la remplace pas.

Glossaire

Auto-évaluation