MP2I — 2023 – 2024 Fiche Memo Analyse de complexité - Gérard Rozsavolgyi LIV, Valbonne
Notation asymptotique
Si 𝑓(𝑛) = 𝒪(𝑔(𝑛)) et si 𝑓(𝑛) = 𝛺(𝑔(𝑛)), alors on note 𝑓(𝑛) = 𝛩(𝑔(𝑛)).
On a besoin d’outils mathématiques pour analyser de la complexité temporelle ou spatiale des
algorithmes. Cette complexité s’exprime en fonction de la taille de l’entrée, également appelée
taille de l’instance, c’est-à-dire en fonction de la taille des données qui définissent l’instance 𝑓(𝑛) 𝑓(𝑛) = 2𝑛 𝑓(𝑛) = 𝑛2 𝑓(𝑛) = 𝑛 log2 𝑛
du problème.
Définition 1 – taille de l’entrée
Notons ℐ une instance de notre problème. Sa taille, notée |ℐ|, est le nombre de bits
nécessaires à la représentation de l’instance.
Par exemple, si le problème à résoudre consiste à trier les 𝑛 éléments d’un tableau et que
chacun de ces éléments sont des nombres représentés sur 8 octets, alors la taille de l’instance
est 8 𝑛 octets, soit 64 𝑛 bits. Habituellement un ordre de grandeur de la taille de l’instance est
suffisant. À la fois pour exprimer la taille d’une instance ou pour exprimer une complexité en
temps ou en mémoire, nous pourrons nous satisfaire du comportement asymptotique de la
fonction qui décrit cette taille ou complexité. Pour cela, nous utilisons couramment la nota-
tion grand O de Landau.
Définition 2 – notation asymptotique 𝒪
𝒪(𝑔(𝑛)) est l’ensemble des fonctions 𝑓(𝑛) pour lesquelles il existe deux constantes 𝑓(𝑛) = 𝑛
positives 𝑐 > 0 et 𝑛0 ≥ 0 telles que, pour tout 𝑛 ≥ 𝑛0 :
0 ≤ 𝑓(𝑛) ≤ 𝑐 ⋅ 𝑔(𝑛).
Remarque 3 – abus de notation 𝑓(𝑛) = log2 𝑛
n note ici 𝑓(𝑛) = 𝒪(𝑔(𝑛)) en commettant un petit abus de notation où on utilise une 𝑛
égalité (=) plutôt que l’appartenance (𝑓(𝑛) ∈ 𝒪(𝑔(𝑛))). Ainsi, pour notre problème du
tri de 𝑛 nombres, nous dirons simplement que la taille de l’instance est 𝒪(𝑛) (puisque
64 𝑛 = 𝒪(𝑛)). Complexité en temps (ou temps d’exécution)
La notation 𝒪 permet d’exprimer des majorants asymptotiques sur la croissance d’une fonc- Là encore, un ordre de grandeur, exprimé par l’usage de la notation asymptotique 𝒪 ou 𝛩
tion. Nous donnons ci-après la définition de la notation 𝛺 qui exprime la notion de minorant sera souvent suffisant et plus simple à établir que la complexité exacte du temps d’exécution.
asymptotique, ansi que la notation plus précise 𝛩 : De façon habituelle, nous exprimons une borne sur le temps d’exécution dans le cas le plus
défavorable : c’est la borne au pire des cas. Une telle borne apporte une garantie sur le temps
Définition 4 – notation asymptotique 𝛺 et 𝛩 d’exécution, quelle que soit l’entrée.
𝛺(𝑔(𝑛)) est l’ensemble des fonctions 𝑓(𝑛) pour lesquelles il existe deux constantes Définition 5 – temps d’exécution au pire des cas
positives 𝑐 > 0 et 𝑛0 ≥ 0 telles que, pour tout 𝑛 ≥ 𝑛0 :
n algorithme 𝒜 s’exécute en temps 𝑓(𝑛) au pire des cas, si le temps d’exécution pour
𝑐 ⋅ 𝑔(𝑛) ≤ 𝑓(𝑛). une entrée quelconque de taille 𝑛 est au plus 𝑓(𝑛).
MP2I — 2023 – 2024 Fiche Memo Analyse de complexité - Gérard Rozsavolgyi LIV, Valbonne
Afin d’évaluer les temps d’exécution de nos algorithmes, de façon indépendantes d’un lan- Complexité en mémoire (ou espace mémoire).
gage et d’une machine, nous utilisons le modèle de calcul nommé modèle RAM.
L’espace mémoire utilisé pendant l’exécution d’un algorithme est une ressource dont on peut
Une Random Access Machine (RAM, machine à accès aléatoire) est un modèle abstrait d’or- souhaiter un usage limité. On s’y intéressera notament lors de l’usage de la programmation
dinateur où chaque opération simple (opérations arithmétiques, comparaisons, affectation, dynamique. Tout comme le temps d’exécution, nous pouvons être amenés à analyser la com-
appel de fonction, instruction de contrôle if, ...) ne demande qu’une seule étape de calcul. plexité en mémoire d’un algorithme. Il s’agit dès lors de quantifier, notamment au travers
On parle alors de temps constant (qui est noté 𝒪(1)). De plus, nous supposerons que chaque l’usage de la notation 𝒪, l’espace mémoire utilisé dans le pire des cas.
accès mémoire ne demande également qu’un temps constant. Par contre, les boucles ne s’exé-
cutent habituellement pas en temps constant puisqu’il s’agit de la composition de plusieurs
opérations.
Pour analyser son temps d’exécution, regardons de façon un peu plus précise la façon dont
est composé un algorithme. Une séquence d’instructions p;q demande un temps égal à la
somme des temps pris pour exécuter p puis q. Le temps nécessaire (au pire des cas) à une
conditionnelle Si condition alors p sinon q est borné par le maximum des temps pour
exécuter p et q, auquel il faut ajouter le temps pour évaluer la condition cond. Pour une boucle
pour ou tant que il faut évaluer le nombre d’itérations de la boucle et le multiplier par le coût
des instructions situées à l’intérieur de celle-ci. L’évaluation du nombre d’itérations d’une
boucle tant que est souvent plus délicate, mais on peut parfois s’éviter quelques calculs grâce
à l’analyse au pire des cas et à l’utilisation de la notation asymptotique 𝒪. En toute rigueur,
il faut également tenir compte du temps d’exécution induit par l’évaluation de la condition à
chaque itération de la boucle.
Lors de l’analyse du temps d’exécution d’un algorithme, si nous notons 𝑛 la taille de l’entrée,
il est courant d’établir des complexités appartenant à ces classes de fonctions :
— 𝒪(1), que l’on nomme temps constant ;
— 𝒪(log 𝑛), que l’on nomme temps logarithmique ;
— 𝒪(𝑛), que l’on nomme temps linéaire ;
— 𝒪(𝑛 log 𝑛), que l’on nomme temps linéarithmique ;
— 𝒪(𝑛2 ), que l’on nomme temps quadratique ;
— 𝒪(𝑛3 ), que l’on nomme temps cubique ;
— 𝒪(𝑛𝑐 ), pour une certaine constante 𝑐 ≥ 1, que l’on nomme temps polynomial ;
— 𝒪(2𝑐⋅𝑛 ), pour une certaine constante 𝑐 ≥ 1, que l’on nomme temps exponentiel.
Il existe également des fonctions dont la croissance est entre polynomiale et exponentielle et
qui sont nommées quasi-polynomiale ou sous-exponentielle. Nous n’aurons pas l’occasion de
les rencontrer cette année.
La figure ci-dessus donne la représentation de quelques fonctions usuelles que nous aurons
l’occasion de rencontrer au gré des exercices et des exemples. Bien entendu, lorsque cela
sera possible, nous viserons à concevoir des algorithmes ayant un temps d’exécution polyno-
mial plutôt qu’un temps exponentiel. Néanmoins, nous aurons l’occasion de rencontrer des
exemples de problèmes pour lesquels nous ne connaissons pas d’algorithmes polynomiaux.