Algorithmique : coût et complexité

I) Une remarque de bon sens
II) Efficacité spatiale, efficacité temporelle
III) Evaluer l'efficacité d'un algorithme
    1) En calculant la durée d'exécution
    2) Coût d'un algorithme
    3) Opérations élémentaires
    4) Exemple
    5) Des hypothèses pour simplifier les calculs
    6) La taille des données
    7) Objectif
    8) Exemples de calculs de coût
IV) Estimation du coût d'un algorithme: la complexité
    1) Rappels mathématiques: O, o, ∼
    2) Complexité
    3) Ordre de grandeur des temps d'exécution
V) Calcul expérimental de la complexité d'un algorithme
    1) Pourquoi faire un calcul expérimental de la complexité ?
    2) Hypothèse et méthode de calcul de la complexité
    3) Ordres de grandeur
    4) Calcul du temps d'exécution et estimation la complexité d'une fonction f(n) en Python
VI) Exemples de calculs théoriques de la complexité
    1) Le tri par ordre croissant d'une liste de nombres
    2) Le test de primalité
    3) Algorithme d'Euclide

I) Une remarque de bon sens

  Imaginez par exemple qu'après avoir lancé une requête sur un moteur de recherche, il faille attendre plusieurs heures pour avoir le résultat ! Les moteurs de recherche n'auraient pas autant de succès...
  Un algorithme doit déjà être correct, c'est-à-dire faire qu'il est supposé faire ! Mais il doit aussi être efficace, c'est-à-dire donner “rapidement” la réponse.

  La preuve de la correction d'un algorithme est traité dans un autre document, on s'intéresse ici à l'efficacité.

II) Efficacité spatiale, efficacité temporelle

  Evaluer l'efficacité spatiale d'un algorithme c'est calculer la quantité de mémoire (la RAM) maximale nécessaire à l'exécution de l'algorithme. Plus cette quantité de mémoire est petite, plus grande est l'efficacité spatiale de l'algorithme.

  Evaluer l'efficacité temporelle d'un algorithme c'est calculer la durée nécessaire à l'exécution de l'algorithme. Plus cette durée est petite, plus grande est l'efficacité temporelle de l'algorithme.  

  Tant que la quantité de RAM nécessaire ne dépasse pas la quantité maximale disponible sur une machine, la mesure de l'efficacité spatiale n'a pas d'intérêt. Les algorithmes sont tous aussi performants. Par contre, en cas de dépassement du seuil maximal, la machine doit utiliser une partie d'un disque dur comme mémoire d'appoint. Le traitement des instructions est alors très ralenti, les temps d'accès aux données explosent et les taux de transfert de données s'effondrent: c'est la catastrophe...
  Pour dépasser ce seuil, sur des machines modernes qui disposent de plusieurs Go de RAM, il faut manipuler de très grosses données (un bitmap de 3000x4000 pixels pèse 36 Mo par exemple, il y a encore de la place...) ou avoir conçu un algorithme très vorace en mémoire (une fonction récursive maladroite, par exemple).

Dans la suite de ce cours nous nous intéresserons uniquement à l'efficacité temporelle d'un algorithme.

III) Evaluer l'efficacité d'un algorithme

1)  En calculant la durée d'exécution

   La première idée est de penser que l'efficacité d'un algorithme peut être mesurée le temps que met à s'exécuter un programme traduisant cet algorithme. Mais un grand nombre de critères interviennent. Par exemple:

    •    le langage de programmation utilisé pour traduire l'algorithme
    •    le processeur et le type de mémoire de l'ordinateur utilisé
    •    les autres programmes s'exécutant sur l'ordinateur (qui peuvent ralentir le programme testé)

  La durée d'exécution permet de comparer l'efficacité de deux algorithmes traduits dans le même langage et exécutés sur le même ordinateur, mais ne permet pas d'évaluer l'efficacité intrinsèque d'un algorithme.

2) Coût d'un algorithme

  La seconde (et la bonne) idée pour évaluer l'efficacité d'un algorithme est de compter le nombre d'opérations élémentaires effectuées par cet algorithme lors de son exécution.

