Boucles imbriquées et complexité quadratique

Résumé en cinq points

1Boucles imbriquées et comptage des tours

1.1Deux formes à distinguer

for i in range(n):
    for j in range(n):
        ...  # corps exécuté n × n fois

Le corps est exécuté $n^2$ fois.

for i in range(n):
    for j in range(i + 1, n):
        ...  # corps exécuté (n-1) + ... + 0 fois

Le nombre total de tours vaut la somme des $n - 1 - i$ pour $i$ allant de $0$ à $n - 1$ : $$\sum_{i=0}^{n-1} (n-1-i) = \frac{n(n-1)}{2}.$$ C'est exactement le nombre de paires d'éléments distincts d'un ensemble à $n$ éléments.

1.2Formules à connaître

2Recherche d'un facteur dans un texte

2.1Le problème

2.2Algorithme naïf

On essaie toutes les positions de départ possibles, de $0$ à $n - p$ inclus. Pour chacune, on compare le mot au texte caractère par caractère, et on s'arrête à la première différence.

def position_facteur(m, t):
    # Renvoie le plus petit i tel que m apparaît dans t
    # à partir de l'indice i, ou -1 sinon.
    n, p = len(t), len(m)
    for i in range(n - p + 1):
        k = 0
        while k < p and t[i + k] == m[k]:
            k = k + 1
        if k == p:
            return i
    return -1

Trois points de vigilance :

• la borne $n - p + 1$ du range : avec range(n), l'expression t[i + k] sortirait du texte. Si $p > n$, range(n - p + 1) est vide et la fonction renvoie $-1$, ce qui est correct ;
• l'ordre des conditions du while : le test k < p est placé avant t[i + k] == m[k], et le caractère paresseux de and évite de lire m[p] ;
• le test k == p après le while distingue les deux sorties possibles de la boucle : le mot entièrement reconnu, ou une différence trouvée.

2.3Coût

Pour chaque position $i$, la boucle intérieure fait au plus $p$ comparaisons. Il y a $n - p + 1$ positions. Dans le cas le pire, le coût est de l'ordre de $(n-p+1)\,p$ comparaisons.

Il existe des algorithmes plus efficaces, mais ils sont hors du programme de ce thème. L'intérêt ici est de reconnaître la structure « position de départ, puis lecture à partir de cette position ».

3Recherche des deux valeurs les plus proches dans un tableau

3.1Le problème

Étant donné une liste t d'au moins deux nombres, on cherche deux éléments d'indices distincts dont l'écart, en valeur absolue, est minimal. On renvoie par exemple le couple d'indices.

3.2Algorithme par examen de toutes les paires

def plus_proches(t):
    # t : liste d'au moins deux nombres.
    # Renvoie (i, j), i < j, d'écart minimal.
    n = len(t)
    assert n >= 2
    meilleur = (0, 1)
    d_min = t[1] - t[0]
    if d_min < 0:
        d_min = -d_min
    for i in range(n):
        for j in range(i + 1, n):
            d = t[j] - t[i]
            if d < 0:
                d = -d
            if d < d_min:
                d_min = d
                meilleur = (i, j)
    return meilleur

On calcule la valeur absolue à la main pour rester dans le noyau de l'annexe. La fonction abs de Python n'est pas listée dans l'annexe et devrait donc être accompagnée de sa documentation dans un sujet.

À la fin, toutes les paires ont été examinées, donc le résultat est correct.

La boucle intérieure est exécutée $\frac{n(n-1)}{2}$ fois en tout, chaque tour faisant un nombre constant d'opérations. Le coût est quadratique dans tous les cas, pas seulement le pire, puisqu'il n'y a aucune sortie anticipée.

3.3Remarque sur une meilleure méthode

Si le tableau est trié, les deux valeurs les plus proches sont forcément voisines, et un seul parcours suffit. Le coût total devient celui du tri suivi d'un parcours linéaire. Avec un tri efficace, vu plus tard dans l'année, on passe d'un coût quadratique à un coût de l'ordre de $n \log n$.

4Tri à bulles

4.1Principe

Trier une liste, c'est la réorganiser par ordre croissant. Le tri à bulles parcourt la liste de gauche à droite en comparant chaque élément à son voisin de droite, et les échange s'ils sont dans le mauvais ordre. Au cours d'un parcours, le plus grand élément non encore placé est poussé jusqu'au bout de la zone non triée, comme une bulle qui remonte. On recommence sur une zone raccourcie d'une case.

