O buclă în interiorul unei bucle
O(n²) înseamnă timp pătratic: munca crește odată cu pătratul datelor de intrare. De două ori mai multe elemente înseamnă de patru ori mai mulți pași. De zece ori mai multe elemente înseamnă de o sută de ori mai mulți pași.
Forma tipică în cod este o buclă în interiorul unei bucle, ambele parcurgând aceleași date. Bucla exterioară rulează de n ori, iar pentru fiecare dintre aceste rulări bucla interioară rulează din nou de n ori: n · n pași.
Timpul pătratic este în regulă pentru liste mici. Pentru 100.000 de elemente înseamnă deja 10 miliarde de pași — acesta este momentul în care programele încep să se blocheze.
Toate perechile
Cea mai directă sarcină O(n²): combinarea fiecărui element cu fiecare element. 4 litere formează 4 · 4 = 16 perechi; 100 de litere ar forma 10.000.
Construiește fiecare pereche
Bucla exterioară alege x, iar bucla interioară îl împerechează cu fiecare y. 4 elemente produc 16 perechi — pătratul dimensiunii datelor de intrare.
Ieșire: program Python complet
letters = ["a", "b", "c", "d"]
pairs = 0
for x in letters:
for y in letters:
print(x + y, end=" ")
pairs += 1
print()
print(len(letters), "elemente au format", pairs, "perechi")
Sortarea cu bule
Sortarea cu bule (bubble sort) este algoritmul pătratic clasic: parcurge lista în mod repetat și interschimbă vecinii aflați în ordinea greșită. Valorile mari „urcă” spre capăt, câte o parcurgere pe rând.
Cu cele două bucle imbricate ale sale, face aproximativ n²/2 comparații. Este un algoritm excelent din care să înveți — și unul prost de folosit: nums.sort() face aceeași treabă în O(n log n).
Sortează cu două bucle imbricate
Sortarea a 5 elemente necesită 4 + 3 + 2 + 1 = 10 comparații. Pentru 1.000 de elemente ar fi aproximativ o jumătate de milion — în timp ce o sortare O(n log n) are nevoie de aproximativ zece mii.
Ieșire: program Python complet
nums = [5, 3, 8, 1, 4]
comparisons = 0
for i in range(len(nums) - 1):
for j in range(len(nums) - 1 - i):
comparisons += 1
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
print("sortată:", nums)
print("comparații:", comparisons)
Duplicate pe calea lentă
Verificarea fiecărui element cu fiecare element care vine după el este un alt tipar cu bucle imbricate — compararea tuturor perechilor pentru a găsi un duplicat.
Funcționează, dar este O(n²). Pagina despre complexitatea în spațiu din acest grup arată trucul standard care face acest lucru liniar: reține valorile pe care le-ai văzut deja într-o mulțime.
Găsește un duplicat cu două bucle
Fiecare element este comparat cu fiecare element de după el. Perechea duplicată de 1 este găsită după 7 verificări; în cel mai rău caz — niciun duplicat — rulează toate cele 15 verificări de perechi.
Ieșire: program Python complet
nums = [3, 1, 4, 1, 5, 9]
checks = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
checks += 1
if nums[i] == nums[j]:
print("duplicat:", nums[i], "după", checks, "verificări")