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 slice-urile 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 intrare. Spațiu O(n): se stochează ceva nou pentru fiecare element din 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. Slice-ul poate avea zece elemente sau zece milioane — algoritmul în sine tot doar contoarele lui le deține.
Adunarea, 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. Memoria folosită nu crește odată cu slice-ul: spațiu O(1).
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func main() {
nums := []int{3, 1, 4, 1, 5, 9, 2, 6}
// O singură variabilă în plus, indiferent cât de lung este slice-ul.
sum := 0
for _, n := range nums {
sum += n
}
fmt.Println("suma:", sum)
}
Spațiu O(n)
De îndată ce algoritmul construiește ceva cu câte o intrare pentru fiecare element — un slice nou, un map — spațiul lui este O(n): dublezi intrarea, dublezi memoria.
Asta nu este rău în sine. Este pur și simplu un cost pe care trebuie să îl observi, pentru că poate fi dat la schimb.
Construirea unui slice nou
Slice-ul de ieșire primește câte un element pentru fiecare element de intrare. 5 intră, 5 ies — memoria crește în pas cu intrarea: spațiu O(n).
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func main() {
nums := []int{1, 2, 3, 4, 5}
// Un slice nou, cu câte un element pentru fiecare element de intrare.
doubled := make([]int, 0, len(nums))
for _, n := range nums {
doubled = append(doubled, n*2)
}
fmt.Println("intrare:", nums)
fmt.Println("ieșire: ", doubled)
}
Spațiu dat la schimb pentru timp
De multe ori poți cheltui memorie ca să economisești timp. Exemplul clasic este Two Sum: găsește într-un slice două numere care adunate dau o valoare țintă.
Metoda directă verifică fiecare pereche — timp O(n²), spațiu O(1). Metoda rapidă parcurge slice-ul o singură dată și reține într-un map fiecare număr văzut. Pentru fiecare număr întreabă: „am văzut deja target - n?” — timp O(n), spațiu O(n).
De obicei schimbul merită: memorie se mai poate adăuga într-o mașină, 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 Go și rezultatul capturat
package main
import "fmt"
func main() {
nums := []int{2, 11, 15, 1, 8, 7}
target := 9
checks := 0
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
checks++
if nums[i]+nums[j] == target {
fmt.Println("găsit:", nums[i], "+", nums[j], "după", checks, "verificări")
}
}
}
fmt.Println("total verificări:", checks)
}
Two Sum cu un map
O singură parcurgere, 6 verificări. Fiecare număr este căutat și stocat în map-ul seen — lucru în timp constant pentru fiecare element. Map-ul este memoria O(n) care cumpără timpul O(n).
Ieșire: program Go și rezultatul capturat
package main
import "fmt"
func main() {
nums := []int{2, 11, 15, 1, 8, 7}
target := 9
seen := map[int]bool{}
for _, n := range nums {
if seen[target-n] {
fmt.Println("găsit:", target-n, "+", n)
}
seen[n] = true
}
fmt.Println("verificate", len(nums), "elemente o singură dată")
}