Skip to content

Notion de complexité et grand O

Référence:  
Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein - 
Algorithmique - 3ème édition - Cours avec 957 exercices et 158 problèmes, 
Dunod,  2010, ISBN: 978-2-10-054526-1
http://www.books-by-isbn.com/2-10/2100545264-Algorithmique-Cours-avec-957-exercices-et-158-problemes-2-10-054526-4.html

Motivation

Montrer qu'une version d'un programme est plus efficace qu'une autre n'est, a priori, pas aisé. La succession ou l'imbrication des tests et des boucles et la multitude des possibilités fait qu'il n'est généralement pas possible ou raisonnable d'évaluer l'efficacité de l'algorithme pour chaque cas possible.

Dans ce chapitre, nous donnerons un aperçu des techniques et méthodes d'estimation de l'efficacité d'un algorithme. En particulier nous définirons la notation grand O qui permettra de classer les algorithmes selon leur type d'efficacité sans devoir détailler le nombre exact d'instructions exécutées par l'algorithme.

Critères de choix d'un algorithme

Généralement, il existe plusieurs méthodes pour résoudre un même problème. Il faut alors en choisir une et concevoir un algorithme pour cette méthode de telle sorte que cet algorithme satisfasse le mieux possible aux exigences.

Parmi les critères de sélection d'une méthode et en conséquence d'un algorithme, deux critères prédominent: la simplicité et l'efficacité de cet algorithme.

Si parfois ces critères vont de paire, bien souvent ils sont contradictoires; un algorithme efficace est, en effet, bien souvent compliqué et fait appel à des méthodes fort élaborées. Le concepteur doit alors choisir entre la simplicité et l'efficacité.

Si l'algorithme devra être mis en oeuvre sur un nombre limité de données qui ne demanderont qu'un nombre limité de calculs, cet algorithme doit de préférence être simple. En effet un algorithme simple est plus facile à concevoir et a moins de chance d'être erroné que ne le sera un algorithme complexe.

Si, par contre, un algorithme est fréquemment exécuté pour une masse importante de données, il doit être le plus efficace possible.

Au lieu de parler de l'efficacité d'un algorithme, on parlera généralement de la notion opposée, à savoir, de la complexité d'un algorithme.

La complexité d'un algorithme ou d'un programme peut être mesurée de diverses façons. Généralement, le temps d'exécution est la mesure principale de la complexité d'un algorithme.

D'autres mesures sont possibles dont:

  • la quantité d'espace mémoire occupée par le programme et en particulier par ses variables;
  • la quantité d'espace disque nécessaire pour que le programme s'exécute;
  • la quantité d'information qui doit être transférée (par lecture ou écriture) entre le programme et les disques ou entre le programme et des serveurs externes via un réseau;
  • ...

Nous n'allons pas considérer de programme qui échange un grand nombre d'informations avec des disques ou un autre ordinateur.

En général nous analyserons le temps d'exécution d'un programme pour évaluer sa complexité. La mesure de l'espace mémoire occupé par les variables sera un autre critère qui pourra être utilisé ici.

De façon générale, la complexité d'un algorithme pour un ensemble de ressources donné est une mesure de la quantité de ces ressources utilisées par cet algorithme.

Le critère que nous utiliserons dans la suite est un nombre d'actions élémentaires exécutées. Nous prendrons soin, avant toute chose, de préciser le type d'actions prises en compte et si nous voulons une complexité minimale, moyenne ou maximale.

Nous verrons que, généralement, la complexité d'un algorithme est exprimée par une fonction qui dépend de la taille du problème à résoudre.

Approche pragmatique : mesurons le temps d'exécution

Une première approche pragmatique, pour avoir des informations sur le temps d'exécution, est tout simplement de le mesurer sur différents jeux de données.

Le module timeit permet de réaliser plusieurs exécutions d'un code donné et de retenir le meilleur temps CPU parmi l'ensemble des exécutions.

Les exécutions peuvent se faire au "terminal", dans un script ou une console Python

$ python3 -m timeit -n 5 "print('coucou')"
coucou
...
coucou
coucou
5 loops, best of 5: 1.69 usec per loop
:0: UserWarning: The test results are likely unreliable. The worst time (9.01 usec) was more than four times slower than the best time (1.69 usec).
ThierryM:~ tmassart$ 

