I.But d'un calcul de complexité

L'objectif premier d'un calcul de complexité algorithmique est de pouvoir comparer l’efficacité d’algorithmes résolvant le même problème. Dans une situation donnée, cela permet donc d'établir lequel des algorithmes disponibles est le plus optimal.

Si nous devons par exemple trier une liste de nombres, est-il préférable d'utiliser un tri fusion ou un tri à bulles ?

Ce type de question est primordial, car pour des données volumineuses la différence entre les durées d'exécution de deux algorithmes ayant la même finalité peut être de l'ordre de plusieurs jours.

Pour faire cela nous chercherons à estimer la quantité de ressources utilisée lors de l'exécution d'un algorithme.

Les règles que nous utiliserons pour comparer et évaluer les algorithmes devront respecter certaines contraintes très naturelles. On requerra principalement qu'elles ne soient pas tributaires des qualités d'une machine ou d'un choix de technologie.

En particulier, cela signifiera que ces règles seront indépendantes des facteurs suivants :

du langage de programmation utilisé pour l'implémentation.
du processeur de l'ordinateur sur lequel sera exécuté le code.
de l'éventuel compilateur employé.


	Le premier réflexe qui consisterait à coder les algorithmes sur un ordinateur puis à comparer leurs durées d’exécution n’est donc pas le bon. Il ne vérifie en effet pas les contraintes précédentes et ne permet donc pas de juger leurs qualités intrinsèques.

Nous allons donc effectuer des calculs sur l’algorithme en lui même, dans sa version "papier". Les résultats de ces calculs fourniront une estimation du temps d’exécution de l’algorithme, et de la taille mémoire occupée lors de son fonctionnement.

Le premier à avoir systématisé le fait de calculer la complexité d’un algorithme est Donald Knuth (1938-) dans sa série d’ouvrage "The Art of Computer Programming".

Pour beaucoup d'informaticiens ces livres constituent la référence ultime en algorithmique. Sans surprise ils sont écrits par un mathématicien.

II. Les deux types de complexité

On distinguera deux sortes de complexité, selon que l'on s'intéresse au temps d'exécution ou à l'espace mémoire occupé.

2.1. Complexité en temps

Réaliser un calcul de complexité en temps revient à décompter le nombre d’opérations élémentaires (affectation, calcul arithmétique ou logique, comparaison…) effectuées par l’algorithme.

Pour rendre ce calcul réalisable, on émettra l'hypothèse que toutes les opérations élémentaires sont à égalité de coût. En pratique ce n'est pas tout à fait exact mais cette approximation est cependant raisonnable.

On pourra donc estimer que le temps d'exécution de l'algorithme est proportionnel au nombre d’opérations élémentaires.

2.2. Complexité en espace

La complexité en espace est quand à elle la taille de la mémoire nécessaire pour stocker les différentes structures de données utilisées lors de l'exécution de l'algorithme.


	On s’intéressera peu à cette problématique dans la suite du cours, on se contentera juste de l'évoquer de temps à autre.

2.3. De quoi est fonction la complexité ?

La complexité d'un algorithme va naturellement être fonction de la taille des données passées en paramètres. Cette dépendance est logique, plus ces données seront volumineuses, plus il faudra d'opérations élémentaires pour les traiter.

Par exemple, pour un algorithme de tri cette taille sera le nombre de valeurs à trier.

On supposera de plus que nos algorithmes n'ont qu'une donnée, dont la taille est nécessairement un entier naturel. La complexité en temps d’un algorithme sera donc une fonction de $ℕ$ dans $ℝ^{+}$ . Nous la noterons en général $T$ (pour Time).

Souvent la complexité dépendra aussi de la donnée en elle même et pas seulement de sa taille. En particulier la façon dont sont réparties les différentes valeurs qui la constituent.

Imaginons par exemple que l'on effectue une recherche séquentielle d’un élément dans une liste non triée. Le principe de l'algorithme est simple, on parcourt un par un les éléments jusqu'à trouver, ou pas, celui recherché. Ce parcours peut s’arrêter dès le début si le premier élément est "le bon". Mais on peut également être amené à parcourir la liste en entier si l’élément cherché est en dernière position, ou même n'y figure pas. Le nombre d'opération élémentaires effectuées dépend donc non seulement de la taille de la liste, mais également de la répartition de ses valeurs.

