Big O pentru memorie
Big O poate descrie memoria la fel cum descrie timpul: de cât spațiu suplimentar are nevoie algoritmul pe măsură ce datele de intrare cresc?
Numărăm doar spațiul suplimentar — variabilele și tablourile pe care le creează algoritmul — nu și datele de intrare. Acest spațiu suplimentar se numește spațiu auxiliar.
Spațiu O(1): un număr fix de variabile, indiferent de datele de intrare. Spațiu O(n): se stochează ceva nou pentru fiecare element de intrare, de exemplu o copie sau un Map cu valorile deja văzute.
Spațiu O(1)
Un algoritm care păstrează doar câteva variabile simple folosește spațiu constant. Tabloul poate avea zece elemente sau zece milioane — algoritmul în sine tot doar contoarele sale le deține.
Însumarea, găsirea maximului și căutarea liniară au toate timp O(n), dar spațiu O(1): citesc mult și rețin aproape nimic.
Sumă cu o singură variabilă
Întregul algoritm reține exact un singur număr, sum. Consumul său de memorie nu crește odată cu tabloul: spațiu O(1).
Ieșire: program TypeScript și rezultatul capturat
const nums = [3, 1, 4, 1, 5, 9, 2, 6]
// O singură variabilă suplimentară, oricât de lung ar fi tabloul.
let sum = 0
for (const n of nums) {
sum += n
}
console.log("suma:", sum)
Spațiu O(n)
De îndată ce algoritmul construiește ceva cu o intrare pentru fiecare element de intrare — un tablou nou, un Map — spațiul său este O(n): dublezi datele de intrare, dublezi memoria.
Asta nu este un lucru rău în sine. Este pur și simplu un cost pe care ar trebui să îl observi, pentru că poate fi schimbat pe altceva.
Construirea unui tablou nou
Tabloul de ieșire primește câte un element pentru fiecare element de intrare. 5 la intrare, 5 la ieșire — memoria crește în pas cu datele de intrare: spațiu O(n).
Ieșire: program TypeScript și rezultatul capturat
const nums = [1, 2, 3, 4, 5]
// Un tablou nou cu un element pentru fiecare element de intrare.
const doubled: number[] = []
for (const n of nums) {
doubled.push(n * 2)
}
console.log("intrare:", nums)
console.log("ieșire: ", doubled)
Schimbul spațiului pe timp
Deseori poți cheltui memorie ca să economisești timp. Exemplul clasic este Two Sum: găsirea a două numere dintr-un tablou care însumate dau o valoare țintă.
Calea directă verifică fiecare pereche — timp O(n²), spațiu O(1). Calea rapidă parcurge tabloul o singură dată și reține fiecare număr văzut într-un Map. Pentru fiecare număr se întreabă: „am văzut deja target - n?” — timp O(n), spațiu O(n).
Acest schimb merită de obicei: memoria poate fi adăugată unei mașini, timpul nu.
Two Sum cu două bucle
Fiecare pereche este verificată până apare o potrivire — până la 15 verificări pentru 6 elemente, iar numărul crește cu pătratul datelor de intrare. Nu se folosește memorie suplimentară.
Ieșire: program TypeScript și rezultatul capturat
const nums = [2, 11, 15, 1, 8, 7]
const target = 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] === target) {
console.log("găsit:", nums[i], "+", nums[j], "după", checks, "verificări")
}
}
}
console.log("total verificări:", checks)
Two Sum cu un Map
O singură parcurgere, 6 verificări. Fiecare număr este căutat cu seen.has() și stocat cu seen.set() — lucru în timp constant pentru fiecare element. Map-ul este memoria O(n) care cumpără timpul O(n).
Ieșire: program TypeScript și rezultatul capturat
const nums = [2, 11, 15, 1, 8, 7]
const target = 9
// O intrare pentru fiecare element văzut până acum: memoria O(n).
const seen = new Map<number, boolean>()
for (const n of nums) {
if (seen.has(target - n)) {
console.log("găsit:", target - n, "+", n)
}
seen.set(n, true)
}
console.log("au fost verificate", nums.length, "elemente o singură dată")