def tri_bulles(t):
    # Trie t en place par ordre croissant.
    n = len(t)
    for k in range(n - 1):
        for j in range(n - 1 - k):
            if t[j] > t[j + 1]:
                t[j], t[j + 1] = t[j + 1], t[j]

L'échange utilise le dépaquetage de tuples, qui fait partie de l'annexe. La fonction ne renvoie rien. Elle modifie la liste reçue, ce qui est possible parce qu'une liste est mutable et que la fonction reçoit une référence vers la même liste. L'appelant constate donc la modification.

4.2Correction

En fin de boucle intérieure, la dernière case de la zone parcourue contient le maximum de cette zone.

Après $n - 1$ parcours, les $n - 1$ dernières cases sont en place, donc la première aussi, et la liste est triée.

Terminaison : les deux boucles sont des boucles for sur des range finis. Elles terminent toujours.

4.3Coût

Le nombre de comparaisons vaut $$(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2},$$ quelle que soit la liste. Le nombre d'échanges est au plus égal à ce nombre, atteint pour une liste triée dans l'ordre décroissant. Le coût est quadratique.

Amélioration classique : si un parcours complet ne fait aucun échange, la liste est déjà triée et on peut s'arrêter. On ajoute un booléen mis à False au début de chaque parcours et à True à chaque échange, et l'on remplace la boucle extérieure par un while. Sur une liste déjà triée, le coût devient linéaire. Le coût dans le cas le pire reste quadratique.

4.4Caractéristiques

Le tri à bulles a trois caractéristiques, reprises au chapitre sur les tris :

• il est en place : il n'utilise pas d'autre tableau que la liste elle-même ;
• il est stable : deux éléments égaux ne sont jamais échangés grâce à la comparaison stricte, donc leur ordre relatif est conservé ;
• il est comparatif : il n'utilise que des comparaisons entre éléments.

5Complexité quadratique

5.1Définition

On ne cherche pas le nombre exact d'opérations. Les constantes dépendent de la machine et de la façon de compter. Seule la forme de la croissance compte.

5.2Conséquences pratiques

Un coût quadratique signifie que doubler la taille de l'entrée multiplie le temps d'exécution par quatre environ, et que multiplier la taille par dix le multiplie par cent.

Un interpréteur Python exécute de l'ordre de quelques dizaines de millions d'opérations simples par seconde. Un algorithme quadratique traite donc confortablement quelques milliers d'éléments, mais un million d'éléments demanderait de l'ordre de $10^{12}$ opérations, soit des heures. Un algorithme linéaire traite le même million en une fraction de seconde.

Ce raisonnement permet de vérifier expérimentalement une complexité. On mesure les temps d'exécution pour $n$, $2n$, $4n$, et l'on regarde s'ils sont multipliés par 2 ou par 4 d'une mesure à la suivante. La mesure du temps demande un module, time par exemple, dont la connaissance n'est pas exigible.

5.3Erreurs fréquentes

6Outils pour valider la correction

Le programme demande de proposer des outils pour valider la correction des algorithmes. Trois outils complémentaires sont utilisés dès le premier semestre.

6.1Jeux de tests

Un jeu de tests est une liste d'entrées dont on connaît la sortie attendue. Un bon jeu couvre les cas généraux et les cas limites.

• Recherche de facteur : un mot au début, au milieu, à la fin du texte, un mot absent, un mot plus long que le texte, le mot vide, un mot égal au texte.
• Tri : une liste vide, une liste à un élément, une liste déjà triée, une liste triée à l'envers, une liste avec des doublons.

On peut aussi comparer le résultat d'une fonction à celui d'une fonction de référence sur de nombreuses entrées tirées au hasard, par exemple comparer tri_bulles à la fonction sorted de Python. Le module random et la fonction sorted ne sont pas exigibles, mais leur usage documenté est naturel en travaux pratiques.

6.2Assertions

L'instruction assert condition interrompt l'exécution avec une erreur si la condition est fausse. On l'utilise pour vérifier une précondition à l'entrée d'une fonction, par exemple assert len(t) >= 2 dans plus_proches, ou pour vérifier le résultat d'un test, par exemple assert position_facteur("ana", "banane") == 1. L'annexe mentionne assert sans message d'erreur.