Cette remarque nous conduit à préciser un peu notre définition de la complexité en temps. En toute rigueur, on devra en effet distinguer trois formes de complexité en temps :

la complexité dans le meilleur des cas : c'est la situation la plus favorable, qui correspond par exemple à la recherche d'un élément situé à la première postion d'une liste, ou encore au tri d'une liste déjà triée.
la complexité dans le pire des cas : c'est la situation la plus défavorable, qui correspond par exemple à la recherche d'un élément dans une liste alors qu'il n'y figure pas, ou encore au tri par ordre croissant d'une liste triée par ordre décroissant.
la complexité en moyenne : on suppose là que les données sont réparties selon une certaine loi de probabilités.

On calculera le plus souvent la complexité dans le pire des cas, car elle est la plus pertinente. Il vaut mieux en effet toujours envisager le pire.


	Lors d'un calcul de complexité en moyenne, on utilise en général une loi uniforme, c’est-à-dire que l’on suppose que toutes les tirages de données se font avec la même probabilité. Les calculs qui en résultent sont souvent complexes, nous ne nous attarderons pas sur ce sujet.

Dernière chose importante à prendre en considération, si la donnée en elle même est un nombre entier, la façon de le représenter influera beaucoup sur l’appréciation de la complexité.

Par exemple, si $n = 4096$ on peut considérer que la taille de $n$ est :

la valeur de $n$ en elle même, façon la plus naturelle de voir les choses, i.e. $4096$
le nombre de chiffres que comporte l'écriture en binaire de $n$ , i.e. $13$
le nombre de chiffres que comporte l'écriture en décimal de $n$ , i.e. $4$

Vu la finalité informatique de nos algorithmes, nous choisirons souvent dans ces cas là le nombre de chiffres dans l'écriture binaire de l'entier $n$ .


	Cette question se posera en particulier lors de l'étude de la complexité des algorithmes arithmétiques (test de primalité, algorithme d'Euclide, etc.).

2.4. Quelques calculs de sommes usuelles

Nous allons dans cette sous-partie énoncer et démontrer quelques égalités bien connues relatives à certaines sommes. Elles nous seront fort utiles lors de nos calculs de complexités.

Somme de n termes constants

Soit $n$ élément de $ℕ^{*}$ et $c$ élément de $ℝ$ .

On a

\sum_{k = 1}^{n} c = n \times c

Démonstration

Cette égalité est triviale puisque l'on a $n$ termes dans cette somme, chacun d'eux étant égal à $c$ .

Somme des n premiers entiers

Soit $n$ élément de $ℕ^{*}$ .

On a

\sum_{k = 1}^{n} k = \frac{n \times (n + 1)}{2}

Démonstration

Effectuons la preuve de ce résultat par récurrence :

Initialisation : pour $n = 1$ , on a $\sum_{k = 1}^{1} k = 1$ qui est bien égal à $\frac{1 \times (1 + 1)}{2} = 1$ .
Hérédité : supposons que pour un $n \geq 1$ l'égalité soit vérifiée. Calculer une somme avec un indice allant de $1$ à $n + 1$ revient à calculer cette même somme avec un indice allant de $1$ à $n$ , puis à rajouter le terme d'indice $n + 1$ . On a ainsi $\sum_{k = 1}^{n + 1} k = \sum_{k = 1}^{n} k + n + 1$ , et donc d'après l'hypothèse de récurrence $\sum_{k = 1}^{n + 1} k = \frac{n \times (n + 1)}{2} + n + 1$ . Une simple mise au même dénominateur et une petite factorisation prouvent ensuite que $\sum_{k = 1}^{n + 1} k = \frac{(n + 1) \times (n + 2)}{2}$ . Ce qui est bien l'égalité au rang $n + 1$ .
On conclut alors en appliquant le principe de récurrence.

L'auteur ne peut s'empécher une petite digression en proposant une preuve sans mots du résultat précédent :

Pour d'autres démonstrations du même genre, consulter l'excellent livre de Roger B. Nelsen, "Proofs Without Words".

Somme des n premiers carrés d'entiers

Soit $n$ élément de $ℕ^{*}$ .

On a

\sum_{k = 1}^{n} k^{2} = \frac{n \times (n + 1) \times (2 n + 1)}{6}

Démonstration

Cette égalité se démontre également par récurrence, en utilisant les mêmes arguments que lors de la preuve précédente. Nous laissons le lecteur y réfléchir.

Somme des n premiers termes d'une suite géométrique

