Kokia yra sudėtingumo asimptotika paieškai sąraše su įmontuotu ciklu?

Jei turite sąrašą ir atliekate paiešką naudodami įdėtą ciklą (pavyzdžiui, du įdėti ciklai toje pačioje sąraše), tokios paieškos asimptotinė sudėtingumas paprastai bus O(n²), kur n yra sąrašo dydis.

Tai vyksta todėl, kad išorinis ciklas vyksta n kartų, ir kiekvieno praeities metu vidinis ciklas taip pat vyksta n kartų, iš viso gaunant n * n = n² operacijų.

Pavyzdys:

for i in range(len(lst)):
    for j in range(len(lst)):
        if lst[i] == lst[j]:
            # kokia nors operacija