Complexité d’un algorithme

Le calcul de la complexité d’un algorithme permet de mesurer sa performance.

Il existe deux types de complexité :

• complexité spatiale : permet de quantifier l’utilisation de la mémoire
• complexité temporelle : permet de quantifier la vitesse d’exécution

Complexité temporelle

L’objectif d’un calcul de complexité algorithmique temporelle 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.

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 !

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

Puisqu’il s’agit seulement de comparer des algorithmes, les règles de ce calcul doivent être indépendantes :

• du langage de programmation utilisé ;
• du processeur de l’ordinateur sur lequel sera exécuté le code ;
• de l’éventuel compilateur employé.

Par soucis de simplicité, on fera l’hypothèse que toutes les opérations élémentaires sont à égalité de coût, soit 1 « unité » de temps.

Exemple : a = b * 3  : 1 multiplication + 1 affectation = 2 « unités »

La complexité en temps d’un algorithme sera exprimé par une fonction, notée \(T\) (pour Time), qui dépend :

• de la taille des données passées en paramètres : plus ces données seront volumineuses, plus il faudra d’opérations élémentaires pour les traiter.
  On notera \(n\) le nombre de données à traiter.
• de la donnée en elle même, de la façon dont sont réparties les différentes valeurs qui la constituent.
  par exemple, si on effectue une recherche séquentielle d’un élément dans une liste non triée, 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.

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

• la complexité dans le meilleur des cas : c’est la situation la plus favorable,
  par exemple : recherche d’un élément situé à la première position d’une liste
• la complexité dans le pire des cas : c’est la situation la plus défavorable,
  par exemple : recherche d’un élément dans une liste alors qu’il n’y figure pas

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.

Ordre de grandeur

Pour comparer des algorithmes, il n’est pas nécessaire d’utiliser la fonction \(T\), mais seulement l’ordre de grandeur asymptotique, noté \(\mathcal{O}\) (« grand O »).

Une fonction \(T(n)\) est en \(\mathcal{O}\left(f(n)\right)\) (« en grand O de f(n)« ) si :

\(\exists n_0\in\mathbb{N}, \exists c\in\mathbb{R^+}, \forall n\in\mathbb{R^+}, n\geq n_0 \Rightarrow |T(n)|\leq c|f(n)|\)

Autrement dit :

\(T(n)\) est en \(\mathcal{O}\left(f(n)\right)\) s’il existe un seuil \(n_0\) à partir duquel la fonction \(T\) est toujours dominée par la fonction \(f\), à une constante multiplicative fixée \(c\) près.

Exemples :

• \(T_1(n)=7=\mathcal{O}(1)\)
• \(T_2(n)=12n+5=\mathcal{O}(n)\)
• \(T_3(n)=4n^2+2n+6=\mathcal{O}(n^2)\)
• \(T_4(n)=2+(n-1)\times 5=\mathcal{O}(n)\)

Classes de complexité

Exemple de calcul de complexité

def factorielle(n):
   fact = 1
   i = 2

   while i <= n:
      fact = fact * i
      i = i + 1
   return fact

.
affectation : 1
affectation : 1
.
itérations : au plus x(n − 1)
   comparaison : 1
   multiplication + affectation : 2
   addition + affectation : 2

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

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

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

def factorielle(n):
   fact = 1 
   i = 2
   while i <= n:
      fact = fact * i
      i = i + 1
   return fact

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]

def fonction_2(n):
   for i in range(n):
      print("Bonjour!")

n = 100
s = 0
for i in range(n):
   a = n
   while a > 1:
      a = a/2
   s += 1

n = 100             # 1
s = 0               # 1
for i in range(n):     # 1  x n
   a = n               # 1
   while a > 1:           # 1 x log2(n)
      a = a/2             # 2
   s += 1              # 2

sources : https://gargantua.polytechnique.fr/siatel-web/linkto/mICYYYTEsXY6
http://igm.univ-mlv.fr/~alabarre/teaching/struct/poly-m1103.pdf
https://www.supinfo.com/cours/2ADS/chapitres/01-notion-complexite-algorithmique

 Comparaison de complexité

Pour comparer plus finement la complexité de plusieurs algorithmes, on peut utiliser un script de ce type, utilisant le module timeit de Python.

import timeit
import matplotlib.pyplot as pl
import numpy as np
from random import *


########################################################################################################
# Comparaison des complexités
########################################################################################################
pl.subplot(2,1,2)

# Différentes tailles pour tracé de courbes
n = range(taille//40, taille, taille//40)

# liste des fonctions à comparer
liste_fct = [......] 

for fct in liste_fct:
    print(fct.__name__)
    d = []
    Y = []
    for i in n:
        d.append( timeit.timeit("fct()", globals=globals(), number=100))
    Y.append(np.array(d))

    p, = pl.plot(n, Y[0], label = fct.__name__)
    pl.fill_between(n, Y[1], Y[2], color = pl.getp(p, 'color'), alpha=0.5)

pl.legend(loc=2)
pl.xlabel('taille')
pl.ylabel('durée [s]')
pl.show()