Space Complexity

Time complexity saja tidak cukup untuk menilai kualitas algoritma. Sebuah algoritma mungkin sangat cepat tetapi menghabiskan memori besar, sehingga tidak bisa dipakai pada perangkat dengan RAM terbatas atau pada input berukuran masif. Space complexity mengukur jumlah memori tambahan yang dialokasikan algoritma sebagai fungsi dari n. Pada Chapter ini kita akan memisahkan konsep auxiliary space dari total space, memahami alokasi pada stack dan heap, serta membandingkan space complexity beberapa algoritma yang menghasilkan output identik.

Komponen Space Complexity #

Space complexity total sebuah algoritma terdiri dari dua bagian:

Input space — memori yang dipakai untuk menyimpan input itu sendiri. Untuk fungsi sort(arr), ukuran array arr adalah bagian input space.
Auxiliary space — memori tambahan yang dialokasikan algoritma di luar input. Misalnya array bantu pada merge sort, atau call stack pada fungsi rekursif.

Memori di C++: Stack vs Heap #

C++ mengalokasikan memori pada dua region utama:

Stack — memori otomatis untuk variabel lokal. Cepat, tetapi ukurannya terbatas (tipikal 1–8 MB per thread). Fungsi rekursif yang dalam bisa menyebabkan stack overflow.
Heap — memori dinamis yang dikelola melalui new/delete atau smart pointer. Ukurannya besar (terbatas RAM fisik), tetapi alokasi dan dealokasi lebih lambat.

Aspek	Stack	Heap
Kecepatan alokasi	Sangat cepat	Lebih lambat
Ukuran tipikal	1–8 MB	Sesuai RAM
Manajemen lifetime	Otomatis (RAII)	Manual atau smart pointer
Fragmentasi	Tidak ada	Mungkin terjadi
Cocok untuk	Variabel lokal kecil	Struktur data besar

Menghitung Space Complexity #

Aturan Praktis #

Variabel primitif lokal (int, double, pointer) berkontribusi O(1).
Array/container lokal berukuran n berkontribusi O(n).
Setiap pemanggilan fungsi menambahkan satu stack frame berukuran O(1) untuk variabel lokal primitifnya.
Fungsi rekursif dengan kedalaman d menambah O(d) stack frame; bila setiap frame menyimpan array lokal berukuran k, kontribusinya O(d × k).

Kode: Dua Pendekatan Penjumlahan Elemen Array #

cpp
#include <iostream>
#include <vector>

// Pendekatan iteratif: auxiliary space O(1)
long long jumlahIteratif(const std::vector<int>& v) {
    long long total = 0;                    // O(1)
    for (int x : v) total += x;             // O(1) per iterasi
    return total;
}

// Pendekatan rekursif: auxiliary space O(n) untuk call stack
long long jumlahRekursif(const std::vector<int>& v, std::size_t i) {
    if (i == v.size()) return 0;             // base case
    return static_cast<long long>(v[i]) +    // recursive case
           jumlahRekursif(v, i + 1);
}