Le coût d'un algorithme  est le nombre d'opérations élémentaires effectuées par cet algorithme.

3) Opérations élémentaires

On appelle opération élémentaire l'une des actions suivantes:
    •    faire une opération mathématique de base (addition, soustraction, multiplication, division)
    •    lire une valeur contenue dans une variable
    •    affecter une valeur à une variable
    •    effectuer un test
    •    faire une opération booléenne (“et”, “ou”, “non”)

4) Exemple

1.    def somme_entiers(n):
2.        total =  0
3.        while n > 0:
4.                total = total + n
5.                n  = n - 1
6.        return total

Cette fonction (qui calcule la somme des entiers de 1 à n) fait:
    •    2n opérations mathématiques (n×L4 + n×L5)
    •    4n + 1 lectures ( n×L3 + 2n×L4 + n×L5  + L6)
    •    2n + 1 affectations ( L2 + n×L4 + n×L5)
    •    n comparaisons (n×L3)
Le coût est de 9n + 2 opérations élémentaires

5) Des hypothèses pour simplifier les calculs

Remarquons que:
     • Parmi ces opérations certaines prennent en pratique plus de temps que d'autres.
    • Pour une même opération, le temps d'exécution est proportionnel à la taille des données (pour la multiplication des entiers, par exemple).

On fait alors les hypothèses suivantes pour ne pas rendre les calculs inextricables:

    • Nous ferons l'approximation que toutes ces opérations élémentaires prennent le même temps.
    • Nous compterons souvent non pas toutes les opérations élémentaires, mais seulement une partie d'entre elles, suivant le type d'algorithme. Il faudra choisir les opérations élémentaires les plus significatives de l'algorithme. Les opérations élémentaires à prendre en compte seront en général précisées.

6) La taille des données

   La taille des données d'un algorithme est (en général) un entier n qui “mesure” les données à traiter. Comme un algorithme est ici écrit comme une fonction, les données à traiter sont les paramètres d'appels de cette fonction.

Les cas fréquents sont:
     • donnée = entier n                → taille = n (parfois nombre de bits nécessaires pour coder n)
    • donnée = liste                    → taille  = longueur de la liste
    • donnée = plusieurs entiers             → taille = par exemple le plus grand des entiers, où l'un des entiers

7) Objectif

  Nous chercherons à calculer le coût (ou plutôt la complexité, une estimation du coût, voir paragraphe suivant) en fonction de la taille des données.

8) Exemples de calculs de coût

a) Une suite récurrente double

Calculer le coût en opérations élémentaires (somme, produit, racine) de cet algorithme en fonction de n

def moy_arithm_geom(a, b, n):
    for i in range(n):
        a, b = 0.5 *(a + b), sqrt(a * b)
    return b

  Dans chacune des n itérations, il y a 2 multiplications, une addition et un calcul de racine, soit 4 opérations. Le coût total C(n) est de 4n

b) Le tri par ordre croissant d'une liste de nombres

Calculer le nombre de comparaisons et d'affectations de cet algorithme en fonction de la longueur n de la liste.
Les éléments d'une liste s de longueur n sont s[0], ..., s[n-1]

def tri(s):
    n = len(s)
    for i in range(n - 1):
        for j in range(i, n):
            if s[i] > s[j]:
                x = s[i]
                s[i] = s[j]
                s[j] = x
    return s

  Il y a une affectation au départ ( n = ) et à l'arrivée (return ). Dans chacune des   ( n - 1 ) + ( n - 2 ) + ... + 1 = n ( n - 1 ) 2 itérations, il y a une comparaison et 0 ou 3 affectations. Au total: n ( n - 1 ) 2 comparaisons et entre 2 et 2 + 3 * n ( n - 1 ) 2 affectations suivant les données.

  Sur cet exemple simple, on voit que le coût dépend non seulement de la taille, mais de la valeur des données.

