Complexité O(n²) — paires en double boucle

O(n²), ca veut dire quadratique. Le temps d'execution augmente avec le carre de la taille des données. Si ta liste double, le temps est multiplie par 4.

C'est typiquement ce qui se passe quand tu as deux boucles imbriquees : pour chaque élément, tu regardes tous les autres.

Imagine que tu as une classe de 30 eleves et que chaque eleve doit serrer la main de tous les autres. Le nombre de poignees de main n'est pas 30, c'est environ 30 x 29 / 2 = 435.

Écris une fonction trouver_paires(lst, cible) qui retourne la liste de toutes les paires (i, j) avec i < j telles que lst[i] + lst[j] == cible. Les paires contiennent les valeurs, pas les indices.

Exemple :
trouver_paires([1, 2, 3, 4], 5) renvoie [(1, 4), (2, 3)]
trouver_paires([1, 1, 1], 2) renvoie [(1, 1), (1, 1), (1, 1)]

Tests (2/4)

Paires basiques

assert trouver_paires([1, 2, 3, 4], 5) == [(1, 4), (2, 3)]

Aucune paire

assert trouver_paires([1, 2, 3], 10) == []

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

def trouver_paires(lst, cible):
    paires = []
    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):
            if lst[i] + lst[j] == cible:
                paires.append((lst[i], lst[j]))
    return paires

← Complexité O(n) — somme d'une … Complexité O(log n) — recherche … →

solution.py

Bravo!

Complexité O(n²) — paires en double boucle

Tests (2/4)

Indices (3 disponibles)

Solution officielle