O buclă în interiorul altei bucle
O(n²) înseamnă timp pătratic: munca crește cu pătratul intrării. De două ori mai multe elemente, de patru ori mai mulți pași. De zece ori mai multe elemente, de o sută de ori mai mulți pași.
Forma care trădează acest caz în cod este o buclă în interiorul altei bucle, ambele parcurgând aceleași date. Bucla exterioară rulează de n ori, iar pentru fiecare dintre acestea bucla interioară rulează din nou de n ori: n · n pași.
Timpul pătratic este acceptabil pentru tablouri mici. Pentru 100.000 de elemente înseamnă deja 10 miliarde de pași — acolo încep programele să se blocheze.
Toate perechile
Cea mai directă sarcină O(n²): combină fiecare 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 intrării.
Ieșire: program TypeScript și rezultatul capturat
const letters = ["a", "b", "c", "d"]
let pairs = 0
for (const x of letters) {
const row: string[] = []
for (const y of letters) {
row.push(x + y)
pairs++
}
console.log(row.join(" "))
}
console.log(letters.length, "elemente au format", pairs, "perechi")
Bubble sort
Bubble sort este algoritmul pătratic clasic: parcurge tabloul în mod repetat și interschimbă vecinii aflați în ordine greșită. Valorile mari „urcă la suprafață” spre final, câte o trecere 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((a, b) => a - b) face aceeași treabă în O(n log n).
Sortare 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 TypeScript și rezultatul capturat
const nums = [5, 3, 8, 1, 4]
let comparisons = 0
for (let i = 0; i < nums.length - 1; i++) {
for (let j = 0; j < nums.length - 1 - i; j++) {
comparisons++
if (nums[j] > nums[j + 1]) {
const left = nums[j]
nums[j] = nums[j + 1]
nums[j + 1] = left
}
}
}
console.log("sortat:", nums)
console.log("comparații:", comparisons)
Duplicate pe calea lentă
Verificarea fiecărui element față de 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 Complexitate spațială din acest grup arată trucul standard care face acest lucru liniar: reține într-un Map valorile pe care le-ai văzut deja.
Găsește un duplicat cu două bucle
Fiecare element este comparat cu fiecare element ulterior. Perechea duplicată de valori 1 este găsită după 7 verificări; în cazul cel mai defavorabil — niciun duplicat — rulează toate cele 15 verificări de perechi.
Ieșire: program TypeScript și rezultatul capturat
const nums = [3, 1, 4, 1, 5, 9]
let checks = 0
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
checks++
if (nums[i] === nums[j]) {
console.log("duplicat:", nums[i], "după", checks, "verificări")
}
}
}