Soit $n$ élément de $ℕ^{*}$ et $q$ élément de $ℝ$ .

Si $q \neq 1$ , on a

\sum_{k = 0}^{n} q^{k} = \frac{1 - q^{n + 1}}{1 - q}


	A noter que si $q = 1$ , on retrouve la somme de termes constants.

Démonstration

Là aussi une simple récurrence prouve ce résultat.

2.5. Rappels sur la fonction logarithme

La fonction logarithme jouant un rôle important dans la suite de ce cours, nous allons consacrer cette sous-partie à en rappeler sa définition et ses propriétés classiques.

Définition

Soit $a$ élement de $ℝ_{+}^{*}$ tel que $a \neq 1$ .

Le logarithme de base $a$ , noté $\log_{a}$ , est l'unique fonction définie sur $ℝ_{+}^{*}$ vérifiant les deux propriétés suivantes :

$\log_{a} (a) = 1$ .
$\forall x, y > 0, \log_{a} (x y) = \log_{a} (x) + \log_{a} (y)$ .

Il existe ainsi une infinité de fonctions logarithmes différentes, autant que de réels strictement positifs différents de $1$ . En voici les plus courantes.

Example 1.1. Fonctions logarithmes usuelles

Si $a = e$ , il s'agit du logarithme népérien, noté également $\ln$ .
Si $a = 2$ , il s'agit du logarithme binaire.
Si $a = 10$ , il s'agit du logarithme décimal.

Présentons maintenant les principales formules de calculs de la fonction logarithme.

Règles opératoires

Soit $a$ élement de $ℝ_{+}^{*}$ tel que $a \neq 1$ .

$\log_{a} (1) = 0$ .
$\forall x > 0, \log_{a} (\frac{1}{x}) = - \log_{a} (x)$ .
$\forall x, y > 0, \log_{a} (\frac{x}{y}) = \log_{a} (x) - \log_{a} (y)$ .
$\forall x > 0, \forall n \in ℕ, \log_{a} (x^{n}) = n \times \log_{a} (x)$ .

Même si ce n'est bien sûr pas l'objet de ce cours, présentons quelques éléments de preuve de ces formules. Cela permettra au lecteur de bien se familiariser avec cette fonction.

Démonstration

Si l'on applique l'égalité définissant le logarithme avec $x = 1$ et $y = 1$ , on obtient $\log_{a} (1) = 2 \times \log_{a} (1)$ . Ce qui prouve bien sûr que $\log_{a} (1) = 0$ .
Appliquons cette même égalité avec cette fois $x$ et $\frac{1}{x}$ . Il vient $\log_{a} (1) = \log_{a} (x) + \log_{a} (\frac{1}{x})$ , ce qui prouve le résultat.
Utilisons maintenant l'égalité avec $x$ et $\frac{1}{y}$ . On a alors $\log_{a} (\frac{x}{y}) = \log_{a} (x) + \log_{a} (\frac{1}{y})$ . Il ne reste alors plus qu'à utiliser la seconde formule pour conclure.
Cette dernière égalité se prouve sans soucis par récurrence en utilisant la définition du logarithme.

La propriété suivante montre que toutes les fonctions logarithmes sont proportionnelles entre elles.

Relation de proportionnalité entre les fonctions logarithmes

Soient $a, b$ élements de $ℝ_{+}^{*}$ tel que $a \neq 1$ et $b \neq 1$ .

On a la relation suivante entre les fonctions $\log_{a}$ et $\log_{b}$ :

\forall x > 0, \log_{a} (x) = \frac{\log_{b} (x)}{\log_{b} (a)}

Démonstration

On constate sans difficultés que les fonctions $\log_{a} (x)$ et $\frac{\log_{b} (x)}{\log_{b} (a)}$ vérifient toutes les deux les propriétés définissant le logarithme de base $a$ . D'après l'unicité de ce dernier elles sont donc égales.

La fonction logarithme permet entre autres d'estimer le nombre de chiffres que comporte l'écriture d'un entier dans une base donnée.

Propriété

Soit $a \in ℕ$ , $a \geq 2$ .

Tout entier naturel $x$ peut s'écrire dans la base $a$ comme une somme de puissances de $a$

x = c_{n} a^{n} + c_{n - 1} a^{n - 1} + . . . + c_{1} a^{1} + c_{0}

Le nombre de chiffres $p$ (i.e. $n + 1$ avec les notations précédentes) de $x$ vérifie alors