IV) Estimation du coût d'un algorithme: la complexité

  Calculer le coût exact d'un algorithme devient vite délicat, fastidieux et est souvent impossible.
  De plus, qu'il y ait n 2 ou n 2 + 2n + 3 opérations élémentaires, c'est pareil ou presque pareil lorsque n est grand. Nous allons définir un outil précis pour cette évaluation: la complexité.

  Le rôle de la complexité est d'estimer, dans le cas le plus défavorable, un ordre de grandeur du coût d'un algorithme en fonction de la taille n des données lorsque cette taille augmente et tend vers l'infini.

1) Rappels mathématiques : O, o, ∼

a) Fonctions équivalentes et notation grand O

Soient f et g deux fonctions définies sur N et à valeurs dans R * . Alors:

f et g sont équivalentes en +∞ ⇔ f ( n ) g ( n ) n + 1 . On note   f ( n ) + g ( n )   , ou f ( n ) g ( n ) et on lit “ f est équivalente à g ” .

f est dominée par g (en + ∞)  ⇔ f g est bornée en +∞ ⇔ M R + , N N / n N , | f ( n ) g ( n ) | M .
  On note alors f ( n ) = O + ( g ( n ) ) ,  ou f ( n ) = O ( g ( n ) )   et on lit “ f est un grand ô de g

b) Théorème

Si   f ( n ) g ( n ) n + L R * , c'est à dire f ( n ) L g ( n ) , alors f ( n ) = O ( g ( n ) ) .

2) Complexité

a) Paramètre de complexité d'un algorithme

   Dans les définitions qui suivent, on suppose que le coût C ( n ) d'un algorithme est fonction d'un entier n mesurant la taille des données de l'algorithme.

b) Coût “au pire”

  Parfois (souvent), on ne sait pas calculer le coût C ( n ) d'un algorithme, car ce coût varie suivant non seulement la taille, mais les valeurs des données. Mais on parvient (souvent)  à montrer que dans la pire des situations (lorsque le nombre C ( n ) est le plus grand possible par rapport à n ), alors le coût est en f ( n ) .
  Dans ce cas on dit que le coût au pire est en f ( n ) .

c) Définition

La complexité d'un algorithme est en f ( n ) lorsque le coût au pire C ( n ) de l'algorithme vérifie C ( n ) = O ( f ( n ) ) .

Il faut essayer de trouver la meilleure (la plus petite) fonction f possible.

d) Complexités usuelles

Le plus souvent, on sera dans le cas où:
    • f ( n ) = 1             : l'algorithme a une complexité constante              (rare et excellent)
    • f ( n ) = ln ( n )         : l'algorithme a une complexité logarithmique            (excellent)    
    • f ( n ) = n             : l'algorithme a une complexité linéaire                (très bon)
    • f ( n ) = n ln ( n )     : l'algorithme a une complexité quasi linéaire            (très bon)
    • f ( n ) = n 2         : l'algorithme a une complexité quadratique            (moyen)
    • f ( n ) = n 3         : l'algorithme a une complexité cubique                (mauvais)
    • f ( n ) = n p         : l'algorithme a une complexité polynomiale  (p > 3)    (très mauvais)
    • f ( n ) = a n         : l'algorithme a une complexité exponentielle  (a > 1)    (nul)
    • f ( n ) = n !         : l'algorithme a une complexité factorielle            (nul)

  Plus la complexité est “élevée”, moins l'algorithme est efficace. En pratique, à partir d'une complexité exponentielle, un algorithme n'est pas intéressant, à moins de ne pas en avoir un autre pour résoudre le problème.

e) Complexité  “en moyenne”

   Lorsque les cas (au pire) où le coût C(n) d'un algorithme est maximum et que ce coût au pire est disproportionné par rapport au cas général, il peut être intéressant de calculer le coût moyen et la complexité en moyenne de l'algorithme.

•    C moyen ( n ) = Σ d données de taille n P ( d ) C ( d ) avec { P ( d ) = probabilité d ' avoir la donnée d C ( d ) = coût de l ' algorithme pour la donnée d
• complexité moyenne = f ( n ) C moyen ( n ) = O ( f ( n ) )

3) Ordre de grandeur des temps d'exécution

  On suppose que l'ordinateur effectue un milliard d'opérations élémentaires par seconde. (En pratique, Python en effectue beaucoup moins, plutôt quelques dizaines de millions suivant le PC). On donne le temps d'exécution T(n) en fonction de n suivant la complexité C(n) de l'algorithme.

