Kāda ir meklēšanas ar iekšējo ciklu asimptotiskā sarežģītība?

Ja jums ir saraksts, un jūs veicat meklēšanu, izmantojot iekļauto ciklu (piemēram, divi iekļauti cikli tajā pašā sarakstā), tad šādas meklēšanas asimptotiskā sarežģītība parasti būs O(n²), kur n ir saraksta lielums.

Tas notiek tāpēc, ka ārējais cikls tiek izpildīts n reizes, un katrā pārejas reizē iekšējais cikls arī tiek izpildīts n reizes, kopā veidojot n * n = n² operācijas.

Piemērs:

for i in range(len(lst)):
    for j in range(len(lst)):
        if lst[i] == lst[j]:
            # kāda operācija