ou (ici à la console en utilisant le module timeit, un objet de classe Timer et la méthode timeit :

>>> import timeit
>>> t = timeit.Timer("print('coucou')")
>>> t.timeit(5)

coucou
coucou
coucou
coucou
coucou
4.3688996811397374e-05

Prenons un autre exemple : si nous analysons les deux fonctions anagramme_dico(a, b) et anagramme_list(a, b) données ici, qui renvoient toutes deux True si les séquences a et b sont des permutations l'une de l'autre.

def anagramme_dico(a,b):
    res = False
    if len(a)==len(b):
        dic_a = {}
        dic_b = {}
        for i in a:
            dic_a[i] = dic_a.setdefault(i, 0) + 1
        for i in b:
            dic_b[i] = dic_b.setdefault(i, 0) + 1
        res = dic_a == dic_b
    return res


def anagramme_list(a,b):
    res = False
    if len(a) == len(b):
        liste_b = list(b)
        res = True
        for i in a:
            if i in liste_b:
                liste_b.remove(i)
            else:
                res = False
    return res

Prenons initalement la chaîne de 10 caractères "RAVITAILLE" dont on multiplie la longueur par deux à chaque itération par répétition du même texte, et donneons le temps d'exécution de chaque code.

import timeit

d1 = """
def anagramme_list(a,b):
    res = False
    if len(a) == len(b):
        liste_b = list(b)
        res = True
        for i in a:
            if i in liste_b:
                liste_b.remove(i)
            else:
                res = False
    return res
"""
d2 = """def anagramme_dico(a,b):
    res = False
    if len(a)==len(b):
        dic_a = {}
        dic_b = {}
        for i in a:
            dic_a[i] = dic_a.setdefault(i, 0) + 1
        for i in b:
            dic_b[i] = dic_b.setdefault(i, 0) + 1
        res = dic_a == dic_b
    return res
"""
taille = 1
for i in range(20):
    t1 = timeit.Timer(d1 + f"""anagramme_list('"RAVITAILLE"'*{taille},'"RAVITAILLE"'[::-1]*{taille})""")
    t2 = timeit.Timer(d2 + f"""anagramme_dico('"RAVITAILLE"'*{taille},'"RAVITAILLE"'[::-1]*{taille})""")
    print(f"{taille*10:8d} {t1.timeit(1):11f} {t2.timeit(1):11f}")
    taille *= 2

Celui-ci est presque immédiat pour les chaînes de taille inférieure à 100000 caractères. Au delà, la fonction anagramme_list prend un temps de plus en plus significatif.


Taille anagramme_list (en s) anagramme_dico (en s)
10 0.000008 0.000006
20 0.000009 0.000009
40 0.000012 0.000012
80 0.000022 0.000021
160 0.000037 0.000037
320 0.000063 0.000074
640 0.000121 0.000145
1280 0.000261 0.000266
2560 0.000590 0.000571
5120 0.001676 0.001070
10240 0.005371 0.002035
20480 0.016907 0.003809
40960 0.098608 0.007899
81920 0.303143 0.012504
163840 1.231720 0.027419
327680 4.438462 0.050453
655360 20.400489 0.108817
1310720 102.657282 0.211423
2621440 586.517143 0.412746
5242880 2995.177226 0.991613

Par exemple dans la dernière ligne du tableau ici, pour une chaîne d'un peu plus de cinq millions de caractères, il faut approximativement 3000 secondes pour la version liste, soit près d'une heure, et moins d'une seconde pour la version dictionnaire.

On peut estimer grossièrement que le temps d'exécution grandit

  • linéairement par rapport à la taille des séquences avec la fonction anagramme_dico, et
  • de façon quadratique par rapport à la taille des séquences avec la fonction anagramme_list

il est intuitivement normal que ces fonctions prennent un temps proportionnel à la taille de a (on suppose que les deux chaînes de caractères sont de même taille).

Par contre, cette démarche est chronophage et on atteint vite ses limites car il n'est pas possible de faire des tests pour tous les exemples intéressants possibles et sur l'ensemble des ordinateurs possibles.

Approche analytique : comptons le nombre d'instructions

Essayons d'exprimer la complexité d'un algorithme par une fonction mathématique du nombre d'instructions élémentaires réalisées; celle-ci dépend de la taille du problème à résoudre.

Exemple: la recherche du minimum

Le travail nécessaire pour qu'un programme s'exécute dépend de la 'taille' du jeu de données fourni.

Par exemple, si nous analysons le code qui effectue une recherche de l'indice de l'élément de valeur minimale dans une liste Python s, il est intuitivement normal que cet algorithme prenne un temps proportionnel à len(s), et soit noté, par exemple, \(T(len(s))\).

Dénotons \(len(s) = n\). \(n\) est la taille de la liste et donc par extension, également la taille du problème.

Donnons ici la partie traitement de cet algorithme en ayant eu soin de transformer le for en while pour mieux détailler chaque étape d'exécution de l'algorithme et nous supposons n = len(s) connu dans le programme :

1    res = 0                      
2    i = 1                        
3    while  i< n :                
4       if  s[i][0] < s[res][0]:  
5          res = i                
6       i = i+1                   
7    return res                   

Pour obtenir des résultats qui restent valables quel que soit l'ordinateur utilisé, il faut réaliser des calculs simples donnant une approximation dans une unité qui soit indépendante du processeur utilisé. On peut, par exemple, faire l'approximation que chaque assignation de donnée simple ou test élémentaire représente une unité de temps d'exécution.

D'autres hypothèses auraient pu être faites. Par exemple, on aurait pu ne considérer que les assignations et rechercher la complexité en nombre d'assignations, ou ne considérer que les tests et rechercher la complexité en nombres de tests effectués par l'algorithme.

La complexité dépend donc fortement de l'unité prise qui doit être clairement précisée.

Avec nos hypothèses, les instructions des lignes 1, 2 et 7 prennent chacune une unité de temps d'exécution.

La boucle while de la ligne 3 à 6 s'exécute \(n-1\) fois, mais le test s'effectue \(n\) fois. La ligne 3 prend \(n\) unités et la ligne 6, \(n-1\) unités.

Le test de la ligne 4 prend une unité; il est effectué \(n-1\) fois et donc la ligne 4 utilisera au total \(n-1\) unités.

L'assignation de la ligne 5 prend une unité. Elle n'est effectuée que lorsque le test du if est vérifié. Si l'on ne désire pas uniquement faire une seule mesure sur un jeu de données bien précis, il faut donc expliciter si l'on désire connaître le temps d'exécution dans le meilleur des cas \(T_{min}(n)\), le pire des cas \(T_{MAX}(n))\), ou en moyenne \(T_{moyen}(n)\). Ici:

  • \(T_{min}(n)\) est donné dans le cas où le test du if n'est jamais vérifié, ce qui signifie que le minimum se trouve à la première composante. On a alors: \(T_{min}(n) = 1+1+n+(n-1)+(n-1)+1 = 3n+1\)

  • \(T_{MAX}(n)\) est donné dans le cas où le test du if est à chaque fois vérifié, ce qui correspond au cas où toutes les valeurs de s sont distinctes et triées en ordre décroissant. On a alors: \(T_{MAX}(n) = 1+1+n+(n-1)+(n-1)+(n-1)+1 = 4n\)

Le calcul de \(T_{moyen}(n)\) est généralement beaucoup plus difficile à effectuer. Pour cela, on peut faire des hypothèses sur les jeux de données possibles et leur distribution statistique; ces hypothèses doivent être le plus réaliste possible. Pour que le calcul de \(T_{moyen}(n)\) ne soit pas trop compliqué, on tolère généralement certaines hypothèses simplificatrices. Nous pouvons, par exemple, supposer que toutes les valeurs dans s sont distinctes et faire l'hypothèse que la distribution des valeurs est uniforme, la liste étant non triée a priori.

Pour faire ce calcul, séparons les actions dues au while, au if et à l'assignation finale, des actions d'assignation de la variable res et posons:

\(C(n)\) = le nombre moyen d'assignations à res pour une liste de taille \(n\)

Si nous posons \(R(n)\) = le nombre d'actions dues au while, au if et à l'assignation finale, ce nombre est connu et vaut: \(R(n)\) = 3n.

Nous avons: \(T_{moyen}(n) = C(n) + R(n)\)

Pour exprimer la valeur de \(C(n)\), regardons d'abord sa valeur pour \(n\) valant \(1,2, ...\)

Pour \(n\) valant 1, \(C(1)=1\) puisqu'il y a une assignation en début, et que le corps de la boucle while ne s'exécute jamais.

Pour \(n\) valant 2, la liste contient une valeur maximale \(Max\) et une valeur minimale \(min\). Deux possibilités équiprobables peuvent se présenter:

  1. s = min suivi de Max
  2. s = Max suivi de min

Le cas 1. donne une assignation et le cas 2. deux assignations, soit en moyenne: C(2) = 3/2

Essayons d'avoir une expression générale pour \(C(n)\): \(s[0]\) a une chance sur \(n\) d'être le minimum, une chance sur \(n\) d'être le deuxième minimum, .... Donc \(s[0]\) a \(1/n\) chance d'être le ième minimum et cela pour tout \(i\) entre 1 et \(n\).

Si nous posons \(C(0) = 0\) et si dans la sous-liste qu'il reste à traiter il y a \(j\) éléments plus petits que le minimum provisoire, le nombre d'assignations qu'il faudra encore effectuer vaudra, d'après la définition donnée, \(C(j)\), car les nombres plus grands que le minimum provisoire n'impliqueront aucune assignation supplémentaire. Ce raisonnement est valable pour tout \(i >= 1\).

En conséquence :

\(C(i) = 1 + \frac{1}{i}\sum_{j=0}^{i-1}C(j) \; (\forall i \ge 1) \; (1)\)

le 1 étant dû à la première assignation (c'est-à-dire à l'instruction 1).

Pour avoir une idée précise de la valeur de \(C(n)\), il faut éliminer les \(C(j)\) du membre de droite.

Pour cela exprimons cette équation d'une autre façon en le multipliant par \(i\)

\(i.C(i) = i + \sum_{j=1}^{i-1} C(j) \; (2)\)

et de même si on multiplie \(C(i+1)\) par \(i+1\):

\((i+1).C(i+1) = (i+1) + \sum_{j=1}^{i} C(j) \; (3)\)

En soustrayant la seconde équation de la troisième nous obtenons:

\((i+1).C(i+1) - i.C(i) = 1+C(i) \; (4)\)

Ce qui peut s'écrire:

\(C(i+1) = \frac{1}{i+1} + C(i) \qquad (\forall i \geq 1) \; (5)\)

Pour \(C(1)\) la formule reste vrai \((C(1)=1)\)

Et donc:

\(C(n) = \frac{1}{n} + \frac{1}{n-1} + \ldots + 1 = \sum_{i=1}^{n} \frac{1}{i} \; (6)\)

Notons que nous aurions pu déduire ce résultat plus rapidement en exprimant que \(C(i+1)\) vaut le nombre moyen d'assignations dû à la recherche du minimum pour les \(i\) premiers nombres, c'est-à-dire \(C(i)\), plus la probabilité que le nombre \(V[i]\) soit le minimum, c'est-à-dire \(\frac{1}{i+1}\), ce qui nous redonne l'équation (5).

Pour effectuer une approximation de \(C(n)\), évaluons les aires \(S1\) et \(S2\) donnés en grisé dans la figure ci-dessous où la fonction \(f(x) = \frac{1}{x}\).

\[\begin{figure}[hbt] \centerline{\epsfbox{unsurx2}} \caption{Approximation de $C(n)$} \label{Hn} \end{figure}\]

Ayant \(\int_{1}^{n+1} \frac{1}{x} dx = \ell n (n+1)\), on voit que

\(S2 < \ell n (n+1) < S1\)

Comme

\(S1 = 1 + \frac{1}{2} + \ldots + \frac{1}{n} = \sum_{i=1}^{n} \frac{1}{i} = C(n)\)

\(S2 = \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n+1} = \sum_{i=2}^{n+1} \frac{1}{i} = C(n+1)-1\)