n \ C ( n ) ln ( n ) n n ln ( n ) n 2 n 3
n = 100   5  ns   100 ns 461 ns      10 μs       1ms
n = 10 4 9 ns    10 μs     92 μs   100 ms   17 mn
n = 10 6 13ns 1 ms 13 ms 17 mn 32 a
n = 10 8 21  ns 100 ms 2 s 116 j X
                  
n \ C(n) 2 n n !
n = 10 1  μs 3 ms
n = 20 1  ms 77 a
n = 100 4 * 10 13 a X

  Ces tableaux parlent d'eux mêmes: un algorithme qui résout théoriquement un problème mais qui ne donne jamais la réponse est une curiosité guère utile...

V) Calcul expérimental de la complexité d'un algorithme

1) Pourquoi faire un calcul expérimental de la complexité ?

→  Quand un algorithme est trop complexe pour pouvoir évaluer sa complexité de façon théorique.
→  Pour contrôler un calcul théorique de complexité.

2) Hypothèse et méthode de calcul de la complexité

a) Une hypothèse discutable

  On fait  l'hypothèse (discutable) que si un algorithme a une complexité f ( n ) , alors  le temps T ( n ) d'exécution est à peu près proportionnel à f(n) : T ( n ) k f ( n ) .

  Cette hypothèse est discutable car toutes les opérations élémentaires ne consomment pas le même temps. Une racine carrée, par exemple, est plus longue à calculer qu'une multiplication qui elle même est plus longue qu'une comparaison.

  De plus, n'oublions pas que la complexité est la complexité au pire. Lorsque que le coût de l'algorithme varie beaucoup, pour une taille n fixée des données, de la valeur des données et lorsqu'on fait des tests avec des valeurs “au hasard”, on peut être très loin du pire des cas. Disons dans ce cas qu'en faisant un grand nombre de tests, on pourra avoir une idée de la complexité en moyenne de l'algorithme.

b) Méthode de calcul expérimental de la complexité

  Cette constante k telle que T ( n ) k f ( n ) dépend le la machine qui exécute le programme (fréquence du processeur, qualité de la RAM, autres programmes en cours d'exécution)

  Mais (par exemple) T ( n 10 ) ≈ k f ( n 10 ) , donc T ( n ) T ( n / 10 ) f ( n ) f ( n / 10 ) . En faisant divers essais avec d'assez grandes valeurs de n , on peut assez facilement en déduire, au moins approximativement,  un ordre de grandeur de la complexité f ( n ) .

On peut aussi par exemple évaluer T ( n ) T ( n / 2 ) . L'important est que les résultats trouvés soient significatifs.

3) Ordres de grandeur

a) Pour les algorithmes de complexité raisonnable

  Pour les algorithmes dont la complexité f ( n ) varie de f ( n ) = 1 à f ( n ) = n p , le calcul de R ( n ) = T ( n ) T ( n / 10 ) permet  d'avoir une idée:

n \ f(n) ln(n)         n      n ln(n)     n 2 n 3
n=100        2     10 20      100      1000
n = 10 4 1.33    10     13.3   100   1000
n = 10 6 1.2 10 12 100 1000

  Lorsque les valeurs calculées de R(n) ne sont pas assez caractéristiques,  il faut faire d'autres tests, avec d'autres valeurs de n et/ou de f ( n ) .

b) Autres cas

• Pour les algorithmes exponentiels de complexité f ( n ) = k a n , c'est le calcul de R ( n ) = T ( n + 1 ) T ( n ) (qui est proche de a) qui permet de trancher, avec de PETITES ( n < 30 ) valeurs de n .

••  Pour les algorithmes factoriels de complexité f(n)=k×n ! , c'est le calcul de R ( n ) = T ( n + 1 ) T ( n ) (qui est proche de n+1) qui permet de trancher, avec de PETITES ( n < 15 ) valeurs de n.

