CHAPITRE 2 : COMPTER LES PAS, PAS LES SECONDES

Puisque les secondes mentent, comptons les pas. Reste à savoir ce qu'est un pas, et comment les additionner.

Ce qui vaut un pas

On appelle opération élémentaire une action dont le coût ne dépend pas de la taille des données. Peu importe qu'elle prenne 2 ou 7 nanosecondes : ce qui compte, c'est que ce soit toujours la même chose.

En valent une, à peu de chose près :

• une affectation : x = 5 ;
• une opération arithmétique : a + b, n % 2 ;
• une comparaison : i < n ;
• l'accès à une case de tableau : tab[i] ;
• un return.

N'en valent pas une, et c'est le piège le plus courant :

• copier un tableau : le coût suit sa taille ;
• concaténer deux chaînes : idem ;
• appeler une fonction : il faut compter ce qu'elle fait à l'intérieur ;
• un in sur une liste en Python, c'est un parcours déguisé.

Des instructions qui se suivent

Quand des instructions s'enchaînent, leurs coûts s'additionnent.

def ecart(a, b):
    grand = a          # 1
    petit = b          # 1
    if b > a:          # 1
        grand = b      # 1
        petit = a      # 1
    return grand - petit   # 2 (soustraction + retour)

Au total : sept opérations au plus, quelles que soient les valeurs de a et b. Donnez-lui deux nombres à trois chiffres ou à trente chiffres, c'est pareil.

On écrit T(n) = 7, et comme 7 ne dépend pas de n, on dira que ce code a un coût constant.

Une boucle

Une boucle multiplie le coût de son corps par le nombre de tours.

def somme(tab, n):
    total = 0              # 1 opération
    for i in range(n):     # n tours
        total += tab[i]    # 3 opérations par tour
    return total           # 1 opération

Détaillons. Avant la boucle : 1. Dans la boucle : un accès au tableau, une addition, une affectation, soit 3, et cela n fois. Après : 1.

T(n) = 1 + 3n + 1 = 3n + 2

Le compte dépend maintenant de n. Doublez n, le compte double (à deux unités près). Voilà un algorithme dont le travail suit la taille des données.

Deux boucles imbriquées

def paires_nulles(tab, n):
    compte = 0                       # 1
    for i in range(n):               # n tours
        for j in range(n):           #   n tours chacun
            if tab[i] + tab[j] == 0: #   3 opérations
                compte += 1          #   2, parfois
    return compte                    # 1

La boucle intérieure tourne n fois. La boucle extérieure la relance n fois. Le corps s'exécute donc n × n fois.

T(n) ≈ 1 + n × n × 4 + 1 = 4n² + 2

Ici, doubler n ne double pas le travail : il le quadruple. Pour n = 1 000, on est déjà à quatre millions d'opérations.

Une boucle qui ne va pas jusqu'au bout

Attention aux bornes. Les deux codes suivants n'ont pas le même compte.

# version A : toutes les paires, deux fois chacune
for i in range(n):
    for j in range(n):
        ...                 # n² tours

# version B : chaque paire une seule fois
for i in range(n):
    for j in range(i + 1, n):
        ...                 # n(n-1)/2 tours

La version B fait à peu près deux fois moins de tours. C'est un vrai gain, qu'on sent à l'exécution. Mais dans les deux cas, doubler n quadruple le travail : les deux appartiennent à la même famille. Nous verrons au chapitre 3 pourquoi ce facteur deux finit par ne plus compter.

La méthode, en trois gestes

1. Repérer ce qui dépend de n et ce qui n'en dépend pas.
2. Compter les tours de chaque boucle, en partant de la plus intérieure.
3. Multiplier les boucles imbriquées, additionner les blocs qui se suivent.

avant la 1re boucle : 1
1re boucle : n tours x 2 operations = 2n
2e boucle  : n tours x 3 operations = 3n

T(n) = 1 + 2n + 3n = 5n + 1