et ceci pour tout \(n \geq 1\).

On a donc:

\(C(n+1)-1 < \ell n(n+1) < C(n) \qquad (\forall n \geq 1)\)

De ce fait:

\(C(n) < \ell n(n)+1 \qquad (\forall n > 1)\)

Et finalement, comme \(\ell n(n) < \ell n(n+1)\), on obtient:

\(\ell n(n) < C(n) < \ell n(n)+1 \; (7)\)

L'équation (7) permet de borner \(T_{moyen} (n)\) (rappelons nous que \(T_{moyen}(n) = C(n) + R(n)\) avec \(R(n)\) \(=\) \(3n\))

Nous obtenons donc:

\(3n+\ell n(n) < T_{moyen}(n) < 3n+\ell n(n)+1 \; (8)\)

Autre exemple: la recherche d'un élément

Calculons les \(T{min(n)}\), \(T_{Max(n)}\) et \(T_{moyen(n)}\) de l'algorithme de recherche d'un élément dans une liste s.

On suppose que n = len(s), que l'on cherche l'indice de la première valeur simple valant x dans la liste s qui est de même type que x et que l'on affiche l'indice du résultat ou None par convention pour exprimer que l'on a pas trouvé:

L'algorithme suivant répond à la demande.

   print(s.index(x) if x in s else None)

