Big O pentru memorie
Big O poate descrie memoria la fel cum descrie timpul: cât spațiu suplimentar are nevoie algoritmul pe măsură ce intrarea crește?
Numărăm doar spațiul suplimentar — variabilele și tablourile create de algoritm — nu intrarea însăși. Acest spațiu suplimentar se numește spațiu auxiliar.
Spațiu O(1): un număr fix de variabile, oricare ar fi intrarea. Spațiu O(n): se stochează ceva nou pentru fiecare element din intrare, de exemplu o copie sau un tablou asociativ cu valorile deja văzute.
Spațiu O(1)
Un algoritm care ține doar câteva variabile simple folosește spațiu constant. Tabloul poate avea zece elemente sau zece milioane — algoritmul în sine deține tot doar contoarele lui.
Î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ă
Tot algoritmul reține exact un număr, $sum. Consumul lui de memorie nu crește odată cu tabloul: spațiu O(1).
Ieșire: script PHP
<?php
$nums = [3, 1, 4, 1, 5, 9, 2, 6];
// O singură variabilă suplimentară, indiferent cât de lung este tabloul.
$sum = 0;
foreach ($nums as $n) {
$sum += $n;
}
echo "sumă: ", $sum, "\n";
Spațiu O(n)
În clipa în care algoritmul construiește ceva cu o intrare pentru fiecare element din intrare — un tablou nou, un tablou asociativ — 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 merită să îl observi, pentru că poate fi schimbat pe altceva.
Construirea unui tablou nou
Tabloul de ieșire primește un element pentru fiecare element din intrare. 5 intră, 5 ies — memoria crește în pas cu intrarea: spațiu O(n).
Ieșire: script PHP
<?php
$nums = [1, 2, 3, 4, 5];
// Un tablou nou, cu un element pentru fiecare element din intrare.
$doubled = [];
foreach ($nums as $n) {
$doubled[] = $n * 2;
}
echo "intrare: ", implode(", ", $nums), "\n";
echo "ieșire: ", implode(", ", $doubled), "\n";
Schimbul dintre spațiu și timp
Deseori poți cheltui memorie pentru a câștiga timp. Exemplul clasic este Two Sum: găsește în tablou două numere a căror sumă este 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 ca cheie într-un tablou asociativ. Pentru fiecare număr întreabă: „am văzut deja target - n?” — timp O(n), spațiu O(n).
Acest schimb merită de obicei: memoria poate fi adăugată într-o mașină, 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 lor crește cu pătratul intrării. Nu se folosește memorie suplimentară.
Ieșire: script PHP
<?php
$nums = [2, 11, 15, 1, 8, 7];
$target = 9;
$checks = 0;
$n = count($nums);
for ($i = 0; $i < $n; $i++) {
for ($j = $i + 1; $j < $n; $j++) {
$checks++;
if ($nums[$i] + $nums[$j] === $target) {
echo "găsit: ", $nums[$i], " + ", $nums[$j], " după ", $checks, " verificări\n";
}
}
}
echo "total verificări: ", $checks, "\n";
Two Sum cu un tablou asociativ
O singură trecere, 6 verificări. Fiecare număr este căutat cu isset() și stocat în tabloul asociativ $seen — muncă în timp constant pentru fiecare element. Tabloul este memoria O(n) care cumpără timpul O(n).
Ieșire: script PHP
<?php
$nums = [2, 11, 15, 1, 8, 7];
$target = 9;
$seen = [];
foreach ($nums as $n) {
$need = $target - $n;
if (isset($seen[$need])) {
echo "găsit: ", $need, " + ", $n, "\n";
}
$seen[$n] = true;
}
echo "verificate ", count($nums), " elemente, câte o dată\n";