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é.

[Note]

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.

[Note]

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.

[Note]

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 N dans R+ℝ+. Nous la noterons en général TT (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.

[Note]

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=4096n=4096 on peut considérer que la taille de nn est :

  • la valeur de nn en elle même, façon la plus naturelle de voir les choses, i.e. 40964096

  • le nombre de chiffres que comporte l'écriture en binaire de nni.e. 1313

  • le nombre de chiffres que comporte l'écriture en décimal de nni.e. 44

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 nn.

[Note]

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 nn élément de Nℕ∗ et cc élément de R.

On a

nk=1c=n×c∑k=1nc=n×c

Démonstration

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

Somme des n premiers entiers

Soit nn élément de Nℕ∗.

On a

nk=1k=n×(n+1)2∑k=1nk=n×(n+1)2

Démonstration

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

  • Initialisation : pour n=1n=1, on a 1k=1k=1∑k=11k=1 qui est bien égal à 1×(1+1)2=11×(1+1)2=1.

  • Hérédité : supposons que pour un n1n≥1 l'égalité soit vérifiée. Calculer une somme avec un indice allant de 11 à n+1n+1 revient à calculer cette même somme avec un indice allant de 11 à nn, puis à rajouter le terme d'indice n+1n+1. On a ainsi n+1k=1k=nk=1k+n+1∑k=1n+1k=∑k=1nk+n+1, et donc d'après l'hypothèse de récurrence n+1k=1k=n×(n+1)2+n+1∑k=1n+1k=n×(n+1)2+n+1. Une simple mise au même dénominateur et une petite factorisation prouvent ensuite que n+1k=1k=(n+1)×(n+2)2∑k=1n+1k=(n+1)×(n+2)2. Ce qui est bien l'égalité au rang n+1n+1.

  • On conclut alors en appliquant le principe de récurrence.

[Note]

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 nn élément de Nℕ∗.

On a

nk=1k2=n×(n+1)×(2n+1)6∑k=1nk2=n×(n+1)×(2n+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 nn élément de Nℕ∗ et qq élément de R.

Si q1q≠1, on a

nk=0qk=1qn+11q∑k=0nqk=1−qn+11−q
[Note]

A noter que si q=1q=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 aa élement de R+ℝ+* tel que a1a≠1.

Le logarithme de base aa, noté logaloga, est l'unique fonction définie sur R+ℝ+* vérifiant les deux propriétés suivantes :

  1. loga(a)=1loga(a)=1.

  2. x,y>0, loga(xy)=loga(x)+loga(y)∀x,y>0, loga(xy)=loga(x)+loga(y).

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

Example 1.1. Fonctions logarithmes usuelles

  • Si a=ea=e, il s'agit du logarithme népérien, noté également lnln.

  • Si a=2a=2, il s'agit du logarithme binaire.

  • Si a=10a=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 aa élement de R+ℝ+* tel que a1a≠1.

  1. loga(1)=0loga(1)=0.

  2. x>0,loga(1x)=loga(x)∀x>0,loga(1x)=-loga(x).

  3. x,y>0,loga(xy)=loga(x)loga(y)∀x,y>0,loga(xy)=loga(x)-loga(y).

  4. x>0,nN,loga(xn)=n×loga(x)∀x>0,∀n∈ℕ,loga(xn)=n×loga(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

  1. Si l'on applique l'égalité définissant le logarithme avec x=1x=1 et y=1y=1, on obtient loga(1)=2×loga(1)loga(1)=2×loga(1). Ce qui prouve bien sûr que loga(1)=0loga(1)=0.

  2. Appliquons cette même égalité avec cette fois xx et 1x1x. Il vient loga(1)=loga(x)+loga(1x)loga(1)=loga(x)+loga(1x), ce qui prouve le résultat.

  3. Utilisons maintenant l'égalité avec xx et 1y1y. On a alors loga(xy)=loga(x)+loga(1y)loga(xy)=loga(x)+loga(1y). Il ne reste alors plus qu'à utiliser la seconde formule pour conclure.

  4. 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,ba,b élements de R+ℝ+* tel que a1a≠1 et b1b≠1.

On a la relation suivante entre les fonctions logaloga et logblogb :

x>0,loga(x)=logb(x)logb(a)∀x>0,loga(x)=logb(x)logb(a)

Démonstration

On constate sans difficultés que les fonctions loga(x)loga(x) et logb(x)logb(a)logb(x)logb(a) vérifient toutes les deux les propriétés définissant le logarithme de base aa. 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 aNa∈ℕa2a≥2.

Tout entier naturel xx peut s'écrire dans la base aa comme une somme de puissances de aa

x=cnan+cn1an1+...+c1a1+c0x=cnan+cn-1an-1+...+c1a1+c0

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

p1loga(x)<pp-1≤loga(x)<p
[Note]

Le résultat précédent signifie que loga(x)loga(x) est approximativement égal au nombre de chiffres de xx dans la base aa.

Démonstration

Il suffit de constater que si xx a pp chiffres dans son écriture en base aa alors ap1x<apap-1≤x<ap, puis d'appliquer la fonction logarithme de base aa 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 aa élement de R+ℝ+*.

L'exponentielle de base aa, noté expaexpa, est l'unique fonction définie sur R vérifiant les deux propriétés suivantes :

  1. expa(1)=aexpa(1)=a.

  2. x,y>0, expa(x+y)=expa(x)×expa(y)∀x,y>0, expa(x+y)=expa(x)×expa(y).

On la note également expa(x)=axexpa(x)=ax.

[Note]

Avec une variable entière, cette fonction exponentielle coïncide avec la fonction puissance usuelle, c'est-à-dire que nN,an=a×a×...×a∀n∈ℕ,an=a×a×...×a.

Théorème

Soit aa élement de R+ℝ+* tel que a1a≠1.

La fonction logaloga est bijective de R+ℝ+* dans R, et la fonction expaexpa est bijective de R dans R+ℝ+*. Ces deux fonctions sont de plus réciproques l'une de l'autre, ce qui signifie en particulier que :

  1. x>0,aloga(x)=x∀x>0,aloga(x)=x.

  2. xR,loga(ax)=x∀x∈ℝ,loga(ax)=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

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=xy=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)=8T(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(-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)=3T(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.

[Note]

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 nn premiers entiers

Cette fonction utilise une structure for pour calculer la somme des nn 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)=5n+1T(n)=5n+1.

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

Example 1.5. Calcul de la somme des nn 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)=3T(n)=3.

[Note]

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 nn.

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 nn 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)=4nT(n)=4n.

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 :

  1. Rechercher dans la liste la plus petite valeur et la permuter avec le premier élément de la liste.

  2. Rechercher ensuite la plus petite valeur à partir de la deuxième case et la permuter avec le second élément de la liste.

  3. 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 nn 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 00 et la boucle interne effectue donc n1n-1 itérations.

  • à la seconde itération de la boucle externe la variable i vaut 11 et la boucle interne effectue donc n2n-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

6+5×(n1)+6+5×(n2)+...+6+5×1=n1i=1(6+5×i)=6×(n1)+5×n1i=1i=6×(n1)+5×(n1)×n2=52n2+72n66+5×(n−1)+6+5×(n−2)+...+6+5×1=∑i=1n−1(6+5×i)=6×(n−1)+5×∑i=1n−1i=6×(n−1)+5×(n−1)× n2=52n2+72n−6

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)=2n2+3n5T(n)=2n2+3n-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 à 4n+24n+2 ou 3n+53n+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 N et à valeurs dans R+ℝ+.

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 N. 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 ff est un grand O d’une fonction gg si et seulement si