Mais nous prenons plutôt la version piétonne ci-dessous qui montre chaque étape élémentaire.

1   i = 0                     
2   while i < n and s[i] != x:
3      i = i+1              
4   if i == n:              
5      i = None # pas trouvé
6   print(i) 

\(T_{min(n)}\) est donné lorsque l'on trouve directement l'élément.

Si l'on suppose ici encore que toute assignation et tout test élémentaire prend une unité de temps et que le test du while est composé de deux tests élémentaires (le temps pour le and étant omis), on obtient: \(T_{min(n)} = 5 (c'est-à-dire 1 en ligne 1 + 2 en ligne 2 + 1 en ligne 4 + 1 en ligne 6)\)

\(T_{MAX(n)}\) est donné dans le cas où l'élément x n'est pas dans s: T_{MAX(n)} = 3n+5

\(T_{moyen(n)}\) dépend de la probabilité \(p\) que x soit dans s.

En supposant que si x est dans s, il a la même probabilité d'être dans n'importe quelle composante \(s[i]\) (pour \(0 <= i < n\)), en énumérant les cas possibles on obtient:

Cas possibles Nombre d'unités
1 : on trouve x en \(s[0]\) \(3+2\)
2 : on trouve x en \(s[1]\) \(6+2\)
...
n : on trouve x en \(s[n-1]\) \(3n+2\)

Si x est dans s:

\(moyen\)

\(\; \; \; \; \; \; \; \; \; \; \; \; = \frac{3}{n} (1 + 2 + \ldots + n) + 2\)

$\; \; \; \; \; \; \; \; \; \; \; \; = \frac{3(n + 1)}{2} + 2 \; \; $ (puisque \(\sum_{i=1}^{n} i = \frac{(1 + n) n}{2}\))

\(\; \; \; \; \; \; \; \; \; \; \; \; = \frac{3}{2} n + \frac{7}{2}\)

Si x n'est pas dans s:

\(min = moyen = MAX = 3n+5\)

Finalement

\(T_{moyen}(n) = (1-p) (3n+5) + p(\frac{3}{2} n+ \frac{7}{2}) = (3 - \frac{3}{2}p) n + (- \frac{3}{2} p + 5)\)

La notion de grand \(O\)

Les exemples précédents montrent qu'il est souvent très difficile de calculer le temps moyen (ou maximal) d'exécution d'un algorithme. Ces calculs précis sont, de plus, inutiles puisqu'ils se basent sur des approximations grossières du temps d'exécution des actions élémentaires; évaluations qui ne tiennent pas non plus compte, par exemple, de l'ordinateur et de l'interpréteur utilisés.

Une évaluation du temps d'exécution d'un algorithme ne devient généralement intéressante que lorsque la taille du jeu de données, c'est-à-dire de \(n\) dans nos exemples précédents, est grande. En effet pour \(n\) petit, les algorithmes s'exécutent généralement très rapidement.

Supposons que la complexité maximale d'un algorithme \(A = 100.n\), que la complexité maximale d'un algorithme \(B = 15.n^2\) , celle de \(C = n^4\) et celle de \(D = 2^n\).

La table suivante donne les valeurs de complexité pour \(n = 1,10,100,1,000, 10,000, 10^6\) et \(10^9\);

\(n\) \(A\) \(B\) \(C\) \(D\)
\(1\) \(100\) \(15\) \(1\) \(2\)
\(10\) \(1000\) \(1500\) \(10000\) \(\approx 10^3\)
\(100\) \(10000\) \(150000\) \(10^8\) \(\approx 10^{30}\)
\(1000\) \(100000\) \(15.10^6\) \(10^{12}\) \(\approx 10^{300}\)
\(10000\) \(10^6\) \(15.10^8\) \(10^{16}\) \(\approx 10^{3000}\)
\(10^6\) \(10^8\) \(15.10^{12}\) \(10^{24}\) \(\approx 10^{300000}\)
\(10^9\) \(10^{11}\) \(15.10^{18}\) \(10^{36}\) \(\approx 10^{3.10^{8}}\)
...

Valeur de \(100.n\), \(15.n^2\), \(n^4\) et \(2^n\) pour différentes valeurs de \(n\)

Ces valeurs doivent être divisées par le nombre d'instructions élémentaires par seconde pour obtenir un temps exprimé en seconde.

Les micro processeurs actuels permettent d'exécuter de l'ordre de \(10^9\) instructions par seconde soit environ \(10^14\) instructions par jour.