6.3Invariants et variants

Ces notions seront formalisées au second semestre. Dès maintenant, il faut savoir énoncer l'invariant d'un algorithme en une phrase.

Un test ne prouve jamais qu'un programme est correct, il peut seulement montrer qu'il est faux. Un invariant correctement démontré prouve la correction de l'algorithme, mais pas l'absence d'erreur de frappe dans le code. Les deux démarches sont complémentaires.

Méthodes

Ce qu'il faut savoir refaire en khôlle

1. Écrire la recherche naïve d'un facteur dans un texte, justifier les bornes, et donner son coût dans le cas le pire avec un exemple qui le réalise.
2. Écrire la recherche des deux valeurs les plus proches par examen des paires, et montrer qu'elle fait $\frac{n(n-1)}{2}$ comparaisons.
3. Expliquer comment trier le tableau permet de faire mieux pour ce problème.
4. Écrire le tri à bulles, énoncer ses deux invariants, et compter ses comparaisons.
5. Écrire la version avec arrêt anticipé et donner son coût sur une liste déjà triée.
6. Définir la complexité quadratique et prévoir l'effet d'un doublement de la taille sur le temps d'exécution.
7. Proposer un jeu de tests pour une fonction donnée et placer des assertions pertinentes.
8. Donner un variant pour une boucle while et expliquer ce qu'il prouve.

Les résultats à connaître

Le programme cite ces algorithmes comme exemples d'activités. Il ne les impose pas, mais tout sujet suppose qu'on sache les réécrire, les compter et les justifier.

• Sommes usuelles. On a 1 + 2 + … + n = n(n + 1)/2. Il y a n(n − 1)/2 paires i < j et n(n − 1)(n − 2)/6 triplets i < j < k. Calculs exigibles.
• Coût d'une boucle. C'est la somme des coûts de chaque tour, exprimés en fonction de l'indice extérieur. Méthode exigible.
• Recherche naïve d'un facteur. Pour m de longueur p et t de longueur n, on fait au plus (n − p + 1) × p comparaisons, borne atteinte par un exemple explicite. À savoir réécrire.
• Deux valeurs les plus proches par examen des paires. Pour au moins deux éléments, on calcule exactement n(n − 1)/2 écarts. À savoir réécrire.
• Lemme des voisins. Dans une liste triée, l'écart minimal est atteint par deux cases consécutives. À savoir démontrer.
• Tri à bulles. Il fait exactement n(n − 1)/2 comparaisons. Son nombre d'échanges égale le nombre d'inversions initial (exercice 9). À savoir réécrire.
• Tri à bulles avec arrêt anticipé. Coût linéaire sur une liste triée, quadratique dans le pire cas.
• Complexité quadratique. Coût dans le pire cas de l'ordre de n², où n mesure la taille de l'entrée. Seul le pire cas est au programme.
• Taille de l'entrée. Pour une matrice n × n, la taille est n². Un coût en n² y est linéaire en la taille.
• Faits de langage. range(a, b) est vide si a ≥ b. Réaffecter l'indice d'une boucle for est sans effet sur le tour suivant. Un return quitte toutes les boucles de la fonction. [[0] * n] * n crée n références vers la même ligne.
• Hors programme. Les algorithmes linéaires de recherche de motif et le coût moyen.

Clés de démonstration

Nombre de paires. Pour i fixé, for j in range(i + 1, n) fait n − 1 − i tours. La somme de i = 0 à n − 1 vaut n(n − 1)/2. Astuce : chaque tour correspond à une paire {i, j}, vue une seule fois.

Pire cas de la recherche de facteur. La structure des boucles donne la majoration. Pour conclure au coût quadratique, il faut une entrée qui atteint la borne. Astuce : un texte de a et un mot de a terminé par b obligent à lire tout le mot à chaque position.

Correction de la recherche de facteur. Invariant du for : au début du tour i, m n'apparaît à aucune position inférieure à i. Invariant du while : t[i + j] == m[j] pour tout j < k. Astuce : en sortie, k == p signifie que tout le mot concorde.

Lemme des voisins. Soit t trié et i < j. Alors t[j] ≥ t[i + 1], donc t[j] − t[i] ≥ t[i + 1] − t[i]. Astuce : on minore l'écart de toute paire par celui d'une paire consécutive, sans valeur absolue.

