Skip to content

Découpe en vidéos de Notion de complexité et grand O

Vidéo 1: Parlons d'efficacité d'un programme

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.

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

Nous verrons dans ce qui suit 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.

Vidéo 2: 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" ou dans un script ou une console Python

Par exemple dans un terminal l'instruction

python3 -m timeit -n 5 "print('coucou')"

mesure le temps d'exécution pris pour exécuter 5 fois le code donné en paramèrre.

$ 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 : supposons qur nous désirions analyser 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 dont on multiplie la longueur par deux à chaque itération, et donnons 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.

Vidéo 3: 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 du minimum dans une liste Python s de petits entiers, 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 = 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

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. Si nous faisons des hypothèses simplificatrices que toutes les valeurs de la liste sont différentes et distribuées uniformément, nous obtenons :

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

Tout cela fait beaucoup de calculs juste pour 7 lignes de codes. Essayons de trouver plus simple !

Vidéo 4: 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\).

Le graphique montre qu'à partir de \(n\) valant quelques dizaines, \(2^n\) prend le pas sur \(n^4\) qui prend le pas sur \(15n^2\) et encore plus sur \(100n\)

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\)).

De façon générale, quand on regarde les complexités on voit un classement dans les fonctions n exposant n plus grand que 2 exposant n qui elle-même est plus grand que n exposant 3, plus grand que n exposant 2, plus grand que n log n plus grand que n plus grand que log de n plus grand que 1.

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 en terme de complexité. Pour cela, on utilise la notation grand \(O\), 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 en \(O(f(n))\) si \(\exists N, c > 0 .\;\forall n > N \; T(n) \leq 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. Par exemple que \(T(n)=n\) ou \(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)\).

Vidéo 5: 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 :

D'abord les code qui prennent un temps borné qui sont en \(O(1)\) complexité constant ensuite les algorithmes de complexité logarithmique en \(O(log \, n)\) ensuite linéaires en \(O(n)\) ensuite \(O(n \, log \, n)\) ensuite les algorithmes à complexité polynomiales \(O(n^2 )\) : quadratique,
\(O(n^3 )\) , cubique, etc

Ensuite les complexités exponentielles avec \(O(2^n )\) , \(O(3^n )\) , ETC, \(O(n^n )\) , exponentiel en base n et ainsi de suite

Classes de complexité

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 de la recherche du minimum, 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 l'on regarde la complexité en temps d'exécution et si 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\)).

Par exemple, en comptabilisant le temps de toutes les instructions, chacune des instructions suivantes est en O(1) :

  x = 3.14
  z = 3 ** 25 + x - 36
  x == 3.14
  print(3.14)
  y = int(input()) (pour une petite valeur lue)

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)\).

Par exemple la séquence de toutes les instructions simples précédentes est 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)\).

Par exemple le code suivant est en \(O(1)\)

   a = int(input())                          # O(1)
   if (a > 100):                             # O(1)
       print('a dépasse le centaine')         #   O(1)
   else:                                     # O(1)
       print('a ne dépasse pas la centaine')  # O(1)

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

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))\).

Par exemple, la fonction de recherche dans une liste s, de l'indice i de l'élément de s dont la composante \(s[i][0]\) vaut x en est \(O(n)\)\(n\) est la taille de s(on suppose que les éléments de s sont des tuples.)

def recherche(s,x):                      # O(n)
   """Renvoie l'indice où se trouve la valeur x dans s.

   None si x n'existe pas.
   """
   i = 0                                 # O(1)
   while i < len(s) and s[i][0] != x:    # O(n) (cond en O(1), nb d'it en O(n))
      i = i+1                              # O(1)
   if i == len(s)                        # O(1)
      i = None # pas trouvé                # O(1)
   return i                              # O(1)

Règle 5 (for)

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

Donnons de simples exemples de complexité avec des for

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

est en \(O(1)\) car le nombre d'itération est de \(100\) qui est en \(O(1)\).

Par contre, pour une liste s de taille \(n\) d'entiers (de petite valeur) où \(n\) est un paramètre qui dépend de la taille du problème :

   for elem in s:
       print(elem)

est en \(O(n)\).

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.

Par exemple on peut voir que la complexité de la fonction ecrit_carre_nxn est en \(n^2\)n est l'entier reçu en paramètre. Si l'on appelle cette fonction avec la valeur taille ** 3taille est un entier lu, la complexité résultant de l'exécution est donc en \(O(taille^6)\) (soit \(O(n^2)\) pour \(n = taille^3\)).

   def ecrit_carre_nxn(n):        #     complexité de la fonction O(n^2)
       for i in range(n):
            for j in range(n):
                print('X', end='')
            print()

   taille = int(input())                                  #     O(1)
   ecrit_carre_nxn(taille**3) # carré de taille taille^3  #     O((taille^3)^2) = O(taille^6)

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.

Vidéo 6 : 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 = s[0]                 
2     i = 1                      
3     while i < len(s):                
4        if s[i] < res:             
5           res = s[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.

Arbre syntaxique du code  de 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)\)

Vidéo 7 : complexité des tris simples

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

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

Pour le tri par échangé, également appelé, tri bulle, la complexité maximale est également en \(O(n^2)\). Ici, la complexité minimale est aussi 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.

Vidéo 8 : Complexité des manipulations de séquences de données python

La complexité des manipulation des séquences de données sont dépendantes de l'implémentation de python utilisée.

Nous nous basons donc sur l'implémentation CPython utilisé au moins jusqu'à la version Python 3.10.

Dans ce qui suit, on suppose que \(n\) est le nombre d'éléments dans la séquence 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 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)