p - 1 \leq \log_{a} (x) < p


	Le résultat précédent signifie que $\log_{a} (x)$ est approximativement égal au nombre de chiffres de $x$ dans la base $a$ .

Démonstration

Il suffit de constater que si $x$ a $p$ chiffres dans son écriture en base $a$ alors $a^{p - 1} \leq x < a^{p}$ , puis d'appliquer la fonction logarithme de base $a$ aux trois membres de cette inégalité.

Le lecteur n'est pas sans savoir qu'une fonction très liée au logarithme est l'exponentielle. En voici sa définition précise.

Définition

Soit $a$ élement de $ℝ_{+}^{*}$ .

L'exponentielle de base $a$ , noté $\exp_{a}$ , est l'unique fonction définie sur $ℝ$ vérifiant les deux propriétés suivantes :

$\exp_{a} (1) = a$ .
$\forall x, y > 0, \exp_{a} (x + y) = \exp_{a} (x) \times \exp_{a} (y)$ .

On la note également $\exp_{a} (x) = a^{x}$ .


	Avec une variable entière, cette fonction exponentielle coïncide avec la fonction puissance usuelle, c'est-à-dire que $\forall n \in ℕ, a^{n} = a \times a \times . . . \times a$ .

Théorème

Soit $a$ élement de $ℝ_{+}^{*}$ tel que $a \neq 1$ .

La fonction $\log_{a}$ est bijective de $ℝ_{+}^{*}$ dans $ℝ$ , et la fonction $\exp_{a}$ est bijective de $ℝ$ dans $ℝ_{+}^{*}$ . Ces deux fonctions sont de plus réciproques l'une de l'autre, ce qui signifie en particulier que :

$\forall x > 0, a^{\log_{a} (x)} = x$ .
$\forall x \in ℝ, \log_{a} (a^{x}) = x$ .

Présentons la représentation graphique d'une fonction logarithme et de sa fonction réciproque. Nul doute que le lecteur connaît déjà l'allure de ces courbes.

Figure 1.1. Le logarithme binaire et sa fonction réciproque

En rouge la courbe du logarithme binaire et en vert celle de sa fonction réciproque, l'exponentielle binaire. Ces deux courbes sont symétriques par rapport à la droite tracée en bleu d'équation $y = x$ .

2. Premiers calculs de complexité : algorithmes itératifs

Nous allons dans cette partie effectuer nos premiers calculs de complexité. Nous ne traiteront ici que le cas des algorithmes itératifs, ceux récursifs seront étudiés dans le second chapitre de ce cours.

Avant de commencer, rappelons notre hypothèse de base : toutes les opérations élémentaires sont à égalité de côut. Cela permet donc d'affirmer que le temps d'exécution est proportionnel au nombre de ces opérations élémentaires.

Les algorithmes étudiés seront présentés en Python. Comme remarqué précédemment, ce choix n'influe bien sûr pas sur leur complexité.

3.1. Algorithmes sans structures de contrôle

Pour mémoire, une structure de contrôle est une structure itérative ou une structure conditionnelle. Si un algorithme n'en comporte pas, pour évaluer sa complexité il suffit juste de dénombrer le nombre d’opérations successives qu'il possède.

Example 1.2. Une fonction de conversion

La fonction suivante convertit un nombre de secondes en heures, minutes, secondes :

def conversion(n):
    h = n // 3600
    m = (n - 3600*h) // 60
    s = n % 60
    return h,m,s

Cet algorithme ne comporte pas de structures de contrôle.

On peut dénombrer cinq opérations arithmétiques et trois affectations. On a donc $T (n) = 8$ .

Le cas des structures conditionnelles

En présence d'une structure conditionnelle, il faut commencer par dénombrer le nombre de conditions du test.

On décompte ensuite le nombre d’opérations élémentaires de chacune des alternatives, et l'on prend le maximum de ce décompte afin d'obtenir la complexité dans le pire des cas.

Example 1.3. Un calcul de puissance

La fonction suivante calcule ${(- 1)}^{n}$ sans effectuer de produit mais en utilisant un test avec une alternative :

def puissanceMoinsUn(n):
   if n%2==0:
      res = 1
   else:
      res = -1
   return res

Le test de la conditionnelle comporte une opération arithmétique et une comparaison.

Chaque alternative possède une affectation, ainsi le maximum des coûts des différentes alternatives est de un.

