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 intrarea crește?
Numărăm doar spațiul suplimentar — variabilele și listele pe care le creează algoritmul — nu și intrarea însăși. Acest spațiu suplimentar se numește spațiu auxiliar.
Spațiu O(1): un număr fix de variabile, indiferent de intrare. Spațiu O(n): se stochează ceva nou pentru fiecare element de intrare, de exemplu o copie sau o mulțime de valori deja văzute.
Spațiu O(1)
Un algoritm care păstrează doar câteva variabile simple folosește spațiu constant. Lista poate avea zece elemente sau zece milioane — algoritmul însuși deține tot doar contoarele sale.
Î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.
Suma cu o singură variabilă
Întregul algoritm reține exact un număr, total. Memoria folosită nu crește odată cu lista: spațiu O(1).
Ieșire: program Python complet
nums = [3, 1, 4, 1, 5, 9, 2, 6]
# O singură variabilă suplimentară, indiferent cât de lungă este lista.
total = 0
for n in nums:
total += n
print("suma:", total)
Spațiu O(n)
De îndată ce algoritmul construiește ceva cu câte o intrare pentru fiecare element de intrare — o listă nouă, un dicționar — spațiul său este O(n): intrare dublă, memorie dublă.
Asta nu este rău în sine. Este pur și simplu un cost pe care trebuie să-l observi, pentru că poate fi schimbat pe altceva.
Construirea unei liste noi
Lista de ieșire primește câte un element pentru fiecare element de intrare. 5 intră, 5 ies — memoria crește în același ritm cu intrarea: spațiu O(n).
Ieșire: program Python complet
nums = [1, 2, 3, 4, 5]
# O listă nouă cu câte un element pentru fiecare element de intrare.
doubled = []
for n in nums:
doubled.append(n * 2)
print("intrare:", nums)
print("ieșire: ", doubled)
Spațiu în schimbul timpului
Deseori poți folosi memorie pentru a economisi timp. Exemplul clasic este Two Sum: găsește două numere dintr-o listă care adunate dau o valoare țintă.
Metoda directă verifică fiecare pereche — timp O(n²), spațiu O(1). Metoda rapidă parcurge lista o singură dată și reține într-o mulțime fiecare număr văzut. Pentru fiecare număr se întreabă: „am văzut deja target - n?” — timp O(n), spațiu O(n).
De obicei acest schimb merită: memorie se poate adăuga unui calculator, timp 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 lor crește cu pătratul intrării. Nu se folosește memorie suplimentară.
Ieșire: program Python complet
nums = [2, 11, 15, 1, 8, 7]
target = 9
checks = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
checks += 1
if nums[i] + nums[j] == target:
print("găsit:", nums[i], "+", nums[j], "după verificări:", checks)
print("total verificări:", checks)
Two Sum cu o mulțime
O singură parcurgere, 6 verificări. Fiecare număr este căutat și stocat în mulțimea seen — muncă în timp constant pentru fiecare element. Mulțimea este memoria O(n) care cumpără timpul O(n).
Ieșire: program Python complet
nums = [2, 11, 15, 1, 8, 7]
target = 9
seen = set()
for n in nums:
if target - n in seen:
print("găsit:", target - n, "+", n)
seen.add(n)
print("elemente verificate câte o dată:", len(nums))