Complexité en temps

I. Approche intuitive de la complexité en temps

Une première façon d'estimer la complexité en temps d'un algorithme est de l'exécuter sur des problèmes de tailles différentes et d'étudier la courbe obtenue. Pour chaque taille de problème, il faut faire la moyenne sur plusieurs exécutions, avec des données aléatoires, et en essayant de limiter au maximum la charge de la machine. On obtient alors une idée approximative de la complexité en temps d'un algorithme.

Une autre façon consiste à incrémenter un compteur à chaque opération "coûteuse" et à procéder comme précédemment, mais à utiliser la valeur de ce compteur plutôt que le temps mis. On a alors des valeurs qui ne sont plus sujettes aux perturbations extérieures, mais cela reste approximatif et intuitif.

Ces 2 méthodes présentent en plus l'inconvénient d'être éventuellement lentes, puisqu'elles prennent le temps nécessaire à l'exécution.

À titre d'exemples, vous pouvez regarder les fichiers complexiteTemps01fibo.py — en testant jusqu'à fibo(40) — et complexiteTemps02recherche.py — en testant jusqu'à un tableau de 1000 cases.

II. Calcul formel de la complexité en temps

Le meilleur moyen de connaître la complexité en temps d'un algorithme est de la calculer formellement. Pour ce faire, on va en général compter "1" pour les opérations les plus lourdes, et on négligera les autres.

Application à fibonacci : cas trivial

cplx(0) = 0
cplx(1) = 0
cplx(n) = cplx(n-1) + cplx(n-2) + 1 ≡ fibo(n)

Application à la recherche naïve :

Complexité au pire : il faut parcourir toute la liste, soit n étapes

cplx(n) = O(n)

Complexité en moyenne : il faut effectuer de 1 à n étapes de façon équiprobable, soit (n(n+1)/2)/n ≡ n/2

cplx(n) = O(n/2)

Application à la recherche dichotomique

Complexité au pire : on ne trouve l'élément qu'une fois arrivée à une liste de taille 1

u(1) = 1
u(n) = 1 + u(n/2)
Hypothèse : u(n) ≡ O(log₂(n))
u(n) = 1 + u(n/2) ≡ 1 + O(log₂(n/2)) ≡ log₂(n)

III. Exercices

Exercice 1 : faire une comparaison graphique empirique des complexités en temps des algorithmes de tri suivant :

tri à bulle
tri rapide
tri fusion

Ci-dessous figurent 2 propositions de correction. La première n'effectue le tri qu'une fois pour chaque taille de liste, la deuxième 1000 fois. Les bibliothèques utilisées sont accessibles en bas de la page.

import matplotlib.pyplot as plt
from random import randint

from calcTemps import calcTempsFonction

from triBulle import triBulle
from triFusion import triFusion
from triRapide import triRapide

def genererListe(n):
    liste = []
    for i in range(0, n):
        liste.append(randint(1,100))
    return liste

tailles = [n for n in range(0, 1000)]
listeListes = list(map(genererListe, tailles))

print(listeListes)
tempsBulle = list(map(lambda x: calcTempsFonction(triBulle, x), listeListes))
tempsFusion = list(map(lambda x: calcTempsFonction(triFusion, x), listeListes))
tempsRapide = list(map(lambda x: calcTempsFonction(triRapide, x), listeListes))
print(tempsBulle)
print(tempsFusion)
print(tempsRapide)

plt.plot(tailles, tempsBulle)
plt.plot(tailles, tempsFusion)
plt.plot(tailles, tempsRapide)

plt.show()

import matplotlib.pyplot as plt
from random import randint

from calcTemps import calcTempsFonction

from triBulle import triBulle
from triFusion import triFusion
from triRapide import triRapide

def genererListe(n):
    liste = []
    for i in range(0, n):
        liste.append(randint(1,100))
    return liste

def genererNListes(n,t):
    retour = []
    for i in range(0, n):
        retour.append(genererListe(t))
    return retour

tailles = [n for n in range(0, 50)]
listeListes = list(map(lambda x:genererNListes(1000,x), tailles))

