CHAPITRE 6 : LIRE LA COMPLEXITÉ DANS UN CODE

Vous savez compter, vous savez simplifier, vous connaissez les familles. Il reste à acquérir le réflexe : regarder un code et annoncer sa complexité sans crayon.

Deux règles, et c'est tout

Règle d'addition. Deux blocs qui se suivent : on garde le plus coûteux.

trier(tab)              # O(n log n)
for x in tab:           # O(n)
    print(x)
# total : O(n log n) : le tri écrase le parcours

Règle de multiplication. Un bloc à l'intérieur d'une boucle : on multiplie.

for i in range(n):          # n fois
    dichotomie(tab, i)      # O(log n) chacune
# total : O(n log n)

Reconnaître les boucles

Le nombre de tours ne se lit pas toujours sur la première ligne. Trois schémas à connaître.

# incrément de 1 : n tours        -> O(n)
i = 0
while i < n:
    i += 1

# incrément de 100 : n/100 tours  -> O(n), car 1/100 est une constante
i = 0
while i < n:
    i += 100

# multiplication par 2 : log₂ n tours -> O(log n)
i = 1
while i < n:
    i *= 2

La question à se poser : la variable de boucle s'ajoute-t-elle ou se multiplie-t-elle ? Ajouter donne du linéaire, multiplier donne du logarithmique.

Les boucles imbriquées dépendantes

Quand la boucle intérieure dépend de l'extérieure, il faut sommer.

for i in range(n):
    for j in range(i):     # i tours, pas n
        ...

Total : 0 + 1 + 2 + … + (n−1) = n(n−1)/2, soit O(n²). La moitié du travail de la version carrée, mais la même famille.

Voici un cas plus retors, qu'on croit souvent quadratique :

i = 1
while i < n:
    for j in range(n):     # n tours
        ...
    i *= 2                 # log n tours de la boucle externe

La boucle externe multiplie : log n tours. L'interne en fait n. Total : O(n log n).

Le piège des bibliothèques

Un appel de fonction ne coûte pas une opération : il coûte ce que la fonction fait. Voici le tableau qui sauve le plus de programmes.

uniques = []
for x in donnees:            # n tours
    if x not in uniques:     # O(n) a chaque tour !
        uniques.append(x)

vus = set()
uniques = []
for x in donnees:
    if x not in vus:         # O(1)
        vus.add(x)
        uniques.append(x)

La concaténation de chaînes

Même histoire, autre déguisement.

# O(n²) : chaque + recopie toute la chaîne construite jusque-là
texte = ""
for mot in mots:
    texte += mot + " "

# O(n) : on accumule, on assemble une seule fois
texte = " ".join(mots)

En Python, les chaînes sont immuables : texte += mot ne modifie pas texte, il en fabrique une copie neuve. Au tour numéro k, cette copie fait k caractères. Total : 1 + 2 + … + n, encore notre somme en n²/2.

Les fonctions qu'on écrit soi-même

Pour analyser une fonction qui en appelle d'autres, on remplace chaque appel par sa complexité, puis on applique les deux règles.

def analyser(donnees):          # n éléments
    propres = nettoyer(donnees)     # O(n)
    propres.sort()                  # O(n log n)
    doublons = compter_doublons(propres)  # O(n), liste triée
    return resumer(doublons)        # O(1)

Addition de quatre blocs : O(n) + O(n log n) + O(n) + O(1). On garde le plus gros : O(n log n).

La marche à suivre

1. Qu'est-ce que n ? Le nombre d'éléments ? La longueur d'une chaîne ? La valeur d'un entier ? Toute analyse commence là.
2. Repérer les boucles, et pour chacune compter les tours.
3. Vérifier chaque appel : un in, un + sur des chaînes, un insert(0, …) cachent des parcours.
4. Multiplier l'imbriqué, garder le maximum de ce qui se suit.

vus = set(b)      # O(n), une fois
c = 0
for x in a:       # n tours
    if x in vus:  # O(1) maintenant
        c += 1

# total : O(n)