Boucles imbriquées et complexité quadratique

Résumé en cinq points

1Compter les tours de boucles imbriquées

1.1Boucle intérieure de longueur fixe

Pour un tableau de mesures à $n$ lignes et $m$ colonnes parcouru case par case, le coût est proportionnel au nombre de cases.

1.2Boucle intérieure dépendant de l'indice extérieur

C'est le cas des algorithmes qui considèrent chaque paire d'éléments une seule fois.

for i in range(n):
    for j in range(i + 1, n):
        ...

1.3Boucles cachées

Une seule ligne peut contenir un parcours. Le test x in liste, la copie d'une liste, la concaténation, l'extraction d'une tranche t[a:b] coûtent un temps proportionnel à la longueur concernée.

2Recherche d'un facteur dans un texte

2.1Énoncé

2.2Algorithme naïf

On teste chaque position de départ $i$ possible, de $0$ à $n - p$. Pour chacune, on compare les caractères un à un tant qu'ils coïncident.

def contient(t, m):
    # Renvoie True si m est un facteur de t.
    n, p = len(t), len(m)
    i = 0
    while i <= n - p:
        k = 0
        while k < p and t[i + k] == m[k]:
            k = k + 1
        if k == p:
            return True
        i = i + 1
    return False

Justifications :

• La dernière position testée est $n - p$, car à partir de $i = n - p + 1$ il reste moins de $p$ caractères. Si le motif est plus long que le texte, la boucle extérieure ne s'exécute pas et la fonction renvoie False.
• Dans la condition du while intérieur, k < p est évalué en premier. Quand k vaut $p$, le caractère paresseux de and évite l'accès hors limites m[p].
• En sortie du while intérieur, k == p signifie que les $p$ caractères ont coïncidé.
• Terminaison : la quantité $n - p - i$ décroît d'une unité à chaque tour de la boucle extérieure, et $p - k$ décroît à chaque tour de la boucle intérieure. Ce sont des variants.

2.3Coût dans le cas le pire

Chaque position demande au plus $p$ comparaisons, il y a $n - p + 1$ positions, d'où au plus $(n-p+1)\,p$ comparaisons.

Le coût dépend de deux tailles :

• pour un motif court de longueur fixée, il est linéaire en $n$ ;
• pour un motif de longueur proportionnelle à $n$, par exemple $p = n/2$, il vaut environ $n^2/4$, quadratique.

Des algorithmes plus rapides existent, mais ils ne relèvent pas de ce thème.

3Les deux valeurs les plus proches

3.1Énoncé et contexte

On dispose d'une liste de $n$ valeurs, par exemple les longueurs d'onde, en nanomètres, des raies d'émission d'un mélange de gaz. On veut l'écart minimal entre deux raies distinctes, pour savoir si un spectromètre de résolution donnée pourra toutes les séparer.

3.2Algorithme

def ecart_minimal(lam):
    # lam : liste d'au moins deux flottants.
    n = len(lam)
    assert n >= 2
    d_min = None
    for i in range(n - 1):
        for j in range(i + 1, n):
            d = lam[i] - lam[j]
            if d < 0:
                d = -d
            if d_min == None or d < d_min:
                d_min = d
    return d_min

• On ne considère que les paires $i < j$, car l'écart est symétrique et qu'une case comparée à elle-même donnerait un écart nul, sans intérêt.
• La valeur None sert de marqueur « aucun écart encore calculé ».
• Le test d_min == None est évalué d'abord, et grâce au caractère paresseux de or, la comparaison d < d_min n'est jamais faite avec None.
• On aurait pu aussi initialiser d_min avec l'écart entre les deux premières valeurs.

3.3Faire mieux en triant

Dans une liste triée, deux valeurs les plus proches sont forcément voisines. Après un tri, il suffit donc de comparer lam[k] et lam[k + 1] pour chaque $k$, en un seul parcours. Avec un tri de coût $n \log n$, vu au second semestre, le coût total devient de l'ordre de $n \log n$.

4Tri à bulles

4.1Principe

On veut ranger par ordre croissant une liste, par exemple des valeurs de $\mathrm{p}K_a$ pour ordonner des acides du plus fort au plus faible. Le tri à bulles compare les voisins deux à deux de gauche à droite, et les échange s'ils sont mal ordonnés.

• À la fin d'un passage, la plus grande valeur de la zone parcourue se retrouve à la dernière place.
• On recommence sur la zone restante, raccourcie d'une case.
• On peut s'arrêter dès qu'un passage ne fait aucun échange.