c>0, n0>0 tel que n>n0, f(n)<c×g(n)∃c>0, ∃n0>0 tel que ∀n>n0, f(n)<c×g(n)

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

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

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

Interprétation graphique de la notion de grand O

A partir du rang n0n0, la courbe de ff est au dessous de celle de cc fois gg.

Example 1.8. Quelques relations grand O

  • Si T(n)=4T(n)=4 alors T(n)=O(1)T(n)=Ο(1). Pour le prouver, prendre par exemple c=5c=5 et n0=0n0=0.

  • Si T(n)=3n+2T(n)=3n+2 alors T(n)=O(n)T(n)=Ο(n). Pour le prouver, prendre par exemple c=4c=4 et n0=2n0=2.

  • Si T(n)=2n+3T(n)=2n+3 alors T(n)=O(n2)T(n)=Ο(n2). Pour le prouver, prendre par exemple c=3c=3 et n0=1n0=1.

[Note]

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 ff est un grand Oméga d’une fonction gg si et seulement si

c>0, n0>0 tel que n>n0, c×g(n)<f(n)∃c>0, ∃n0>0 tel que ∀n>n0, c×g(n)<f(n)

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

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

[Note]

Le lecteur se persuadera sans peine que

f(n)=Ω(g(n))g(n)=O(g(n))f(n)=Ω(g(n))⇔g(n)=Ο(g(n))

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