On a donc $T (n) = 3$ .

Le cas des structures itératives

Il y a deux possibilités lors du traitement d'une structure itérative.

Si chaque itération comporte le même nombre d'opérations élémentaires, pour évaluer la complexité il suffit de multiplier le nombre d'itérations par le nombre d'opérations de chacune d'elles.

Si chaque itération ne possède pas le même nombre d'opérations, il faudra alors distinguer ces itérations, c'est-à-dire évaluer la complexité de chacune d'elle puis en faire la somme.


	Le nombre d'opérations élémentaires d'une itération inclut bien sûr l'évaluation des tests d'entrée de boucle.

Example 1.4. Calcul itératif de la somme des $n$ premiers entiers

Cette fonction utilise une structure for pour calculer la somme des $n$ premiers entiers :

def sommeEntiers(n):
    somme = 0
    for i in range(n+1):
        somme += i
    return somme

Ici chaque itération a le même nombre d’opérations, à savoir cinq : deux affections (i et somme), deux additions (i et somme) et une comparaison.

On a d'autre part une affectation, lors de l'initialisation de la variable somme.

Ainsi $T (n) = 5 n + 1$ .

Une autre méthode pour calculer cette somme est d'utiliser une formule explicite.

Example 1.5. Calcul de la somme des $n$ premiers entiers à l'aide d'une formule explicite

Cette fonction utilise l'une des formules présentées dans la sous-partie 1.4 :

def sommeEntiersBis(n):
   return n*(n+1)//2

Cet algorithme ne comporte pas de structures de contrôle, il est juste constitué de trois opérations arithmétiques.

On a donc $T (n) = 3$ .

Les deux algorithmes précédents nous offrent un premier exemple de comparaison d'efficacité puisqu'ils répondent tous deux à la même question.

La conclusion est ici évidente, il vaut mieux utiliser le second.

3.2. Premiers exemples un peu plus élaborés

On va dans cette sous-partie se pencher sur des situations un peu plus délicates avec le calcul de la complexité des algorithmes de recherche séquentielle et du tri par sélection.

Example 1.6. Recherche séquentielle d'un élément dans une liste

La fonction suivante recherche l'élément x dans la liste l. Si x appartient à l elle retourne l'indice de la première occurence de x dans l, sinon elle retourne -1.

Son fonctionnement est simple, les éléments de la liste sont parcourus un par un grâce à une structure for :

def recherche(l,x):
    for i in range(len(l)):
        if l[i]==x:
            return i
    return -1

Ici la complexité sera fonction de la longueur de la liste, que nous noterons $n$ .

Dans le pire des cas l'élément recherché n'appartient pas à la liste, et il a fallu la parcourir en entier pour arriver à cette conclusion, c'est-à-dire effectuer $n$ itérations.

De plus, chaque itération comporte le même nombre d'opérations élémentaires, à savoir une affectation, une addition et deux comparaisons.

On a donc $T (n) = 4 n$ .

L'exemple qui suit contient une imbrication de boucles, il demande donc un peu plus de vigilance.

Example 1.7. Tri par sélection

Rappelons, voir cours 1ADS, que le tri par sélection est un algorithme itératif réalisant le tri par ordre croissant d'une liste.

Il consiste dans un premier temps à mettre à la première place le plus petit élément de la liste, puis à la seconde place le deuxième plus petit élément, etc.

Sa description est la suivante :

Rechercher dans la liste la plus petite valeur et la permuter avec le premier élément de la liste.
Rechercher ensuite la plus petite valeur à partir de la deuxième case et la permuter avec le second élément de la liste.
Et ainsi de suite jusqu’à avoir parcouru toute la liste.

En voici son implémentation en Python :

def triSelection(l):
    for i in range(len(l)-1):
        indMini=i
        for j in range(i+1,len(l)):
            if l[j]<l[indMini]:
                indMini=j
        l[i],l[indMini]=l[indMini],l[i]

Ici aussi la complexité sera fonction de la longueur $n$ de la liste.

Le pire des cas correspond à une liste triée par ordre décroissant.

Chaque itération de la boucle principale, la plus externe, ne possède pas le même nombre d'opérations. Il y a toujours les six mêmes (les opérations concernant la variable i, l'initialisation de indMini et l'échange des valeurs), plus les opérations dues à la boucle la plus interne, qui elles sont en nombre variable.

