Quelle est la complexité asymptotique de la recherche dans une liste avec une boucle imbriquée?

Si vous avez une liste et que vous effectuez une recherche à l'aide d'une boucle imbriquée (par exemple, deux boucles imbriquées sur la même liste), la complexité asymptotique de cette recherche sera généralement de O(n²), où n est la taille de la liste.

Cela se produit parce que la boucle externe s'exécute n fois, et pour chaque passage, la boucle interne s'exécute également n fois, soit au total n * n = n² opérations.

Exemple:

for i in range(len(lst)):
    for j in range(len(lst)):
        if lst[i] == lst[j]:
            # une opération quelconque