Cela signifie qu'en un jour, si aucune autre limitation ne perturbe l'exécution des algorithmes (telle que l'espace mémoire disponible par exemple), avec un microprocesseur, on peut résoudre avec l'algorithme

  • \(A\) , un problème pour \(n\) valant approximativement \(10^{12}\)
  • \(B\) , un problème pour \(n\) valant approximativement \(10^7\)
  • \(C\) , un problème pour \(n\) valant approximativement \(3000\)
  • \(D\) , un problème pour \(n\) valant approximativement \(50\)

et donc \(A\) est meilleur que \(B\), qui est meilleur que \(C\), lui-même étant meilleur que \(D\) (sauf pour de petites valeurs de \(n\)).

En vertu des remarques précédentes et de ces chiffres, on préfère donner un ordre de grandeur permettant d'avoir une idée du type d'algorithme. Pour cela, on utilise la notation grand \(O\) définie ci-dessous, qui permet:

  • de déterminer si un algorithme a une chance de s'exécuter pour un \(n\) donné,
  • connaissant le temps d'exécution pour un \(n\) donné, de faire une approximation de ce temps pour une autre valeur de \(n\).

Définition de complexité en O()

La notation grand \(O\) est définie comme suit:

Définition (\(O\)) : Une complexité \(T(n)\) est dite en grand \(O\) de \(f(n)\) (en \(O(f(n))\) s'il existe un entier \(N\) et une constante \(c > 0\) tels que pour tout entier \(n > N\) nous avons \(T(n) <= c.f(n)\)

Cette définition permet d'effectuer de nombreuses simplifications dans les calculs. En effet de cette définition il résulte que:

  • Les facteurs constants ne sont pas importants. En effet, si par exemple \(T(n)=n\) ou si \(T(n)=100n\), \(T(n)\) est toujours en \(O(n)\)
  • Les termes d'ordres inférieurs sont négligeables. Ainsi si \(T(n) = n^3 + 4n^2 + 20n + 100\), on peut voir que pour \(n > N = 5\)

    • \(n^3 > 4n^2\)
    • \(n^3 > 20n\)
    • \(n^3 > 100\)

et donc pour \(n>5\), \(T(n) = n^3 + 4n^2 + 20.n + 100 < 4n^3\).

De ce fait \(T(n)\) est en \(O(n^3)\).

Calcul du grand \(O\)

Classes de complexité

Si on peut calculer qu'un algorithme est un \(O(n^2 )\), il n'est pas intéressant, même si cela est trivialement vrai, d'exprimer le fait que \(T(n)\) est en \(O(n^3 )\), \(O(n^4 )\), ....

Lorsque l'on évalue le grand \(O\) d'une complexité, c'est la meilleure estimation "simple" que l'on cherche à obtenir.

Ainsi on classe généralement les complexités d'algorithmes selon leur grand \(O\) comme donné par la table suivante :

\(O\) Classe d'algorithmes
\(O(1)\) constant
\(O(log \, n)\) logarithmique
\(O(n)\) linéaire
\(O(n \, log \, n)\) \(n\, log\, n\)
\(O(n^2 )\) quadratique
\(O(n^3 )\) cubique
\(O(2^n )\) exponentiel en base 2
\(O(3^n )\) exponentiel en base 3
...
\(O(n^n )\) exponentiel en base n
...

Classes de complexité

Dans la suite, nous essayerons toujours de donner une approximation de la complexité des algorithmes vus.

Remarquons qu'en vertu du fait que pour tout a,b positif : \(log_a n = (log_a b).(log_b n)\)

et comme \(log_a b\) est une constante pour \(a\) et \(b\) fixés, si \(T(n)\) est en \(O(log_a n)\) il est également en \(O(log_b n)\). (la base du logarithme n'a donc pas d'importance pour exprimer un grand \(O\)). Notons encore que ceci n'est pas vrai pour la base des complexités exponentielles.

Règles de calcul du grand O

Donnons ici un petit nombre de règles permettant d'évaluer la complexité d'un algorithme. Ces règles ne donnent en général qu'une surapproximation parfois grossière; une estimation plus précise devant tenir compte du fonctionnement de l'algorithme.

Tout d'abord, l'évaluation se fait en "bottom-up", depuis les instructions simples, vers les instructions plus complexes. Si l'on regarde l'arbre syntaxique du code, on détermine donc d'abord la complexité des feuilles (avec les instructions 1, 2, 5, 6 et 7) pour ensuite remonter en déterminant la complexité de l'instruction if et ensuite du while pour enfin avoir la complexité de tout le code qui correspond à la racine de l'arbre syntaxique.

Arbre syntaxique du code  de recherche du minimum

1     res = s[0]  
2     i = 1       
3     while i < n:
4        if s[i] < res:
5           res = s[i] 
6        i = i + 1     
7     return res

Règle 1 (unité) Il faut clairement définir l'unité utilisée et les éléments pris en compte. Ainsi si, si l'on regarde la complexité en temps d'exécution et l'on tient compte des tests élémentaires, des assignations, des lectures de données et des écritures de résultats, une assignation à une variable simple, une instruction input ou print d'une donnée simple, ou l'évaluation d'une expression (ou d'une condition) simple ne donnant pas lieu à l'exécution de fonctions, prend un temps constant fixé et est donc en \(O(1)\). L'assignation à des objets plus complexes ou des input ou print de données plus complexes peut ne plus être en \(O(1)\) en fonction de leur taille qui peut dépendre de la taille du problème (\(n\)).

Règle 2 (séquence)

  • Si un traitement 1 prend un temps \(T_1(n)\) qui est en \(O(f_1(n))\) et
  • un traitement 2 prend un temps \(T_2(n)\) qui est en \(O(f_2(n))\) alors
  • le traitement 1 suivi du traitement 2 prend \(T_1(n) + T_2(n)\) et est en
    \(O(f_1(n) + f_2(n)) = O (max(f_1(n) , f_2(n)))\)

où max prend la fonction qui croît le plus vite c'est-à-dire de plus grand ''ordre''.

Par exemple si \(T_1(n)\) est en \(O(n^2 )\) et \(T_2(n)\) est en \(O(n)\), \(T_1(n) + T_2(n)\) est en \(O(n^2 + n) = O(n^2)\)

En particulier une séquence d'instructions simples (dont on tient compte) ne faisant aucun appel à une procédure ou à une fonction ne dépend pas de \(n\) et sont donc en \(O(1)\).

Règle 3 (if)

Pour un if condition: instruction_1 else: instruction_2

  • instruction_1 est en \(O(f_1(n))\)
  • instruction_2 est en \(O(f_2(n))\)
  • l'évaluation de la condition est en \(O(g(n))\)

suivant le test, le if sera en \(O(max(f_1(n),g(n)))\) ou en \(O(max(f_2(n),g(n)))\) et peut être borné par:

\(O(max(f_1(n), f_2(n), g(n)))\)

Notons que souvent \(g(n)\) est en \(O(1)\).

Cette règle peut être généralisée pour une instruction if ayant une ou des parties elsif.

Règle 4 (while)

Pour un while, sachant que le corps de la boucle est en \(O(f_1(n))\) et que l'évaluation de la condition est en \(O(f_2(n))\), si on a une fonction en \(O(g(n))\) qui donne une borne supérieure du nombre de fois que le corps sera exécuté, alors le while est en \(O(f(n).g(n))\) avec \(f(n) = max(f_1(n),f_2(n))\).

Règle 5 (for)

Pour une boucle for, il suffit de ''traduire'' le for en while.

Par exemple :

    for i in range(n):
       print(i)

se traduit en:

    i=0
    while i < n: 
       print(i)
       i=i+1

La fonction iter() appliquée sur une séquence ou un range, permet de pouvoir ensuite utiliser la fonction next() sur l'objet produit.

Par exemple :

  st = "bonjour"  
  for i in st:
       print(i)

se traduit en:

    st = "bonjour"
    i = iter(st)
    s=next(i)
    while s != None:
       print(s)
       s=next(i)

Donnons de simples exemples de complexité avec des for où ici aussi \(n\) est la taille du problème :

  for i in range(10):
    traitement 

est en \(O(10.f(n))\)\(O(f(n))\) est la complexité d'une exécution du traitement et donc le code complet est également en \(O(f(n))\)

   for i in range(n):
    traitement 

est en \(O(n.f(n))\)\(O(f(n))\) est la complexité d'une exécution du traitement.

Règle 6 (fonction)

L'appel à une fonction est en \(O(f(n))\) correspondant à la complexité du traitement de cette fonction pour les paramètres effectifs donnés.

On peut raffiner ces calculs, selon que l'on essaye de trouver une complexité minimale, moyenne ou maximale. Ce raffinement se situera dans le nombre de fois qu'une instruction sera répétée, ayant par exemple certaines hypothèses sur la probabilité que certaines conditions de if ou de boucles sont vérifiées.

Application des règles de calcul

Note : Les algorithmes dont les codes python sont donnés ici sont expliqués dans le chapitre 8 du cours : http://di.ulb.ac.be/verif/tmassart/Prog/html/chapitre8.html#recherche-sequentielle

Ayant ces règles d'évaluation du grand \(O\) pour chaque type d'instruction, le calcul de la complexité d'un algorithme se fait en partant des complexités des instructions simples, et en calculant, de proche en proche, les complexités des instructions non simples à partir des résultats déjà calculés. Ces calculs procèdent en quelque sorte par des regroupements en suivant la structure de l'algorithme.

Complexité de la recherche du minimum

Prenons l'exemple de la recherche du minimum c'est-à-dire du traitement suivant (après traduction en utilisant un while en ayant n = len(s):

1     res = 0                    
2     i = 1                      
3     while i < n:          
4        if s[i][0] < s[res][0]: 
5           res = i  
6        i = i+1
7     return res
Nous supposons que chaque instruction simple est prise en compte pour le calcul de la complexité.

Rappelons que le traitement, comme tout algorithme, peut être décomposé sous forme d'arbre syntaxique comme donné par la figure suivante où chaque noeud représente une instruction Python simple ou composée.

recherche du minimum

Décomposition d'un traitement en suivant la structure

Les noeuds sans fils, appelés les feuilles de l'arbre, correspondant aux instructions 1, 2, 5, 6 et 7, représentent des instructions d'assignations simples ou return qui, d'après la règle 1, sont en \(O(1)\).

De ce fait, d'après la règle 3, le noeud 4-5 correspondant à l'instruction if est en \(O(1)\).

D'après la règle 2, la complexité de la séquence d'instructions 4-6 est en \(O(1)\).

On peut maintenant évaluer la complexité du while (noeud 3-6), il s'exécute \(n-1\) fois et la complexité du corps de la boucle est, comme on vient de le voir, en \(O(1)\). Donc d'après la règle 4, la complexité du while est en \(O(n)\).

Finalement, d'après la règle 2, la complexité de tout le traitement est en \(O(1+1+n+1)\) qui peut être simplifié par \(O(n)\).

Note

  • Si, par exemple, un algorithme \(A\) est en \(O(n)\) et un algorithme \(B\) est en \(O(n^2 )\), \(A\) est 'meilleur', en terme, de complexité que \(B\).

    Par contre si \(A\) et \(B\) sont tous les deux en \(O(f(n))\), il faut détailler le calcul de la complexité pour déterminer lequel est plus complexe que l'autre.

  • D'après la définition du \(O\), l'algorithme de recherche du minimum est en \(O(n)\) et donc trivialement également en \(O(n^2)\), \(O(n^3)\), ..., \(O(n^n)\). Lorsque l'on cherche la complexité d'un algorithme, on essaye bien évidemment de donner la valeur la plus précise (Exemple: \(O(n)\) pour la recherche du minimum)

  • Rappelons que l'on peut évaluer plusieurs complexités différentes. Par exemple, pour les algorithmes de tris de liste, on peut regarder la complexité en terme de nombre d'instructions ou seulement regarder les instructions qui effectuent des déplacements d'éléments (le déplacement d'un élément peut prendre beaucoup plus de temps que les autres instructions). Certains tris sont en \(O(n^2)\) si l'on regarde toutes les instructions, mais en \(O(n)\) en terme de déplacement d'informations.

Complexité de la recherche séquentielle et dichotomique

Il est facile de voir que l'algorithme de recherche séquentielle, vue plus haut, est également en \(O(n)\)\(n\) est la longueur de la liste et en supposant que les tests s[i] == x sont effectués en \(O(1)\).

Recherche dichotomique

Une version Python de l'algorithme classique de recherche dichotomique de l'indice d'un élément dans un vecteur (une liste python) s est donné ici :

def recherche_dichotomique(s,x):                                # O(log n)
  """Renvoie un indice où se trouve la valeur de x dans s
  None s'il n'existe pas.
  La méthode de recherche dichotomique ou binaire est utilisée.
  """
  bi, bs = 0, len(s)                                            # O(1)
  m = (bi+bs)//2                                                # O(1)
  while bi < bs and x != s[m][0]:                               # O(log n) (O(log n) itérations)
     m = (bi+bs)//2                                                # O(1)
     if s[m][0] < x:                                               # O(1)
        bi = m+1                                                     # O(1)
     else:                                                         # O(1)
        bs = m  # x est avant ou est trouvé                          # O(1)

  if  len(s) <= m or s[m][0] != x:  # pas trouvé                # O(1)
      m = None                                                    # O(1)
  return m                                                      # O(1)

Attention, ici on suppose que chaque élément de s contient un couple avec la clé en sous composante 0 et une information satellite en sous composante 1. Ainsi s[m][0] représente la clé de l'élément d'indice m dans la liste et s[m]représente tout l'élément (clé et information satellite).

Pour calculer la complexité de la recherche dichotomique, en utilisant les règles vues précédemment, on peut assez rapidement observer que la complexité moyenne ou maximale en nombre d'actions élémentaires de cet algorithme est en \(O(f(n))\)\(f(n)\) est le nombre respectivement moyen \((f_{moyen(n)})\) ou maximum \((f_{max(n)})\) de fois que la boucle while est exécutée.

Pour évaluer \(f_{max(n)}\), commençons par analyser le comportement de l'algorithme. Nous pouvons tout d'abord remarquer qu'à chaque tour de boucle, au pire des cas, l'intervalle de recherche est divisé par deux, quelle que soit la valeur de x.

La figure suivante donne une évolution possible de l'intervalle de recherche dans s pour une liste à 100 éléments en supposant que x n'est pas dans s mais que s[40] < x < s[41]

image

Evolution de l'intervalle de recherche lors d'une recherche dichotomique

Le while s'exécute donc au maximum 7 fois. De façon générale on peut voir que:

\(2^{f_{max}(n)-1} \leq n < 2^{f_{max}(n)}\)

et donc que \(f_{max(n)} <= \log_2(n) + 1\)

La recherche dichotomique a donc une complexité maximale en \(O(ln \; n)\). On peut calculer que la complexité moyenne (en supposant ou non que x est dans s) est également en \(O(ln \; n)\).

Notons que dans la section algorithmique, nous verrons que cette complexité peut être calculée avec le master theorem (https://fr.wikipedia.org/wiki/Master_theorem) et la relation de récurrence \(T(n) = T(n/2) + O(1)\)

Complexité du tri par sélection

Soit une solution Python du tri par sélection :

def tri_selection(s):                                            # O(n^2)
   """Trie  la liste s par sélection."""
   n = len(s)                                                    # O(1)
   for i in range(n-1):                                          # O(n^2) (O(n) itérations)
      # recherche du min dans s[i..n]
      min = i # min = indice du min provisoire                     # O(1)
      for j in range(i+1,n):                                       # O(n) (O(n) itérations)
        if  s[j][0] < s[min][0]:                                      # O(1)
           min = j                                                       # O(1)
      # placement du ième élément: échange s[i]<->s[min]
      s[min],s[i] =  s[i],s[min]                                   # O(1)

où l'on suppose ici aussi, le vecteur s composé de couples (clé, information satellite).

Pour calculer la complexité maximale du tri par sélection décomposons l'algorithme sous forme d'arbre en suivant sa structure; ceci est donné en figure suivante:

image

Décomposition du tri par sélection

En supposant que toutes les instructions et les traitements de passages de paramètres interviennent dans ce calcul, en suivant les règles pour calculer cette complexité, nous obtenons :

  • 1, 5, 8, 11 et 13 , sont en \(O(1)\)
  • le if (10-11) est en \(O(1)\)
  • le for (9-11) imbriqué est en \(O(n-i)\) et peut être borné par \(O(n)\)
  • le for global (6-13) est en \(O(n^2)\)
  • la procédure tri_selection (1-13) est en \(O(n^2)\)

Ce calcul peut être raffiné mais les résultats restent en \(O(n^2)\).

Complexité du tri par insertion

Soit une solution Python du tri par insertion :

def tri_insertion(s):                                            # O(n^2)
   """Trie liste s par insertion."""
   n = len(s)                                                    # O(1)
   for i in range(1,n):                                          # O(n^2) (O(n) itérations)
      Save = s[i]   #utilisé pour l'échange                        # O(1)
      # insertion de s[i]
      j = i-1                                                      # O(1)
      while j>=0 and s[j][0] > Save[0]:                            # O(n) (O(n) itérations)
         s[j+1] = s[j]                                                 # O(1)
         j=j-1                                                         # O(1)
      s[j+1] = Save                                                # O(1)

En analysant l'algorithme de tri par insertion, on peut voir que sa complexité maximale est également en \(O(n^2)\). On peut voir que la complexité minimale est rencontrée dans le cas où la liste est déjà triée et vaut \(O(n)\)

Complexité du tri par échange ou tri Bulle

Soit une solution Python du tri par échange simple :

def tri_bulle(s):                                                            # O(n^2)
   """Trie les n premières composantes de la liste s par méthode Bulle."""
   n = len(s)                                                                # O(1)
   for i in range(n,1,-1):  # réarrange s[0..i]                              # O(n^2) (O(n) itérations)
      for j in range(i-1):                                                     # O(n) (O(n) itérations)
         if s[j][0] > s[j+1][0]:                                                  # O(1)
           s[j], s[j+1] = s[j+1], s[j]                                               # O(1)

Ici aussi la complexité maximale est en \(O(n^2)\). La complexité minimale est également en \(O(n^2)\).

Complexité du tri par énumération

Soit une solution Python du tri par `énumartion où l'on suppose les valeurs possibles en \(0\) et \(m - 1\) :

m = 5

def tri_enumeration(s):
   """Trie les n premières composantes de la liste s par énumération."""
   n = len(s)                                      # O(1)
   w = [0]*n                                       # O(n)
   count = [-1]+[0]*(m-1)                          # O(m)

   # 1 Comptage
   for j in range(n):                              # O(n) (O(n) itérations)
      count[s[j][0]] +=1                             # O(1)

   # 2 Cumul des compteurs
   for i in range(1,m):                            # O(m) (O(m) itérations)
     count[i] += count[i-1]                          # O(1)

   # 3 Placement des éléments dans w
   for j in range(n-1,-1,-1):                      # O(n) (O(n) itérations)
     w[count[s[j][0]]] = s[j]                        # O(1)
     count[s[j][0]] -= 1                             # O(1)

   # 4 Recopiage de w dans s
   s[:] = w                                        # O(n)

Si \(m < n\), la complexité moyenne et maximale de ce tri est en \(O(n)\) ce qui est remarquable.

Quelques exemples intéressants

Le calcul ds exemples suivants est intéressant (on considère que m, l et n sont des paramètres entiers positifs).

   i = 1
   while i < n**3 :
      i=i*2
   for i in range(n):
     for j in range(m):
        for k in range(l):
            print('hello')
   i = 2
   while i < n:
      i=i*i

Complexité des manipulations des séquences de données python

Voir le site wiki python pour plus de détails:

https://wiki.python.org/moin/TimeComplexity

On suppose que \(n\) est le nombre d'éléments dans la liste et \(k\) la valeur (ex: longueur) du paramètre.

La complexité moyenne suppose que les paramètres sont générés uniformément de façon aléatoire.

Complexité des opérations sur les listes

De façon interne, une liste est représentée sous forme de vecteur où les composantes sont contiguës en mémoire et avec, en moyenne, de la place libre pour allonger la liste. La pire opération est donc une insertion ou suppression en début de liste car toutes les composantes doivent bouger. Malheureusement, au pire des cas, un simple s.append(x) peut demander de recopier toute la liste s'il n'y a plus de place libre juste après la liste s.

Opération Complexité moyenne Complexité maximale
Copy O(n) O(n)
Append O(1) O(n)
Insert O(n) O(n)
Get Item O(1) O(1)
Set Item O(1) O(1)
Delete Item O(n) O(n)
Iteration O(n) O(n)
Get Slice O(k) O(k)
Del Slice O(n) O(n)
Set Slice O(k+n) O(n+k)
Extend O(k) O(n+k)
Sort O(n log n) O(n log n)
Multiply O(nk) O(nk)
x in s O(n) O(n)
min(s), max(s) O(n) O(n)
len(s) O(1) O(1)

Complexité des opérations sur les ensembles

L'implémentation des ensembles est similaire à celle des dictionnaires (voir plus bas).

Opération Complexité moyenne Complexité maximale
x in s \(O(1)\) \(O(n)\)
s \| t \(O(len(s)+len(t))\) \(O(len(s) * len(t))\)
s & t \(O(max(len(s),len(t))\) \(O(len(s) * len(t))\)
s - t \(O(max(len(s),len(t))\) \(O(len(s) * len(t))\)
s ^ t \(O(max(len(s),len(t))\) \(O(len(s) * len(t))\)

Complexité des opérations sur les dictionnaires

Avec l'interpréteur que nous utilisons, un dictionnaire Python est stocké dans une table (zone mémoire contiguë). Pour simplifier supposant que c'est une table à MAX composantes (par exemple pour un petit dictionnaire MAX = 100.

L'accès à une composante du dictionnaire (Get Item) se fait par hashing (hash(cle) % 100) qui calcule un indice entre 0 et MAX-1. En moyenne cet indice correspond à l'emplacement dans la table où l'élément (clé et valeur) va être stocké. Cette opération (hashing, modulo et accès à la table) prend un temps constant O(1).

La complexité moyenne suppose que les collisions sont rares avec la fonction de hashage (ce qui est généralement la cas).

Le cas moyen suppose que les paramètres sont choisis uniformément aléatoirement parmi les clés possibles.

Malheureusement, il peut y avoir des collisions. Au pire des cas, pour un dictionnaire de néléments, l'accès à un élément aura n-1 collisions plus le dernier hashing et prend un temps (complexité maximale) en O(n).

En terme de complexité, placer un élément (Set Item) revient à y accéder suivit du stockage de l'élément qui est en O(1) en moyenne et O(n) en complexité maximale, soit la même complexité que l'accès à un élément.

Opération Complexité moyenne Complexité maximale
Copy O(n) O(n)
Get Item O(1) O(n)
Set Item O(1) O(n)
Delete Item O(1) O(n)
Iteration O(n) O(n)