4) Calcul du temps d'exécution et estimation la complexité d'une fonction f(n) en Python

  Voilà une fonction complexite(f,n) affichant le temps d'exécution d'une fonction f(n) ainsi que la rapport R ( n ) = T ( n ) T ( n / 10 ) défini plus haut. Il ne reste plus qu'à comparer avec le tableau ci-dessus pour estimer la complexité.

import time                # On importe le module time au début du fichier

def complexite(f, n):
    “““ Durée d'exécution de f(n)
     Rapport de la durée de f(n) / durée de f(n/10)”””
    t1 = time.perf_counter()
    f(n)
    t1 = time.perf_counter() - t1
    t2 = time.perf_counter()
    f(n // 10)
    t2 = time.perf_counter() - t2
    print()
    print(“Fonction f = {0}   n = {1}”.format(f.__name__,n))
    print(“Durée d'exécution de f(n) = {0:.3} s”.format(t1))
    print(“Durée(n)/durée(n/10) = {0:.3}”.format(t1/t2))

VI) Exemples de calculs théoriques de la complexité

1) Le tri par ordre croissant d'une liste de nombres

  Calculer la complexité (nombre de comparaisons et d'affectations) de cet algorithme en fonction de la longueur n de la liste.

def tri(s):
    n = len(s)
    for i in range(n - 1):
        for j in range(i, n):
            if s[i] > s[j]:
                x = s[i]
                s[i] = s[j]
                s[j] = x
    return s

  On a vu au III) qu'il y a au total: n ( n - 1 ) 2 comparaisons et entre 2 et 2 + 3 * n ( n - 1 ) 2 affectations suivant les données.
  Donc le coût C ( n ) au pire est C ( n ) = 2 + 4 * n ( n - 1 ) 2 . Comme O ( 2 + 2 * n ( n - 1 ) ) = O ( n 2 ) , la complexité est en n 2 et est quadratique.

2) Le test de primalité

  Calculer la complexité (nombre de divisions, on néglige les tests) de cet algorithme en fonction de l'entier n.

from math import *
def test_premier(n):
    for d in range(2, floor(sqrt(n) + 1):
        if n % d == 0:
            return False
    return True

  Notons C ( n ) le nombre de divisions. Pour un entier n pair,   C ( n ) = 1 , pour un entier multiple de 3 non pair, C ( n ) = 2 , ..., pour un entier n premier, C ( n ) = [ n ] - 1 .
  Le pire des cas ( n est premier)  est alors C ( n ) = [ n ] - 1 = O ( n ) , la complexité est en n .

Remarque: le calcul théorique de la complexité en moyenne est difficile pour cet algorithme.

3) Algorithme d'Euclide

  Nous allons calculer la complexité (nombre de divisions, on néglige les affectations) de cette fonction pgcd(a,b), et prouver que cette complexité est en O(ln(b)).
  Le coût C(a, b) est ici le nombre d'exécutions de l'itération while.

def pgcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a     

a) Prouver que si a = b q + r est la divison euclidienne de a par b avec a b 1 , alors r < a 2 .

Conseil: distinguer les cas a 2 b et a < 2 b .

Remarque : Dans tous les cas, au cours du déroulement de l'algorithme d'Euclide, r < a 2 , sauf peut être au départ si a < b (dans ce cas r = a ), mais alors a et b sont échangés à la première itération.

b)  Prouver que n N , b n + 1 < b n - 1 2 .

c) En déduire que pour n N , b 2 n < b 0 2 n , où b 0 = b est la valeur de départ.

d) En déduire que n [ ln ( b ) ln ( 2 ) ] b 2 n = 0 .  

e) En déduire que C ( a , b ) 2 [ ln ( b ) ln ( 2 ) ] .

f) Montrer que  si a < b alors   C ( a , b ) 2 [ ln ( b ) ln ( 2 ) ] + 1 .

g) En déduire que la complexité de l'algorithme d'Euclide est en O ( ln ( min ( a , b ) ) ) donc en O ( ln ( b ) ) . L'algorithme d'Euclide est un excellent algorithme.

© 2014 - Eric Obermeyer      Powered by