La boucle interne a elle par contre le même nombre d'opérations par itération, à savoir cinq.

Le nombre d'itérations de la boucle interne varie d'une itération à l'autre de la boucle externe :

à la première itération de la boucle externe la variable i vaut $0$ et la boucle interne effectue donc $n - 1$ itérations.
à la seconde itération de la boucle externe la variable i vaut $1$ et la boucle interne effectue donc $n - 2$ itérations.
etc.

La complexité de cet algorithme sera alors égale à la somme du nombre d'opérations de chaque itération de la boucle externe. A savoir

\begin{array}{l} 6 + 5 \times (n - 1) + 6 + 5 \times (n - 2) + . . . + 6 + 5 \times 1 & = & \sum_{i = 1}^{n - 1} (6 + 5 \times i) \\ = & 6 \times (n - 1) + 5 \times \sum_{i = 1}^{n - 1} i \\ = & 6 \times (n - 1) + 5 \times \frac{(n - 1) \times n}{2} \\ = & \frac{5}{2} n^{2} + \frac{7}{2} n - 6 \end{array}

Lors de ce calcul, on a utilisé la valeur d'une somme de termes constants et celle de la somme des premiers entiers (voir sous-partie 1.4).

Conclusion, la complexité dans le pire des cas du tri par sélection est $T (n) = 2 n^{2} + 3 n - 5$ .

Remarques sur la précision à apporter

A la vue des calculs précédents, on comprend bien que donner un résultat précis va vite devenir impossible et inutile.

Comment par exemple ne pas oublier une opération élémentaire dans un algorithme de quelques centaines de ligne ?

D'autre part, que la complexité d'un algorithme soit égale à $4 n + 2$ ou $3 n + 5$ ne change pas fondamentalement sa performance.

On va donc plutôt s’intéresser à une complexité asymptotique, qui sera une approximation du nombre d’opérations élémentaires.

Cela nous permettra d’avoir des calculs gérables sans pour autant perdre en pertinence.

Comportement asymptotique des fonctions de référence

Le but de cette partie va être de comparer les complexités calculées avec des fonctions de référence (puissance, logarithme, exponentielle, etc.). Il faudra préalablement introduire quelques notations classiques des études de fonctions.

3.3. Notations asymptotiques

Dans cette sous-partie de généralités, on supposera que toutes les fonctions considérées sont définies sur $ℕ$ et à valeurs dans $ℝ_{+}$ .

Dans notre contexte ce n'est bien sûr pas une contrainte, car les fonctions exprimant une complexité sont nécessairement positives.

Les définitions suivantes permettent de comparer le comportement à l'infini de deux fonctions définies sur $ℕ$ . Plus précisément, il s'agit de critères pour affirmer qu'une fonction en domine une autre, ou au contraire est du même ordre de grandeur, voir même équivalente.

Notion de grand O

Borne supérieure asymptotique

On dit qu’une fonction $f$ est un grand O d’une fonction $g$ si et seulement si

\exists c > 0, \exists n_{0} > 0 tel que \forall n > n_{0}, f (n) < c \times g (n)

On note alors $f (n) = Ο (g (n))$ .

Moralement, cela signifie qu'à partir d'un certain rang la fonction $f$ est majorée par une constante fois la fonction $g$ . Il s'agit donc d'une situation de domination de la fonction $f$ par la fonction $g$ .

Figure 1.2. Interprétation graphique de la notion de grand O

A partir du rang $n_{0}$ , la courbe de $f$ est au dessous de celle de $c$ fois $g$ .

Example 1.8. Quelques relations grand O

Si $T (n) = 4$ alors $T (n) = Ο (1)$ . Pour le prouver, prendre par exemple $c = 5$ et $n_{0} = 0$ .
Si $T (n) = 3 n + 2$ alors $T (n) = Ο (n)$ . Pour le prouver, prendre par exemple $c = 4$ et $n_{0} = 2$ .
Si $T (n) = 2 n + 3$ alors $T (n) = Ο (n^{2})$ . Pour le prouver, prendre par exemple $c = 3$ et $n_{0} = 1$ .


	Que le lecteur prenne bien le temps de comprendre précisément l'exemple précédent.

3.4. Notion de grand Oméga

Borne inférieure asymptotique

On dit qu’une fonction $f$ est un grand Oméga d’une fonction $g$ si et seulement si

\exists c > 0, \exists n_{0} > 0 tel que \forall n > n_{0}, c \times g (n) < f (n)

