Wie ist die asymptotische Komplexität der Suche in einer Liste mit einer verschachtelten Schleife?

Wenn Sie eine Liste haben und eine Suche mit einer verschachtelten Schleife durchführen (z.B. zwei verschachtelte Schleifen über dieselbe Liste), ist die asymptotische Komplexität dieser Suche in der Regel O(n²), wobei n die Größe der Liste ist.

Dies liegt daran, dass die äußere Schleife n-mal ausgeführt wird, und für jeden Durchlauf wird die innere Schleife ebenfalls n-mal ausgeführt, insgesamt also n * n = n² Operationen.

Beispiel:

for i in range(len(lst)):
    for j in range(len(lst)):
        if lst[i] == lst[j]:
            # eine Operation