def tri_bulles(t):
    # t : liste de nombres, triée en place.
    fin = len(t) - 1
    echange = True
    while echange and fin > 0:
        echange = False
        for j in range(fin):
            if t[j] > t[j + 1]:
                t[j], t[j + 1] = t[j + 1], t[j]
                echange = True
        fin = fin - 1

La liste passée en argument est modifiée par la fonction, qui ne renvoie rien. C'est possible parce qu'une liste est mutable : la fonction et l'appelant désignent la même liste. Pour conserver la liste d'origine, on trie une copie : u = t.copy(), ou u = list(t), ou u = t[:].

4.2Correction

La boucle s'arrête dans deux cas :

• fin vaut 0 : toutes les cases sauf la première sont en place, donc la liste est triée ;
• un passage n'a fait aucun échange : sans échange, $t[j] \leqslant t[j+1]$ pour tout $j < \text{fin}$, donc la zone est triée et, avec l'invariant, toute la liste l'est.

==La terminaison est assurée par le variant fin, entier qui décroît d'une unité à chaque passage.==

4.3Coût

Pour une liste déjà triée, un seul passage de $n - 1$ comparaisons suffit. Mais le programme s'intéresse au cas le pire, qui reste quadratique.

4.4Propriétés

• Le tri à bulles trie en place, sans liste auxiliaire.
• Il est stable : deux valeurs égales ne sont jamais échangées, la comparaison étant stricte. Cette stabilité compte quand on trie des enregistrements, par exemple des couples (espèce, $\mathrm{p}K_a$), selon un seul champ.
• Il est comparatif : il ne fait que comparer des éléments deux à deux.

5Complexité quadratique

5.1Définition

5.2Lecture physique

L'idée rejoint celle des ordres de grandeur en physique. Un coût quadratique signifie que le temps de calcul est multiplié par 4 quand la taille double, par 100 quand elle est multipliée par 10.

Python exécute de l'ordre de quelques dizaines de millions d'opérations simples par seconde. Un algorithme quadratique traite quelques milliers de mesures presque instantanément, mais un enregistrement d'un million d'échantillons, courant pour une acquisition à haute fréquence, demanderait de l'ordre de $10^{12}$ opérations, soit plusieurs heures.

5.3Pièges

6Valider la correction d'un algorithme

6.1Tests

Un test compare la sortie d'une fonction à un résultat connu. Un jeu de tests pertinent couvre les cas généraux et les cas limites :

• pour contient : motif en tête, en fin, au milieu, absent, plus long que le texte, égal au texte, vide ;
• pour ecart_minimal : deux valeurs seulement, valeurs égales, valeurs négatives ;
• pour le tri : liste vide, à un élément, déjà triée, triée à l'envers, avec des doublons.

On peut compléter par des tests aléatoires, en comparant le résultat de sa fonction à celui d'une fonction de référence, par exemple sorted pour un tri, sur des listes tirées au hasard avec le module random.

6.2Assertions

L'instruction assert condition arrête le programme avec une erreur si la condition est fausse. On s'en sert pour les préconditions, assert n >= 2, et pour écrire les tests sous une forme compacte, assert contient("ACGAATTCG", "GAATTC"). L'annexe prévoit assert sans message.

6.3Invariants et variants

Ces notions seront formalisées au second semestre. Dès ce chapitre, on les énonce en une phrase pour chaque algorithme.

Méthodes

Ce qu'il faut savoir refaire en khôlle

1. Écrire la recherche naïve d'un motif dans une séquence, en justifiant les bornes et l'ordre des conditions.
2. Donner le coût de cette recherche dans le pire des cas, avec un exemple d'entrée qui l'atteint, et discuter selon la longueur du motif.
3. Écrire le calcul de l'écart minimal entre deux valeurs d'une liste, et montrer qu'il fait $n(n-1)/2$ comparaisons.
4. Expliquer pourquoi un tri préalable permet un algorithme plus rapide pour ce problème.
5. Écrire le tri à bulles avec arrêt anticipé, énoncer ses invariants, et donner son coût dans le pire et dans le meilleur cas.
6. Expliquer ce que signifient tri en place et tri stable, et vérifier ces propriétés pour le tri à bulles.
7. Définir la complexité quadratique et proposer une vérification expérimentale par mesure de durées.
8. Proposer un jeu de tests et des assertions pour une fonction donnée.

Les résultats à connaître

Dans ce chapitre, les « résultats » sont des dénombrements de tours, des preuves de correction et des coûts dans le pire cas.