Interprétation graphique de la notion de grand Oméga

A partir du rang n0n0, la courbe de ff est au dessus de celle de cc fois gg.

Example 1.9. Quelques relations grand Oméga

  • Si T(n)=4T(n)=4 alors T(n)=Ω(1)T(n)=Ω(1).

  • Si T(n)=4n+2T(n)=4n+2 alors T(n)=Ω(n)T(n)=Ω(n).

  • Si T(n)=4n2+1T(n)=4n2+1 alors T(n)=Ω(n)T(n)=Ω(n).

[Note]

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 ff est un grand Théta d’une fonction gg si et seulement si

c1>0, c2>0, n0>0 tel que n>n0, c1×g(n)<f(n)<c2×g(n)∃c1>0, ∃c2>0, ∃n0>0 tel que ∀n>n0, c1×g(n)<f(n)<c2×g(n)

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

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

[Note]

Il est facile de voir que

f(n)=Θ(g(n))(f(n)=O(g(n))etf(n)=Ω(g(n)))f(n)=Θ(g(n))⇔(f(n)=Ο(g(n))etf(n)=Ω(g(n)))

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

Interprétation graphique de la notion de grand Théta

A partir du rang n0n0, la courbe de ff est entre celle de c1c1 fois gg et celle de c2c2 fois gg.

Example 1.10. Quelques relations grand Théta

  • Si T(n)=4T(n)=4 alors T(n)=Θ(1)T(n)=Θ(1).

  • Si T(n)=4n+2T(n)=4n+2 alors T(n)=Θ(n)T(n)=Θ(n).

  • Si T(n)=4n2+1T(n)=4n2+1 alors T(n)=Θ(n2)T(n)=Θ(n2).

 3.6. Notion d'équivalence

Equivalence

On dit qu’une fonction ff est équivalente à une fonction gg si et seulement si

limnf(n)g(n)=1limn→∞f(n)g(n)=1

On note alors f(n)g(n)f(n)∼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 11.

Example 1.11. Quelques équivalences

  • Si f(n)=4n+2f(n)=4n+2 et g(n)=4n666g(n)=4n-666, alors f(n)g(n)f(n)∼g(n).

  • Si f(n)=4n23n+5f(n)=4n2-3n+5 et g(n)=4n2g(n)=4n2, alors f(n)g(n)f(n)∼g(n).

[Note]

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 logarithmeexponentielle 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,ba,b éléments de R tels que a>1a>1 et b>1b>1.

Alors, loga(n)=Θ(logb(n))loga(n)=Θ(logb(n)).

Démonstration

D'après la propriété de proportionnalité entre les fonctions logarithmes, voir sous-partie 1.5, on a loga(n)=logb(n)logb(a)loga(n)=logb(n)logb(a). Avec les notations de la définition de grand Théta, il suffit alors de poser n0=1n0=1 et c1=c2=1logb(a)c1=c2=1logb(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!2πn(ne)nn!∼2πn(ne)n
[Note]

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 f1(n)=1f1(n)=1f2(n)=log(n)f2(n)=log(n)f3(n)=nf3(n)=nf4(n)=n×log(n)f4(n)=n×log(n)f5(n)=n2f5(n)=n2f6(n)=n3f6(n)=n3f7(n)=2nf7(n)=2n et f3(n)=n!f3(n)=n!.

Elles sont classées de telle sorte que i{1,...,7},fi(n)=O(fi+1(n))∀i∈{1,...,7}, fi(n)=O(fi+1(n)).

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

[Note]

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

Représentation graphique des fonctions de référence

Du "bas vers le haut" on a les fonctions log(x)log(x)xxx×log(x)x×log(x)x2x2x3x32x2x.

 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 :

OΟ

Type de complexité

O(1)Ο(1) constant
O(log(n))Ο(log(n)) logarithmique
O(n)Ο(n) linéaire
O(n×log(n))Ο(n×log(n)) quasi-linéaire
O(n2)Ο(n2) quadratique
O(n3)Ο(n3) cubique
O(2n)Ο(2n) exponentiel
O(n!)Ο(n!) factoriel
[Note]

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 nn 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.

 
 

footer2

Richard GAUTHIER
Professeur de Physique Appliquée
Certification ISN
Cette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser.

www.carhaix2020.bzh