Kompleksitas ruang

Waktu bukan satu-satunya sumber daya yang dihitung dalam analisis algoritma. Setiap daftar tambahan, setiap variabel, dan setiap pemanggilan fungsi memakan memori, dan jumlahnya juga tumbuh mengikuti ukuran masukan. Topik ini menghitung pemakaian ruang dengan penghitungan yang sama seperti waktu, membuktikannya lewat demo yang dapat dijalankan, lalu menutupnya dengan tabel trade-off antara waktu dan memori beserta soal latihan.

Ruang tambahan, bukan ukuran masukan#

Istilah kuncinya adalah auxiliary space, yaitu memori tambahan yang dibuat algoritma di luar masukannya. Masukan sendiri tidak ikut dihitung, sebab kalau dihitung, setiap algoritma yang menerima daftar sepanjang $n$ otomatis berutang $O(n)$ ruang dan tidak ada gunanya dibedakan satu sama lain. Dengan menghitung ruang tambahan saja, algoritma yang bekerja di tempat dapat berbeda kelas dengan algoritma yang menyalin dulu sebelum bekerja.

Contohnya langsung terlihat pada dua pekerjaan yang serupa. Menjumlahkan seluruh isi daftar hanya butuh satu variabel akumulasi, sehingga ruang tambahannya $O(1)$. Menyalin isi daftar yang sudah terurut ke daftar hasil butuh $n$ sel baru, sehingga ruang tambahannya $O(n)$, meskipun waktunya sama-sama $O(n)$. Konstanta dan suku rendah juga dibuang di sini, dan ruang dihitung pada kasus terburuk, persis seperti waktu.

Satu kebiasaan membantu saat menghitung ruang, yaitu mengabaikan variabel yang hanya menyimpan satu bilangan. Penghitung, indeks, dan penunjuk dianggap berbiaya tetap karena ukurannya tidak tumbuh bersama masukan. Yang diperhitungkan adalah struktur yang besarnya bergantung pada $n$, seperti daftar hasil, tabel bantu, atau kedalaman pemanggilan. Dari kebiasaan inilah keputusan seperti membalik di tempat atau menyalin dulu terasa bobotnya berbeda.

Dua solusi, satu masalah#

Demo berikut menyelesaikan satu masalah dengan dua solusi, yaitu membalik urutan daftar catatan suhu. Solusi pertama menyusun daftar baru dari ujung akhir, sehingga ia membuat $n$ sel tambahan. Solusi kedua menukar elemen dari dua ujung menuju tengah tanpa membuat struktur baru, dan cara kerja semacam ini disebut in-place, yaitu mengubah masukan langsung di tempatnya. Ruang tambahan dihitung sebagai panjang struktur baru yang dibuat di dalam fungsi.

# Dua cara membalik urutan daftar dan hitungan ruang tambahannya.
# Ruang tambahan dihitung dari struktur baru yang dibuat di dalam
# fungsi, bukan dari daftar masukan itu sendiri.

def balik_dengan_daftar_baru(data):
    hasil = []                     # struktur baru sepanjang n
    for i in range(len(data) - 1, -1, -1):
        hasil.append(data[i])
    return hasil, len(hasil)       # satu elemen tambahan per elemen masukan

def balik_secara_in_place(data):
    kiri, kanan = 0, len(data) - 1  # hanya dua variabel penunjuk
    while kiri < kanan:
        data[kiri], data[kanan] = data[kanan], data[kiri]
        kiri += 1
        kanan -= 1
    return data, 0

catatan = [21, 19, 23, 20, 18, 22, 19, 20, 21, 24]

baru, ruang_baru = balik_dengan_daftar_baru(catatan)
print(f"daftar baru    : {baru}")
print(f"ruang tambahan : {ruang_baru} elemen")

urutan, ruang_urutan = balik_secara_in_place(catatan)
print(f"in-place       : {urutan}")
print(f"ruang tambahan : {ruang_urutan} elemen")

