Tous distincts ?

Tous distincts ?

Boucles imbriquées et complexité quadratique · niveau 1 (application)

Énoncé

Écrire une fonction tous_distincts(t) déterminant si tous les éléments de la liste t sont uniques, à l'aide d'une double boucle. Donner sa preuve de correction, sa complexité et la comparer avec la version utilisant un dictionnaire.

Corrigé

def tous_distincts(t: list) -> bool:
    for i in range(len(t)):
        for j in range(i + 1, len(t)):
            # Invariant : aucun couple d'indices distincts visité avant (i, j) n'a de valeurs égales
            if t[i] == t[j]:
                return False
    return True

Correction : Si la fonction s'interrompt en renvoyant False, c'est qu'elle a trouvé $i < j$ avec $t [i] == t [j]$ , ce qui valide la présence d'un doublon. Si elle termine les deux boucles, l'invariant final prouve l'absence de doublon. La borne i + 1 évite de comparer un élément avec lui-même.
Complexité : Au pire, on effectue $\frac{n ( n - 1 )}{2}$ comparaisons, soit une complexité de $O (n^{2})$ .
Comparaison : La méthode avec dictionnaire (chapitre 2) offre un coût de $O (n)$ , mais requiert que les éléments soient hachables. La double boucle fonctionne dès que l'opérateur d'égalité == est défini.

Énoncé

Corrigé

Exercices semblables