Coût d'un algorithme : compter les opérations

Le coût d'un algorithme mesure comment son nombre d'opérations varie avec la taille n des données. On ne cherche pas un nombre exact, mais un ordre de grandeur quand n devient grand. Pour l'estimer, on compte les tours de boucle en fonction de n.

Les quatre fonctions ci-dessous comptent leurs propres tours, pour n = 64, 128, 256 et 512 :

def tours_log(n):
    c = 0
    while n > 1:
        n = n // 2
        c = c + 1
    return c

def tours_lineaire(n):
    c = 0
    for i in range(n):
        c = c + 1
    return c

def tours_quadratique(n):
    c = 0
    for i in range(n):
        for j in range(n):
            c = c + 1
    return c

for n in [64, 128, 256, 512]:
    print(n, tours_log(n), tours_lineaire(n), tours_quadratique(n))

64 6 64 4096
128 7 128 16384
256 8 256 65536
512 9 512 262144

Quand n double : le coût logarithmique augmente d'une étape, le coût linéaire double, le coût quadratique est multiplié par quatre.

Deux boucles qui se suivent s'additionnent. Ci-dessous, n tours puis 3n tours : 4n en tout, ce qui reste linéaire. Ce sont des boucles imbriquées qui se multiplient.

Une boucle dont le nombre de tours est fixé ne dépend pas de n : range(10) fait toujours 10 tours, le coût est constant.

def deux_boucles(n):
    c = 0
    for i in range(n):
        c = c + 1
    for j in range(3 * n):
        c = c + 1
    return c

def boucle_fixe(n):
    c = 0
    for i in range(10):
        c = c + 1
    return c

for n in [100, 200, 400]:
    print(n, deux_boucles(n), boucle_fixe(n))

100 400 10
200 800 10
400 1600 10

Pourquoi c'est important. Pour un million de données, un tri en n² ferait de l'ordre de 10¹² opérations, un tri en n log₂ n environ 2 × 10⁷ ; une recherche en log₂ n une vingtaine d'étapes au lieu d'un million :

from math import log2
n = 10 ** 6
print(round(n * log2(n)))
print(n * n)
print(round(log2(n)))

19931569
1000000000000
20

Énoncé. Quand n devient grand, comment varie le nombre d'opérations de cette fonction ?

def f(n):
    c = 0
    for i in range(n):
        for j in range(i):
            c = c + 1
    return c

print(f(100), f(200), f(400))

Résolution.

1. Deux boucles imbriquées : la boucle intérieure fait i tours, pour i allant de 0 à n − 1.
2. Au total : 0 + 1 + … + (n − 1) = n(n − 1)/2 passages, de l'ordre de n².
3. Contrôle par l'exécution : quand n double, le nombre de passages est presque multiplié par quatre.

4950 19900 79800

Le coût est quadratique : de l'ordre de n², même si la boucle intérieure ne fait pas toujours n tours.

Les valeurs sont celles comptées par les programmes de la leçon.