• Deux boucles imbriquées de n et m tours exécutent le corps n × m fois : exigible.
• La double boucle sur les paires i < j fait n(n − 1)/2 tours, celle sur i ≤ j en fait n(n + 1)/2 : exigible avec démonstration.
• 1 + 2 + … + k = k(k + 1)/2 : exigible, démontré en mathématiques.
• Deux boucles successives de n tours ont un coût linéaire : exigible.
• Une boucle intérieure dont le nombre de tours est borné par une constante ne change pas l'ordre de grandeur : exigible.
• La recherche naïve d'un facteur est correcte et fait au plus (n − p + 1)p comparaisons. Cette borne est atteinte : exigible avec justification.
• L'écart minimal par examen des paires demande exactement n(n − 1)/2 comparaisons : exigible.
• Dans une liste triée, deux valeurs les plus proches sont voisines : exigible avec démonstration.
• Le tri à bulles avec arrêt anticipé est correct et termine, par invariant et variant : exigible avec justification.
• Le tri à bulles fait n(n − 1)/2 comparaisons dans le pire cas, atteint pour une liste strictement décroissante. Il en fait n − 1 pour une liste déjà triée : exigible.
• Le tri à bulles à comparaison stricte est en place et stable : exigible.
• Le nombre d'échanges du tri à bulles est égal au nombre d'inversions de la liste : classique, non exigible en tant que tel, à savoir redémontrer.
• Un coût quadratique est multiplié par environ 4 quand n double : exigible.
• Hors programme signalé : les algorithmes rapides de recherche de motif (Knuth-Morris-Pratt, Boyer-Moore) et l'étude du coût en moyenne. La méthode sort, la fonction sorted et le module time ne s'utilisent qu'avec leur documentation.

Clés de démonstration

Compter les paires. Pour i fixé, la boucle for j in range(i + 1, n) fait n − 1 − i tours. On somme de i = 0 à n − 1 et l'on reconnaît 0 + 1 + … + (n − 1). L'astuce est le dénombrement : chaque tour correspond à une paire {i, j} et à une seule, et il y a n(n − 1)/2 paires.

Recherche de facteur. On écrit un invariant par boucle. Boucle intérieure : les k premiers caractères de m coïncident avec t[i], …, t[i + k − 1]. Boucle extérieure : m n'apparaît à aucune position strictement inférieure à i. En sortie de la boucle intérieure, soit k = p et m est trouvé en i, soit un caractère diffère et l'invariant extérieur reste vrai pour i + 1. L'astuce est de nommer séparément ce que prouve chaque boucle.

Voisins dans une liste triée. Soit u triée et i < j. L'écart u[j] − u[i] est la somme télescopique des écarts u[k + 1] − u[k] pour k allant de i à j − 1. Tous ces termes sont positifs, donc u[j] − u[i] est supérieur ou égal à u[i + 1] − u[i]. L'astuce est le télescopage : le minimum sur toutes les paires est atteint sur une paire de voisins.

Passage du tri à bulles. On montre par récurrence sur j qu'avant la comparaison d'indice j, t[j] est le maximum de t[0], …, t[j]. Si t[j] > t[j + 1], l'échange amène ce maximum en j + 1. Sinon, t[j + 1] est déjà le plus grand. L'astuce est de suivre la plus grande valeur rencontrée, qui avance comme une bulle.

Pire cas du tri à bulles. Sur une liste strictement décroissante, le premier passage décale toutes les valeurs d'une case vers la gauche et place le maximum à la fin. La zone restante est donc encore strictement décroissante. Par récurrence, chaque passage fait un échange tant que la zone a deux cases. On compte alors n − 1 passages et (n − 1) + … + 1 comparaisons. L'astuce est de montrer que la forme de l'entrée se conserve d'un passage au suivant.

Terminaison. Chaque boucle while se justifie par un entier positif qui décroît strictement : n − p − i pour la recherche, p − k pour la boucle intérieure, fin pour les bulles. L'astuce est d'écrire ce variant en une phrase, même quand il paraît évident.

Exemples et contre-exemples à connaître