On note alors $f (n) = Ω (g (n))$ .

Cette fois-ci, à partir d'un certain rang la fonction $f$ est minorée par une constante fois la fonction $g$ . Il s'agit donc d'une situation de domination de la fonction $g$ par la fonction $f$ .


	Le lecteur se persuadera sans peine que $f (n) = Ω (g (n)) \Leftrightarrow g (n) = Ο (g (n))$

Figure 1.3. Interprétation graphique de la notion de grand Oméga

A partir du rang $n_{0}$ , la courbe de $f$ est au dessus de celle de $c$ fois $g$ .

Example 1.9. Quelques relations grand Oméga

Si $T (n) = 4$ alors $T (n) = Ω (1)$ .
Si $T (n) = 4 n + 2$ alors $T (n) = Ω (n)$ .
Si $T (n) = 4 n^{2} + 1$ alors $T (n) = Ω (n)$ .


	Nous laissons cette fois-ci le lecteur trouver lui-même les "bonnes" constantes.

3.5. Notion de grand Théta

Borne asymptotique

On dit qu’une fonction $f$ est un grand Théta d’une fonction $g$ si et seulement si

\exists c_{1} > 0, \exists c_{2} > 0, \exists n_{0} > 0 tel que \forall n > n_{0}, c_{1} \times g (n) < f (n) < c_{2} \times g (n)

On note alors $f (n) = Θ (g (n))$ .

Cette situation combine les deux précédentes, à partir d'un certain rang la fonction $f$ est encadrée par des multiples de la fonction $g$ . Cela signifie que les fonctions $f$ et $g$ sont du même ordre de grandeur.


	Il est facile de voir que $f (n) = Θ (g (n)) \Leftrightarrow (f (n) = Ο (g (n)) et f (n) = Ω (g (n)))$

Figure 1.4. Interprétation graphique de la notion de grand Théta

A partir du rang $n_{0}$ , la courbe de $f$ est entre celle de $c_{1}$ fois $g$ et celle de $c_{2}$ fois $g$ .

Example 1.10. Quelques relations grand Théta

Si $T (n) = 4$ alors $T (n) = Θ (1)$ .
Si $T (n) = 4 n + 2$ alors $T (n) = Θ (n)$ .
Si $T (n) = 4 n^{2} + 1$ alors $T (n) = Θ (n^{2})$ .

3.6. Notion d'équivalence

Equivalence

On dit qu’une fonction $f$ est équivalente à une fonction $g$ si et seulement si

lim_{n \to \infty} \frac{f (n)}{g (n)} = 1

On note alors $f (n) \sim g (n)$ .

Il faut bien comprendre que cette notion est plus forte que celle de grand Théta, car non seulement les fonctions sont du même ordre de grandeur mais leur quotient tend vers $1$ .

Example 1.11. Quelques équivalences

Si $f (n) = 4 n + 2$ et $g (n) = 4 n - 666$ , alors $f (n) \sim g (n)$ .
Si $f (n) = 4 n^{2} - 3 n + 5$ et $g (n) = 4 n^{2}$ , alors $f (n) \sim g (n)$ .


	Pour prouver l'équivalence entre deux fonctions, la méthode classique consiste à exprimer leur quotient, puis à factoriser au numérateur et au dénominateur les termes prépondérants.

Croissance des fonctions de référence

Dans cette sous-partie nous allons énoncer quelques résultats permettant de comparer entre elles les fonctions de référence, à savoir les fonctions logarithme, exponentielle et puissance.

Cette première propriété stipule que toutes les fonctions logarithmes sont du même ordre de grandeur.

Comparaison des fonctions logarithmes

Soient $a, b$ éléments de $ℝ$ tels que $a > 1$ et $b > 1$ .

Alors, $\log_{a} (n) = Θ (\log_{b} (n))$ .

Démonstration

D'après la propriété de proportionnalité entre les fonctions logarithmes, voir sous-partie 1.5, on a $\log_{a} (n) = \frac{\log_{b} (n)}{\log_{b} (a)}$ . Avec les notations de la définition de grand Théta, il suffit alors de poser $n_{0} = 1$ et $c_{1} = c_{2} = \frac{1}{\log_{b} (a)}$ pour prouver le résultat.

La formule suivante, due au mathématicien écossais James Stirling (1692-1770), montre la très forte vitesse de croissance vers plus l'infini de la fonction factorielle.