int main() {
    std::vector<int> data{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    std::cout << "Iteratif : " << jumlahIteratif(data) << '\n';
    std::cout << "Rekursif : " << jumlahRekursif(data, 0) << '\n';
    return 0;
}

Output yang Dihasilkan:

text

Iteratif : 55
Rekursif : 55

Bedah Kode Baris-per-Baris #

Baris long long total = 0;: variabel lokal primitif. Stack frame jumlahIteratif menyimpan satu variabel total saja, yaitu O(1).
Baris for (int x : v): x juga primitif O(1). Loop tidak menambah alokasi memori tambahan.
Baris if (i == v.size()) return 0;: base case rekursif. Pada saat ini, call stack sudah berisi n+1 frame.
Baris return ... + jumlahRekursif(v, i + 1);: setiap pemanggilan rekursif menambah satu stack frame. Untuk array berukuran n, kedalaman rekursi mencapai n+1, sehingga auxiliary space O(n).
Output: kedua fungsi menghasilkan jumlah yang sama (55), tetapi space complexity keduanya berbeda: iteratif O(1), rekursif O(n).

Contoh Konkret: Tiga Algoritma dengan Space Berbeda #

Mekanisme Tiga Algoritma Membalik Array #

Kita akan membandingkan tiga algoritma membalik array: (1) iteratif in-place dengan dua pointer, (2) membuat array baru yang berisi elemen-elemen terbalik, dan (3) rekursif in-place dengan mempertukarkan ujung-ujung lalu rekursi ke bagian tengah.

Kode Program #

cpp
#include <iostream>
#include <vector>

// 1) In-place iteratif: O(1) auxiliary
void balikInPlace(std::vector<int>& v) {
    int lo = 0, hi = static_cast<int>(v.size()) - 1;
    while (lo < hi) {
        std::swap(v[lo], v[hi]);
        ++lo; --hi;
    }
}

// 2) Salinan ke array baru: O(n) auxiliary
std::vector<int> balikSalinan(const std::vector<int>& v) {
    std::vector<int> hasil;
    hasil.reserve(v.size());
    for (std::size_t i = v.size(); i-- > 0;) {
        hasil.push_back(v[i]);
    }
    return hasil;
}

// 3) Rekursif in-place: O(n) call stack
void balikRekursif(std::vector<int>& v, int lo, int hi) {
    if (lo >= hi) return;
    std::swap(v[lo], v[hi]);
    balikRekursif(v, lo + 1, hi - 1);
}

void cetak(const std::vector<int>& v) {
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

int main() {
    std::vector<int> a = {1, 2, 3, 4, 5};
    balikInPlace(a);
    cetak(a);

    std::vector<int> b = {1, 2, 3, 4, 5};
    auto c = balikSalinan(b);
    cetak(c);

    std::vector<int> d = {1, 2, 3, 4, 5};
    balikRekursif(d, 0, static_cast<int>(d.size()) - 1);
    cetak(d);
    return 0;
}

Output yang Dihasilkan:

Bedah Kode Baris-per-Baris #

Fungsi balikInPlace: hanya memakai variabel lo dan hi (O(1)). Operasi std::swap pada int tidak menambah alokasi. Total auxiliary space: O(1).
Baris hasil.reserve(v.size());: memesan kapasitas v.size() pada hasil. Operasi reserve tidak mengubah size(), hanya capacity(), sehingga push_back berikutnya tidak perlu realokasi.
Fungsi balikSalinan: membuat std::vector<int> hasil baru berukuran n. Auxiliary space: O(n) karena hasil dialokasikan di heap dan terus hidup selama fungsi berjalan.
Fungsi balikRekursif: tidak membuat array baru, tetapi setiap pemanggilan rekursif menambah stack frame. Kedalaman rekursi untuk n=5 adalah n/2 = 2, namun untuk n umum adalah ⌈n/2⌉. Auxiliary space: O(n) untuk call stack.
Output: ketiga algoritma menghasilkan array yang sama-sama terbalik. Pilihan antar ketiganya adalah trade-off antara kejelasan kode, kecepatan, dan pemakaian memori.

Trade-off Space vs Time #

Salah satu prinsip penting DSA adalah space-time trade-off. Kita sering bisa menukar memori dengan waktu, atau sebaliknya:

Teknik	Time →	Space →
Memoization pada DP	Berkurang (dari eksponensial ke polinomial)	Bertambah (perlu tabel)
Prefix sum	Query `O(1)` (vs `O(n)` recompute)	`O(n)` untuk tabel prefix
Caching / buffer	Akses berulang jadi `O(1)`	Bertambah sesuai ukuran cache
In-place sort	Sama dengan non-in-place	Berkurang (tanpa array bantu)
Precompute lookup table	Komputasi `O(1)` per query	Bertambah sesuai tabel

flowchart LR A[Masalah] --> B{Prioritas?} B -- Cepat --> C[Precompute + caching] B -- Hemat memori --> D[In-place / recomputation]

Space Complexity Algoritma Umum #

Algoritma	Time (worst)	Space (auxiliary)
Linear search	`O(n)`	`O(1)`
Binary search iteratif	`O(log n)`	`O(1)`
Binary search rekursif	`O(log n)`	`O(log n)`
Insertion sort	`O(n²)`	`O(1)`
Merge sort	`O(n log n)`	`O(n)`
Quick sort (average)	`O(n log n)`	`O(log n)`
Heap sort	`O(n log n)`	`O(1)`
Counting sort	`O(n + k)`	`O(n + k)`
DFS rekursif	`O(V + E)`	`O(V)`
BFS dengan queue	`O(V + E)`	`O(V)`

Ringkasan #

Space complexity mengukur memori tambahan yang dipakai algoritma sebagai fungsi dari n.
Auxiliary space adalah memori di luar input; inilah yang biasanya kita maksud saat menyebut “space complexity”.
Stack cocok untuk variabel lokal kecil; heap cocok untuk struktur data besar.
Rekursi memakai O(d) stack frame dengan d adalah kedalaman rekursi.
Sering terjadi trade-off antara space dan time: memoization, prefix sum, caching semua menukar memori dengan kecepatan.

Pada Chapter berikutnya kita akan memformalkan cara menuliskan kompleksitas dengan notasi Big-O, yang menjadi bahasa standar untuk menyatakan batas atas pertumbuhan fungsi.