daftar baru    : [24, 21, 20, 19, 22, 18, 20, 23, 19, 21]
ruang tambahan : 10 elemen
in-place       : [24, 21, 20, 19, 22, 18, 20, 23, 19, 21]
ruang tambahan : 0 elemen

Kedua solusi mengembalikan urutan yang sama, tetapi solusi pertama berutang 10 elemen tambahan untuk daftar sepanjang 10, sedangkan solusi kedua berutang nol. Bila daftar berisi sejuta nilai, selisihnya satu juta sel melawan beberapa variabel penunjuk. Waktu kedua solusi tetap $O(n)$ karena keduanya menyentuh setiap elemen sekali, sehingga selisih di antara keduanya murni soal ruang.

Solusi in-place membawa konsekuensi yang perlu disebut, yaitu masukannya ikut berubah. Bila urutan aslinya masih dibutuhkan setelah pembalikan, salinan tetap harus dibuat dan ruangnya kembali $O(n)$. Soal ujian dan wawancara kerap menguji tepat perbedaan ini, sehingga keputusan in-place tidak boleh diambil tanpa membaca batasan yang diberikan.

Stack rekursi memakan ruang#

Ruang yang sering terlupakan ada di call stack, yaitu tumpukan frame memori yang disiapkan untuk setiap pemanggilan fungsi yang belum selesai. Setiap fungsi rekursif yang memanggil dirinya menumpuk satu frame di atas frame pemanggilnya, dan tumpukan itu baru dibongkar ketika dasar rekursi tercapai. Rekursi berkedalaman $n$ berarti ada sekitar $n$ frame aktif bersamaan, sehingga ruang tambahannya $O(n)$ meskipun fungsinya tidak membuat satu daftar pun.

# Kedalaman stack yang ditimbulkan rekursi berkedalaman n.
# Setiap pemanggilan menambah satu frame di atas frame pemanggilnya.

def hitung_mundur(n, kedalaman=1):
    if n == 0:
        return kedalaman
    return hitung_mundur(n - 1, kedalaman + 1)

for n in (10, 100, 500):
    print(f"n = {n:4} -> kedalaman stack = {hitung_mundur(n):4}")

n =   10 -> kedalaman stack =   11
n =  100 -> kedalaman stack =  101
n =  500 -> kedalaman stack =  501

Kedalaman stack naik satu untuk setiap tambahan elemen masukan, persis pola linear, dengan satu frame ekstra untuk pemanggilan paling awal. Versi perulangan dari fungsi yang sama hanya membawa satu variabel penghitung, sehingga ruang tambahannya $O(1)$. Ketika sebuah solusi rekursif terasa boros memori, konversi ke perulangan adalah salah satu jalan menekan ruangnya tanpa mengubah hasil.

Mengukur memori dengan sys.getsizeof#

Modul sys menyediakan sys.getsizeof(), fungsi yang melaporkan ukuran suatu objek dalam byte. Fungsinya berguna untuk merasakan skala, dengan catatan penting bahwa ia mengukur wadahnya saja. Pada daftar berisi seribu angka, fungsinya tidak melaporkan memori seribu objek angka itu, melainkan hanya struktur daftar yang menampungnya.

import sys

for n in (10, 1000):
    data = list(range(n))
    print(f"n = {n:5} -> sys.getsizeof(data) = {sys.getsizeof(data)} byte")

n =    10 -> sys.getsizeof(data) = 136 byte
n =  1000 -> sys.getsizeof(data) = 8056 byte