Croissance de la fonction factorielle

On a

n! \sim \sqrt{2 π n} {(\frac{n}{e})}^{n}


	Il existe de nombreuses preuves élégantes de cette formule. Dans le cadre de ce cours nous l’admettrons.

Finissons cette sous-partie avec un résultat bien connu des bacheliers scientifiques.

Croissances comparées

Considérons les fonctions $f_{1} (n) = 1$ , $f_{2} (n) = log (n)$ , $f_{3} (n) = n$ , $f_{4} (n) = n \times log (n)$ , $f_{5} (n) = n^{2}$ , $f_{6} (n) = n^{3}$ , $f_{7} (n) = 2^{n}$ et $f_{3} (n) = n!$ .

Elles sont classées de telle sorte que $\forall i \in {1, . . .,7}, f_{i} (n) = O (f_{i + 1} (n))$ .

Autre formulation, chacune de ces fonctions est un grand O de la fonction suivante.


	Il est inutile de préciser la base du logarithme dans le résultat précédent puisque toutes les fonctions logarithmes sont du même ordre de grandeur.

Pour bien fixer les idées sur le comportement de ces fonctions, voici le tracé de leurs courbes.

Figure 1.5. Représentation graphique des fonctions de référence

Du "bas vers le haut" on a les fonctions $log (x)$ , $x$ , $x \times log (x)$ , $x^{2}$ , $x^{3}$ , $2^{x}$ .

3.7. Classes de complexité

Il est temps maintenant de revenir à notre sujet de départ.

Les complexités algorithmiques que nous allons calculer vont dorénavant être exprimées comme des grand O ou grand Théta de fonctions de références. Cela va nous permettre de les classer.

Des algorithmes appartenant à une même classe seront alors considérés comme de complexité équivalente. Cela signifiera que l'on considèrera qu'ils ont la même efficacité.

Le tableau suivant récapitule les complexités de référence :

$Ο$	Type de complexité
$Ο (1)$	constant
$Ο (log (n))$	logarithmique
$Ο (n)$	linéaire
$Ο (n \times log (n))$	quasi-linéaire
$Ο (n^{2})$	quadratique
$Ο (n^{3})$	cubique
$Ο (2^{n})$	exponentiel
$Ο (n!)$	factoriel


	Ces complexités sont rangées dans l’ordre croissant, et ce d’après les résultats de croissances comparées entre fonctions usuelles.

Example 1.12. Classes de complexité

Voici la réinterprétation en terme de classes de complexité de certains calculs déjà effectués :

Le calcul de la somme des $n$ premiers entiers à l’aide d’une formule explicite est de complexité constante.
Ce même calcul réalisé de façon itérative est de complexité linéaire.
Le tri par sélection est de complexité quadratique.

Détails: Écrit par : Richard GAUTHIER; Création : 2 Février 2021; Mis à jour : 2 Février 2021; Clics : 1624

Vidéos YouTube

Télétravail Nsi séquence n°28 : Complexité algorithmique

I.But d'un calcul de complexité

II. Les deux types de complexité

2.1. Complexité en temps

2.2. Complexité en espace

2.3. De quoi est fonction la complexité ?

2.4. Quelques calculs de sommes usuelles

Somme de n termes constants

Démonstration

Somme des n premiers entiers

Démonstration

Somme des n premiers carrés d'entiers

Démonstration

Somme des n premiers termes d'une suite géométrique

Démonstration

2.5. Rappels sur la fonction logarithme

Définition

Règles opératoires

Démonstration

Relation de proportionnalité entre les fonctions logarithmes

Démonstration

Propriété

Démonstration

Définition

Théorème

2. Premiers calculs de complexité : algorithmes itératifs

3.1. Algorithmes sans structures de contrôle

Le cas des structures conditionnelles

Le cas des structures itératives

3.2. Premiers exemples un peu plus élaborés

Remarques sur la précision à apporter

Comportement asymptotique des fonctions de référence

3.3. Notations asymptotiques

Notion de grand O

Borne supérieure asymptotique

3.4. Notion de grand Oméga

Borne inférieure asymptotique

3.5. Notion de grand Théta

Borne asymptotique

3.6. Notion d'équivalence

Equivalence

Croissance des fonctions de référence

Comparaison des fonctions logarithmes

Démonstration

Croissance de la fonction factorielle

Croissances comparées

3.7. Classes de complexité