1. La liste [5, 1, 4]. Si l'on compare seulement les voisins, on obtient 3, alors que 5 et 4 sont à distance 1. L'argument des voisins exige une liste triée.
2. Le texte « AAAA…A » et le motif « AA…AC ». Chaque position échoue à la dernière comparaison. C'est l'entrée qui réalise le pire cas de la recherche naïve.
3. Le motif vide. La fonction contient de la fiche renvoie True, même pour un texte vide. C'est la convention usuelle, mais il faut la signaler.
4. Le motif « AA » dans « AAAA ». Il a trois occurrences, car elles se chevauchent. Un compteur qui avance de p cases après un succès n'en trouve que deux.
5. Une liste strictement décroissante. Elle réalise le pire cas du tri à bulles, avec n(n − 1)/2 comparaisons et autant d'échanges.
6. Le tri à bulles écrit avec >=. Il trie encore et il termine grâce au variant fin. Mais il échange les valeurs égales, donc il perd la stabilité. Sur une liste constante, il fait tous les passages au lieu d'un seul.
7. for i in range(n): if t[i] in t[i + 1:]. On ne voit qu'une boucle, mais la tranche et le test in en cachent une seconde. Le coût est quadratique.
8. Un seul passage de bulles. Il trie [2, 1] et [1, 3, 2], mais il transforme [3, 2, 1] en [2, 1, 3]. Deux tests réussis ne prouvent rien.
9. Le test de symétrie d'une matrice n × n. Il demande n(n − 1)/2 comparaisons : c'est quadratique en n, mais linéaire en n², le nombre de cases. Le mot « quadratique » n'a de sens qu'une fois la taille précisée.

Techniques du chapitre

Technique 1, le tableau des tours. Mini-exercice : combien de fois s'exécute le corps de for i in range(n): for j in range(i): ... ? Pour i = 0, 1, …, n − 1, la boucle intérieure fait i tours. Le total vaut 0 + 1 + … + (n − 1) = n(n − 1)/2.

Technique 2, réutiliser le tour précédent. Mini-exercice : calculer les sommes cumulées c[k] = t[0] + … + t[k]. Refaire chaque somme par une boucle intérieure coûte de l'ordre de n²/2. Avec c[k] = c[k − 1] + t[k], chaque terme coûte une addition, et le total est linéaire.

Technique 3, sortir des deux boucles par return. Mini-exercice : renvoyer le premier couple (i, j), avec i < j, de mesures égales. On écrit la double boucle dans une fonction et l'on renvoie (i, j) dès que t[i] == t[j]. Le return interrompt les deux boucles d'un coup, sans variable drapeau.

Technique 4, fabriquer l'entrée du pire cas. Mini-exercice : quel est le pire cas d'une recherche de doublon par double boucle ? La sortie anticipée n'a lieu que si deux valeurs sont égales. Le pire cas est donc une liste sans doublon, qui impose les n(n − 1)/2 comparaisons.

Technique 5, trier puis ne regarder que les voisins. Mini-exercice : tester l'absence de doublon dans une liste triée u. Deux valeurs égales y sont forcément voisines. Un parcours de k = 0 à n − 2 qui compare u[k] et u[k + 1] suffit. Son coût est linéaire.

Technique 6, tracer un passage à la main. Mini-exercice : premier passage du tri à bulles sur [4, 1, 3, 2]. On échange 4 et 1, puis 4 et 3, puis 4 et 2. On obtient [1, 3, 2, 4] : le maximum est en place, le reste n'est pas encore trié.

Technique 7, lire un rapport de durées. Mini-exercice : un programme quadratique met 2 s pour n = 10 000. Combien pour n = 30 000 ? La taille est multipliée par 3, donc la durée par 9, soit environ 18 s.

Exercices classiques corrigés

Choisis ton niveau. Difficulté indicative ; les exercices qui se suivent restent dans l'ordre.

c = 0
for i in range(n):
    for j in range(i, n):
        for k in range(3):
            c = c + 1

def occurrences_motif(t, m):
    n, p = len(t), len(m)
    c = 0
    for i in range(n - p + 1):
        k = 0
        while k < p and t[i + k] == m[k]:
            k = k + 1
        if k == p:
            c = c + 1
    return c

def premiere_position(t, m):
    n, p = len(t), len(m)
    for i in range(n - p + 1):
        k = 0
        while k < p and (m[k] == "?" or t[i + k] == m[k]):
            k = k + 1
        if k == p:
            return i
    return -1

def tous_distincts(t):
    n = len(t)
    for i in range(n):
        for j in range(i + 1, n):
            if t[i] == t[j]:
                return False
    return True

def tri_selection(t):
    n = len(t)
    for i in range(n - 1):
        k = i
        for j in range(i + 1, n):
            if t[j] < t[k]:
                k = j
        t[i], t[k] = t[k], t[i]

def est_symetrique(M):
    n = len(M)
    for i in range(n):
        for j in range(i + 1, n):
            if M[i][j] != M[j][i]:
                return False
    return True

def inversions(t):
    c = 0
    n = len(t)
    for i in range(n):
        for j in range(i + 1, n):
            if t[i] > t[j]:
                c = c + 1
    return c

def somme_max(t):
    meilleur = t[0]
    for i in range(len(t)):
        s = 0
        for j in range(i, len(t)):
            s = s + t[j]
            if s > meilleur:
                meilleur = s
    return meilleur

Erreurs fréquentes