Selisihnya sekitar delapan byte per elemen, yaitu ukuran satu slot referensi pada daftar Python, ditambah sejumlah byte tetap untuk kepala daftarnya. Angka 136 dan 8056 byte juga memperlihatkan bahwa wadah daftar punya bagian tetap yang dibayar sejak daftar masih kosong, sehingga perbandingan ukuran hanya bermakna pada $n$ yang besar. Nilai pastinya bergantung pada versi dan arsitektur interpreter, yaitu program yang menjalankan kode Python, sehingga angka byte ini layak dibaca sebagai ordo besaran, bukan sebagai spesifikasi. Untuk analisis kompleksitas, bentuk $O(n)$ pada pertambahan slot itulah yang penting, dan penghitungan buatan sendiri seperti pada demo sebelumnya tetap menjadi alat utama.

Trade-off waktu versus memori#

Waktu dan ruang sering dapat ditukar, dan tabel berikut merangkum beberapa pola yang sudah dikenal, termasuk yang berbantu hash set, yaitu struktur data yang menyimpan nilai unik dan memeriksa keanggotaan dengan cepat. Kolom ruang menghitung ruang tambahan, bukan ukuran masukannya.

Baris kedua membeli kecepatan dengan memori, sedangkan baris keempat menolak membeli apa pun dan menerima waktu yang sama dengan baris kelima. Aturan praktisnya, memori sering menjadi sumber daya yang lebih murah untuk ditambah, sehingga struktur tambahan seperti set dan jumlah prefiks menjadi pilihan bawaan ketika tidak ada batasan memori. Soal ujian dan wawancara biasanya menyebutkan batasnya secara eksplisit, misalnya meminta solusi dengan ruang $O(1)$, dan batas itulah yang menentukan pola mana yang boleh dipakai.

Soal untuk dipraktikkan#

Kaedah penjumlahan, perkalian, dan penggandaan dari modul ini sudah cukup untuk menyelesaikan empat soal analisis berikut. Taksir dulu waktu dan ruang tambahannya di kertas, lalu petakan taksiran itu ke kelas Big-O.

1. Taksir waktu dan ruang tambahan dari fungsi yang menerima daftar sepanjang $n$, menjumlahkan seluruh nilainya, lalu menyusurinya sekali lagi untuk mencari nilai terbesar.
2. Sebuah perulangan menggandakan nilai i dari 1 sampai melewati $n$, dan setiap putaran menyimpan satu elemen ke daftar hasil baru. Taksir waktu dan ruang tambahannya.
3. Fungsi rekursif menghitung panjang linked list, yaitu rangkaian node yang masing-masing menunjuk ke node berikutnya, dengan memanggil dirinya pada node selanjutnya sampai node habis. Bandingkan waktu dan ruangnya dengan versi perulangan, lalu jelaskan dari mana selisih ruangnya berasal.
4. Dua algoritma mencari nilai ganda pada daftar sepanjang $n$, satu membandingkan setiap pasangan dan satu menyalin seluruh isi ke hash set sebelum memeriksa keanggotaan. Taksir waktu dan ruang kedua versi, lalu sebutkan batas masukan yang membuat pilihan berganti.

Soal-soal dengan pola serupa, lengkap dengan pembahasannya, dikumpulkan pada peta jalan NeetCode yang dirujuk di bagian Referensi.

Ringkasan#

• Yang dihitung dalam kompleksitas ruang adalah ruang tambahan di luar masukan, dengan konstanta dan suku rendah dibuang seperti pada waktu.
• Dua solusi untuk masalah yang sama dapat berbeda ruang, seperti daftar baru $O(n)$ melawan penukaran in-place $O(1)$.
• Rekursi berkedalaman $n$ memakai $O(n)$ ruang stack, sedangkan versi perulangannya cukup $O(1)$.
• Waktu dan ruang dapat ditukar, dan batas yang disebutkan pada soal menentukan pola mana yang boleh dipakai.

Referensi#

• sys — Dokumentasi Python — Dokumentasi sys.getsizeof() beserta catatan interpretasi ukurannya.
• NeetCode roadmap — NeetCode — Kumpulan soal latihan DSA yang dikelompokkan per pola, termasuk soal trade-off waktu dan ruang.