Tri à bulles avec arrêt. Un parcours de t[0], …, t[f] sans échange prouve t[j] ≤ t[j + 1] pour tout j < f, donc la zone est triée. Avec l'invariant « la fin contient les plus grands éléments, triés », toute la liste l'est. Astuce : l'absence d'échange renseigne sur toutes les paires voisines à la fois.

Échanges et inversions. Échanger deux voisins t[j] > t[j + 1] ne change l'ordre relatif que de ces deux éléments. Le nombre d'inversions baisse donc d'exactement 1. Astuce : c'est un variant, qui finit à 0 pour une liste triée.

Exemples et contre-exemples à connaître

1. Texte « aaaaaa » et mot « aab ». Chaque position coûte 3 comparaisons, c'est le modèle du pire cas.
2. Le mot vide est facteur aux n + 1 positions de range(n + 1). Un compteur d'occurrences doit fixer cette convention.
3. Dans la recherche de doublons, range(n) au lieu de range(i + 1, n) compare t[i] à lui-même, et la fonction répond toujours True.
4. m = [[0] * 3] * 3 puis m[0][0] = 1 modifie les trois lignes. On crée les lignes une par une avec append.
5. Une boucle de n tours contenant une boucle de 5 tours fait 5n tours. Imbriquer ne rend pas forcément quadratique.
6. for i in range(n) contenant un while qui double j jusqu'à n coûte de l'ordre de n log n.
7. Avec >= au lieu de >, le tri à bulles n'est plus stable. Dans une version avec drapeau qui ne raccourcit pas la zone, [1, 1] fait même boucler indéfiniment.
8. Tester la symétrie d'une matrice n × n est quadratique en n mais linéaire en le nombre de coefficients.
9. Une liste strictement décroissante a n(n − 1)/2 inversions, et le tri à bulles échange à chaque comparaison.

Techniques du chapitre

Technique 1 : nommer les indices avant d'écrire. Mini-exercice : tester si deux listes a et b ont un élément commun. i parcourt a, j parcourt b, les boucles sont indépendantes. On renvoie True dès que a[i] == b[j], et False après les deux boucles. Coût au pire : len(a) × len(b).

Technique 2 : compter les tours intérieurs, puis sommer. Mini-exercice : for i in range(n) contenant for j in range(2 * i). L'intérieure fait 2i tours, le total vaut 2 × (0 + … + (n − 1)) = n(n − 1).

Technique 3 : majorer, puis exhiber un pire cas. Mini-exercice : la recherche de doublons fait au plus n(n − 1)/2 tests. Une liste d'éléments distincts ne déclenche aucun return et atteint la borne.

Technique 4 : sortir de deux boucles avec return. Mini-exercice : renvoyer la première paire i < j avec t[i] + t[j] == 0. Dans une fonction, return (i, j) quitte tout, et return None final traite l'absence.

Technique 5 : mettre la réponse partielle dans l'invariant extérieur. Mini-exercice : pour les doublons, au début du tour i, aucune paire a < b avec a < i ne vérifie t[a] == t[b]. En fin de boucle, toutes les paires sont couvertes.

Technique 6 : repérer les boucles cachées. Mini-exercice : for i in range(n) contenant if t[i] in t[:i]. La tranche et le test in coûtent chacun de l'ordre de i, le total est de l'ordre de n².

Technique 7 : casser le quadratique par un précalcul. Mini-exercice : calculer toutes les sommes t[0] + … + t[k]. On ajoute t[k] à une variable s à chaque tour au lieu de tout recalculer, et l'on passe de n² à un coût linéaire.

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):
        c = c + 1
d = 0
for i in range(n):
    for j in range(i):
        for k in range(j):
            d = d + 1

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

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

def nb_occurrences(m, t):
    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 tri_bulles_arret(t):
    fin = len(t) - 1
    echange = True
    while echange:
        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

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 plus_proches_trie(t):
    k = 0
    for i in range(1, len(t) - 1):
        if t[i + 1] - t[i] < t[k + 1] - t[k]:
            k = i
    return (k, k + 1)

def f1(t):
    c = 0
    for i in range(len(t)):
        if t[i] in t[:i]:
            c = c + 1
    return c

def f2(t):
    c = 0
    for i in range(len(t)):
        j = 1
        while j < len(t):
            j = 2 * j
            c = c + 1
    return c

def inversions(t):
    n = len(t)
    c = 0
    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