print(listeListes)
#tempsBulle = list(map(lambda x: calcTempsFonction(triBulle, x), listeListes))
tempsBulle = list(map(lambda x: sum(map(lambda y: calcTempsFonction(triBulle, y),x)), listeListes))
tempsFusion = list(map(lambda x: sum(map(lambda y: calcTempsFonction(triFusion, y),x)), listeListes))
tempsRapide = list(map(lambda x: sum(map(lambda y: calcTempsFonction(triRapide, y),x)), listeListes))
#print(tempsBulle)
#print(tempsFusion)
#print(tempsRapide)

plt.plot(tailles, tempsBulle)
plt.plot(tailles, tempsFusion)
plt.plot(tailles, tempsRapide)

plt.show()

Exercice 2 : établir formellement la complexité du tri à bulle.

IV. Annexes : bibliothèques utilisées plus haut

  from time import time

  def calcTempsFonction(f,param):
      t1 = time()
      f(param)
      t2 = time()
      return t2 - t1

  def triBulle(liste):
      inversion = True

      while (inversion == True):
          inversion = False
          i = 0
          while (i < len(liste)-1):
              if (liste[i] > liste[i+1]):
                  liste[i:i+2] = [liste[i+1],liste[i]]
                  inversion = True
              i = i + 1

  from random import randint

  def triRapide(liste):
      """
      fonction qui initialise la fonction récursive de tri rapide d'une liste.
      """
      trier(liste, 0, len(liste)-1)

  def trier(liste, indiceDebut, indiceFin):
      """
      fonction récursive qui trie une liste en utilisant la méthode trie rapide.
      """
      if (indiceFin <= indiceDebut):
          return
      indicePivot = randint(indiceDebut, indiceFin)
      pivot = liste[indicePivot]
      indicePivot = partitionner(liste, pivot, indiceDebut, indicePivot, indiceFin)
      trier(liste, indiceDebut, indicePivot-1)
      trier(liste, indicePivot+1, indiceFin)

  def partitionner(liste, pivot, indiceDebut, indicePivot, indiceFin):
      """
      fonction qui partitionne une liste en fonction d'un pivot en mettant à gauche
      du pivot les éléments plus petits que le pivot et à droite les éléments plus
      grand. L'indice du pivot est susceptible d'être modifié au cours du traitement ;
      il est donc renvoyé par cette fonction.
      """
      termine = False
      indiceCourant = indiceDebut
      while indiceCourant <= indiceFin:
          if liste[indiceCourant] > pivot and indiceCourant < indicePivot:
              liste[indicePivot] = liste[indiceCourant]
              liste[indiceCourant] = liste[indicePivot-1]
              liste[indicePivot-1] = pivot
              indicePivot = indicePivot - 1
          elif liste[indiceCourant] < pivot and indiceCourant > indicePivot:
              liste[indicePivot] = liste[indiceCourant]
              liste[indiceCourant] = liste[indicePivot+1]
              liste[indicePivot+1] = pivot
              indicePivot = indicePivot + 1
          else:
              indiceCourant = indiceCourant + 1
      return indicePivot

  from random import randint

  def triFusion(liste):
      """
      renvoie une version triée d'une liste en utilisant la méthode du tri fusion.
      """
      taille = len(liste)
      if taille <= 1:
          return liste
      milieu = int(taille/2)
      return fusionner(triFusion(liste[:milieu]), triFusion(liste[milieu:]))

  def fusionner(listeA, listeB):
      """
      fonction qui fusionne 2 listes triées
      """
      fusion = []
      teteA = listeA[0]
      teteB = listeB[0]
      while (len(listeA) > 0 and len(listeB) > 0):
          if teteA < teteB:
              fusion.append(teteA)
              listeA.pop(0)
              if len(listeA) > 0:
                  teteA = listeA[0]
          else:
              fusion.append(teteB)
              listeB.pop(0)
              if len(listeB) > 0:
                  teteB = listeB[0]
      fusion = fusion + listeA + listeB
      return fusion