Kompleksitas Ruang: Cara Algoritme Menggunakan Memori

Kompleksitas ruang mengukur penggunaan memori algoritme seiring pertumbuhan ukuran masukan. Ini membuat pemahaman kompleksitas ruang penting untuk pengelolaan sumber daya di lingkungan yang terbatas.

Dalam artikel ini, saya akan menjelaskan secara rinci apa itu kompleksitas ruang, cara menghitungnya, dan cara meminimalkannya. Selain itu, saya akan membahas penerapan di dunia nyata dan landasan teoretisnya.

Memahami Kompleksitas Ruang

Sebelum masuk ke perhitungan dan optimasi, mari kita perjelas apa sebenarnya makna kompleksitas ruang dan mengapa Anda perlu memedulikannya.

Apa itu kompleksitas ruang?

Kompleksitas ruang adalah total memori yang dibutuhkan oleh algoritme relatif terhadap ukuran masukan. Ini relevan untuk menganalisis jejak memori terburuk demi skala sistem, dan total ruang mencakup input, memori bantu, serta overhead, sementara ruang bantu adalah memori ekstra di luar input dan output. Ambil contoh pengurutan sebuah array: total ruang mencakup array itu sendiri, sedangkan ruang bantu mungkin berupa ruang sementara pada merge sort.

Mengapa kompleksitas ruang penting

Dalam komputasi modern, efisiensi ruang sering kali krusial. Dengan mengoptimalkan kompleksitas ruang, Anda memastikan algoritme dapat berjalan pada perangkat dengan RAM terbatas, seperti sistem tertanam di IoT atau ponsel pintar, atau bahkan sistem besar dengan prosedur yang menuntut sumber daya di mana setiap bit RAM berarti.

Ambil contoh aplikasi seluler: mengoptimalkan kompleksitas ruang membantu menghindari crash saat melakukan pemrosesan gambar. Atau pikirkan penghematan biaya penyimpanan di komputasi awan, atau data streaming, dan mendapatkan analitik waktu nyata tanpa memuat seluruh data.

Analisis Asimtotik dan Notasi Big O untuk Ruang

Di bagian ini, saya akan menjelaskan bagaimana notasi asimtotik seperti Big O menggambarkan pertumbuhan ruang, serta memberikan alat untuk membatasi dan membandingkan penggunaan memori.

Pengantar notasi Big O

Secara matematis, sebuah fungsi f(n) didominasi oleh fungsi g(n) jika terdapat konstanta c dan k, sedemikian sehingga untuk semua k>n, 0 ≤ |f(n)| ≤ |g(n)|.

Dalam hal ini, kita tulis f(n)=O(g(n)), dan kita katakan f(n) adalah big O dari g(n).

Secara lebih sederhana, ini berarti f(n) tidak tumbuh lebih cepat daripada g(n) mulai dari indeks tertentu.

Notasi Big O merepresentasikan batas atas ruang sebagai fungsi dari ukuran masukan n, sehingga kita dapat fokus pada suku dominan untuk n yang besar. Notasi ini membantu mengklasifikasikan algoritme; misalnya, O(n) berarti ruang berlipat dua saat masukan berlipat dua.

Ada kesalahpahaman umum di kalangan pemula bahwa Big O untuk ruang mengabaikan konstanta seperti 2n adalah O(n), tetapi dalam praktiknya, konstanta penting untuk n kecil.

Notasi asimtotik terkait

Ada berbagai cara memodelkan kompleksitas dan notasi yang berbeda. Misalnya, Big Omega memberikan batas bawah yang berguna untuk membuktikan kebutuhan ruang minimal, seperti pengurutan memerlukan setidaknya Ω(n). Notasi lain adalah Big Theta, yang memberikan batas ketat ketika batas atas dan bawah cocok, sehingga ideal untuk analisis presisi, seperti O(n) = Θ(n) untuk ruang linear.

Konvensi notasi lainnya

Ada beberapa konvensi notasi lain yang relevan dengan literatur kompleksitas ruang, seperti notasi Soft-O Õ, yang mengabaikan faktor polilog. Ini lazim dalam algoritme tingkat lanjut seperti pemrosesan graf, di mana logaritma dapat diabaikan. Ia muncul dalam makalah teoretis untuk kompleksitas perkiraan seperti Õ untuk ruang sublinear pada algoritme streaming.

Komponen Kompleksitas Ruang

Kompleksitas ruang memiliki banyak kontributor dan titik optimasi dalam perancangan algoritme. Mari kita lihat:

Kebutuhan ruang untuk input

Data masukan menempati ruang yang proporsional dengan ukurannya, misalnya O(n) untuk sebuah array atau saat menganalisis dataset besar seperti sekuens genom.

Umumnya dalam wawancara pemrograman dunia nyata, ruang input dikecualikan saat menghitung ruang bantu dan hanya fokus pada memori ekstra yang digunakan algoritme. Namun, dalam pemrograman kompetitif, total ruang biasanya termasuk input.

Ruang bantu dan memori sementara

Ruang bantu adalah memori ekstra yang dibutuhkan algoritme untuk menjalankan operasinya. Ini langsung memengaruhi bagaimana algoritme dirancang.

Karenanya, Anda dapat, misalnya, menggunakan O(n) untuk array sementara pada algoritme merge sort. Contoh lain adalah tabel hash untuk deteksi duplikat (O(n)), tumpukan rekursi untuk pencocokan tanda kurung (O(n)), dan banyak lainnya.

Contoh klasik ruang bantu mencakup metode dua-pointer (O(1)), algoritme sliding-window yang menggunakan deque (O(k)), dan BFS, yang memerlukan ruang O(V) untuk himpunan visited dan antreannya.

Kode berikut menunjukkan contoh operasi merge sort pada array sementara selama langkah penggabungan:

def merge(left_half, right_half):
    merged = [0] * (len(left_half) + len(right_half))  # O(n) auxiliary space
    left_idx = right_idx = merged_idx = 0
    # merging logic...Didukung oleh

Call stack dan ruang rekursi

Setiap pemanggilan rekursif menambahkan sebuah frame stack (alamat kembali + parameter + variabel lokal).

Di sisi lain, rekursi linear, seperti faktorial atau DFS pada linked list, memiliki stack O(n).

Rekursi biner, seperti Fibonacci naif atau rekursi pohon, memiliki O(n) pada skenario terburuk.

Optimasi tail-call, yang didukung di Scheme, Rust, dan kadang-kadang Python dengan decorator, mengurangi menjadi O(1). Namun, bahaya nyata di sini ada pada batas rekursi bawaan Python, sekitar 1000, yang akan menyebabkan stack overflow pada pohon yang dalam.

Berikut contoh Fibonacci rekursif naif yang menunjukkan pertumbuhan stack:

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)  # O(n) stack depthDidukung oleh

Lihat blog kami tentang Menganalisis Kompleksitas Kode melalui Python untuk mempelajari lebih lanjut tentang analisis kompleksitas di Python.

Overhead struktur data

Hal baik tentang overhead struktur data adalah kesederhanaannya, karena semua struktur menambah biaya tetap/per elemen, misalnya overhead minimal pada array, pointer pada linked list menggandakan ruang, dan banyak contoh lainnya. 

Bagaimanapun, bahasa pemrograman memiliki pengaruh besar. List Python memiliki overhead dinamis, tidak seperti array C—misalnya, hash map dengan load factor 75% membuang ruang pada bucket kosong.

Jenis-Jenis Kompleksitas Ruang

Kompleksitas ruang konstan: O(1)

Kompleksitas ruang konstan adalah solusi fundamental dan optimal jika dapat ditemukan. Banyak algoritme yang dikenal benar-benar memiliki kompleksitas konstan, seperti pertukaran variabel sederhana seperti contoh di bawah ini, yaitu swap in-place sederhana menggunakan tuple unpacking Python:

def swap_numbers(first, second):
    first, second = second, first  # O(1) — only two variables
    return first, secondDidukung oleh

Algoritme kompleksitas konstan lainnya yang dikenal adalah partisi bendera Belanda pada quicksort dan traversal Morris untuk pohon. Namun, ada batas praktis ketika Anda memiliki beberapa lusin variabel sebelum efektif, karena bergantung pada perangkat keras sistem, untuk skenario terburuk, O(1) terkadang tidak cukup jika memori yang dibutuhkan melebihi sumber daya sistem.

Kompleksitas ruang linear: O(n)

Kompleksitas ruang linear didefinisikan sederhana sebagai proporsional terhadap masukan. Beberapa contoh adalah array ekstra untuk penyalinan atau himpunan hash untuk nilai unik. Penggunaan paling umum terdapat pada pola pemrosesan data, seperti memfilter daftar.

Kompleksitas ruang logaritmik dan sublinear

Kompleksitas ruang logaritmik menandakan bahwa jumlah memori yang digunakan algoritme bertambah sangat lambat seiring bertambahnya ukuran masukan. Secara khusus, ia sebanding dengan logaritma ukuran masukan.

Sebagai contoh, rekursi pencarian biner memiliki kedalaman stack O(log(n)), sebagaimana divide-and-conquer dengan tail recursion atau algoritme streaming, yang memperkirakan hasil dalam ruang O(log(n)) atau O(sqrt(n)).

Kompleksitas ruang logaritmik dan sublinear jarang, tetapi sangat kuat untuk dataset masif. Anda dapat melihat contoh kompleksitas logaritmik dengan pencarian biner iteratif (ruang konstan) seperti ditunjukkan kode contoh berikut:

def binary_search(numbers, target):
    left = 0
    right = len(numbers) - 1
    while left <= right:                 # O(1) space total
        mid = (left + right) // 2
        # comparison logic...Didukung oleh

Kompleksitas ruang kuadratik: O(n²)

Kompleksitas ruang kuadratik terjadi ketika kebutuhan memori berskala dengan kuadrat masukan. Contoh umum adalah tabel pemrograman dinamis 2D, yang memiliki kompleksitas O(n²) atau matriks ketetanggaan untuk graf dengan kompleksitas O(V²). Namun, penting untuk dicatat bahwa kompleksitas ini menjadi tidak praktis di atas ribuan elemen masukan.

Kompleksitas ruang eksponensial dan faktorial

Kompleksitas eksponensial, sebagaimana namanya, membuat kebutuhan memori bertumbuh sebanding dengan pemangkatan ukuran masukan O(2^n), dan ini terjadi ketika, misalnya, Anda menyimpan semua subset atau jalur pohon keputusan.

Demikian pula, pada kompleksitas faktorial, memori yang dibutuhkan sebanding dengan faktorial ukuran masukan O(n!), dan ini terjadi ketika Anda mengenumerasi semua permutasi dari masukan. Namun, kompleksitas ini umumnya sangat mahal, dan hampir pasti tidak layak untuk n>20-30 di sebagian besar sistem. Jika Anda mengerjakan ini, Anda mungkin benar-benar membutuhkan pemangkasan, pendekatan perkiraan, atau pendekatan yang berbeda.

Cara Menghitung Kompleksitas Ruang

Analisis sistematis mengidentifikasi semua alokasi memori dan pola pertumbuhannya:

Pendekatan analisis baris demi baris

Langkah pertama adalah memeriksa kode Anda baris demi baris dan mengidentifikasi setiap variabel, array, dan alokasi objek. Langkah berikutnya adalah menentukan apakah ukuran setiap alokasi bergantung pada parameter masukan. Lalu, jumlahkan memori untuk alokasi yang independen dan ambil nilai maksimum untuk cabang yang saling eksklusif. Terakhir, lacak alokasi stack untuk variabel lokal dan alokasi heap untuk memori dinamis. Berikut contohnya:

def linear_search(arr, target):
    n = len(arr)           # O(1) - single integer
    for i in range(n):     # O(1) - loop variable
        if arr[i] == target:
            return i
    return -1
# Total: O(1) auxiliary spaceDidukung oleh

Analisis kompleksitas rekursif

Kompleksitas ruang untuk rekursi sama dengan kedalaman rekursi maksimum dikalikan ruang per frame panggilan, lalu tambahkan struktur data bantu apa pun yang dialokasikan selama rekursi, identifikasi kasus dasar, dan analisis bagaimana kedalaman rekursi terkait dengan ukuran masukan; misalnya, Fibonacci naif membuat kedalaman O(n) dengan O(1) per frame, yang totalnya O(n) ruang stack. Berikut contoh perhitungan ruang untuk faktorial:

def factorial(n):
    if n <= 1:             # Base case
        return 1
    return n * factorial(n - 1)
# Space: O(n)Didukung oleh

Analisis kompleksitas pemrograman dinamis

Tabel DP standar memiliki dimensi yang sesuai dengan parameter submasalah; oleh karena itu, masalah satu dimensi memerlukan ruang O(n), dan masalah dua dimensi memerlukan O(nxm). Teknik optimasi seperti rolling array mengurangi satu dimensi untuk mengubah, misalnya, O(n²) menjadi O(n). Kompresi state memanfaatkan ketergantungan, jadi jika baris i hanya membutuhkan i-1, cukup simpan dua baris. Berikut contoh Fibonacci yang dioptimalkan ruang menggunakan hanya dua variabel:

def fibonacci_optimized(n):
    previous = 0
    current = 1
    for _ in range(2, n + 1):            # O(1) space
        previous, current = current, previous + current
    return currentDidukung oleh

Jika Anda penasaran tentang dimensionalitas dan reduksinya, saya mendorong Anda untuk melihat tutorial kami tentang Menguasai Slowly Changing Dimensions (SCD) dan Memahami Kardinalitas: Tantangan dan Solusi untuk Alur Kerja Data-Intensif.

Langkah-langkah menghitung kompleksitas ruang dalam praktik

Untuk menghitung kompleksitas ruang dalam praktik, ikuti langkah-langkah berikut:

1. Perjelas apakah ruang input disertakan berdasarkan konteks
2. Hitung variabel dan konstanta berukuran tetap. Mereka berkontribusi O(1)
3. Ukur struktur bantu seperti array dan hash map relatif terhadap ukuran masukan
4. Hitung kedalaman rekursi maksimum untuk kontribusi ruang stack
5. Gabungkan seluruh komponen dan nyatakan menggunakan batas asimtotik yang paling ketat.

Kompleksitas Ruang Algoritme Umum

Kebutuhan ruang algoritme pengurutan

Algoritme merge sort memerlukan ruang bantu O(n) untuk array sementara selama penggabungan. Di sisi lain, Quicksort hanya menggunakan ruang stack rata-rata O(log n), tetapi O(n) pada kasus terburuk tanpa optimasi. Sementara heap sort mencapai ruang bantu O(1) dengan mengurutkan in-place seperti yang ditunjukkan kode berikut:

def heapify(array, heap_size, root_index):
    largest = root_index
    left_child = 2 * root_index + 1
    right_child = 2 * root_index + 2
    # comparison & swap logic...       # O(1) auxiliary spaceDidukung oleh

Terakhir, counting sort membutuhkan ruang O(k), di mana k adalah rentang nilai, tetapi menjadi tidak praktis saat k>>n.

Kompleksitas ruang algoritme graf

Penelusuran graf memiliki banyak algoritme. Misalnya, breadth-first search (BFS) mempertahankan antrean yang membutuhkan ruang O(V) untuk simpul, sementara depth-first search (DFS) menggunakan ruang stack O(V) pada kasus terburuk untuk kedalaman maksimum. Di sisi lain, algoritme Dijkstra membutuhkan O(V) untuk priority queue dan pelacakan jarak untuk setiap simpul. Representasi graf berpengaruh karena matriks ketetanggaan menggunakan O(V²) sementara daftar ketetanggaan menggunakan O(V+E). 

Karakteristik ruang struktur data

Ada berbagai struktur data dan masing-masing memerlukan alokasi memori yang berbeda. Misalnya, Array dan ArrayList menyimpan n elemen dalam memori kontigu O(n), linked list memerlukan ruang O(n) plus overhead pointer untuk setiap simpul, pohon biner menggunakan ruang O(n) dengan 2–3 pointer per simpul yang menambah overhead signifikan, tabel hash mengonsumsi ruang O(n) dikalikan load factor yang biasanya bervariasi antara 1,5 hingga 3 kali, dan daftar ketetanggaan memberikan efisiensi ruang O(V+E) untuk graf jarang.

Contoh perhitungan kompleksitas ruang

Berikut contoh-contoh perhitungan kompleksitas ruang

# O(1): Pembalikan string in-place
left = 0
right = len(text) - 1
while left < right:
    text[left], text[right] = text[right], text[left]  # O(1)
    left += 1
    right -= 1

# O(n): Deteksi duplikat menggunakan hash set
seen_numbers = set()                                      # O(n)
for num in array:
    if num in seen_numbers:
        return True
    seen_numbers.add(num)

# O(log n): Tinggi pohon biner rekursif
def tree_height(root):
    if not root:
        return 0
    return 1 + max(tree_height(root.left), tree_height(root.right))  # O(log n) stack

# O(n²): Matriks jarak Floyd-Warshall
distance = [[float('inf')] * vertices for _ in range(vertices)]  # O(n²)
for i in range(vertices):
    distance[i][i] = 0Didukung oleh

Kompleksitas Ruang vs. Kompleksitas Waktu

Waktu dan ruang mewakili dimensi sumber daya yang berbeda yang harus diseimbangkan berdasarkan batasan sistem:

Perbedaan dan kesamaan kunci

Sekilas, kompleksitas ruang dan waktu mungkin tampak serupa, tetapi juga berbeda karena kompleksitas waktu mengukur operasi komputasi, sementara kompleksitas ruang mengukur konsumsi memori. Meskipun keduanya menggunakan notasi asimtotik dan kerangka analisis matematis yang identik, Anda perlu tahu bahwa algoritme dapat optimal pada satu dimensi namun tidak efisien pada dimensi lain. Optimasi sering kali melibatkan pertukaran ruang yang meningkat untuk mengurangi waktu atau sebaliknya.

Memahami trade-off fundamental

Saat Anda menukar ruang untuk waktu, Anda menyimpan hasil prahitung yang menghilangkan perhitungan berulang. Sebaliknya, menukar waktu untuk ruang memerlukan perhitungan ulang nilai sesuai permintaan alih-alih menyimpannya. Tabel lookup menukar investasi ruang satu kali untuk akses O(1) berulang. Dapat ada batasan khusus seperti batas memori dan kebutuhan kinerja yang menentukan sumber daya mana yang diprioritaskan dibanding yang lain.

Memoisasi dan optimasi pemrograman dinamis

Memoisasi bekerja dengan menyimpan nilai alih-alih menghitung ulang; ini efisien dalam waktu tetapi buruk untuk ruang. Ia menambahkan, misalnya, cache O(n) ke Fibonacci rekursif, namun mengurangi waktu dari O(2^n) menjadi O(n), seperti contoh di bawah pada Fibonacci dengan memoisasi, menghindari perhitungan ulang:

memory = {}
def fibonacci_memory(n):
    if n in memo:
        return memory[n] # O(n) space, O(n) time
    if n <= 1:
        return n
    memory[n] = fibonacci_memory(n-1) + fibonacci_memory(n-2)
    return memory[n]Didukung oleh

Pemrograman dinamis bottom-up, di sisi lain, menghitung secara iteratif untuk menghilangkan overhead stack rekursi. Untuk mengoptimalkan ruang, Anda sebaiknya hanya mempertahankan state sebelumnya yang dibutuhkan untuk perhitungan saat ini; misalnya, jarak edit dapat dikurangi dari tabel O(nxm) menjadi O(min(n,m)) dengan menyimpan satu baris.

Teknik algoritme in-place

Algoritme in-place memodifikasi input secara langsung alih-alih mengalokasikan struktur memori baru, yang, jika diiterasi, sangat membantu dalam alokasi memori, dan dengan demikian menurunkan kompleksitas ruang, seperti contoh di bawah pada rotasi array in-place (Algoritme Reversal):

def rotate_array(nums, k):
    n = len(nums)
    k = k % n
    reverse(nums, 0, k - 1)  # all operations O(1) auxiliary
    reverse(nums, k, n - 1)
    reverse(nums, 0, n - 1)Didukung oleh

Teknik in-place lainnya secara dramatis mengurangi penggunaan memori. Misalnya, teknik dua-pointer memanipulasi array dengan ruang bantu O(1), dan cyclic sort menangani masalah permutasi dalam ruang O(1) dengan menukar elemen ke posisi yang benar. Namun, perlu dicatat bahwa modifikasi in-place dapat merusak data input, memengaruhi kegunaan ulang dan kejelasan kode.

Pemilihan struktur data untuk efisiensi ruang

Ada banyak struktur data berbeda, masing-masing menawarkan trade-off yang berbeda; oleh karena itu, misalnya, Anda sebaiknya memprioritaskan array dibanding linked list ketika ukurannya diketahui, menghilangkan overhead pointer per elemen, dan memanipulasi bit untuk menyimpan flag boolean dengan kompresi 8 kali dibanding array byte. Trie membagikan prefiks umum untuk memberikan efisiensi ruang bagi koleksi string besar. Untuk graf jarang, pilih daftar ketetanggaan dibanding matriks untuk mendapatkan O(V+E) alih-alih O(V²) ruang.

Pertimbangan Praktis dan Realitas Implementasi

Kompleksitas ruang di dunia nyata bergantung pada bahasa pemrograman, arsitektur perangkat keras, dan lingkungan runtime.

Faktor bahasa dan lingkungan runtime

Bahasa tingkat tinggi seperti Python dan Java menambahkan metadata dan overhead per objek, tidak seperti C dan C++ yang menyediakan manajemen memori manual untuk kontrol presisi dengan biaya kompleksitas. Itulah mungkin alasan kerangka optimasi machine learning seperti PyTorch menggunakan C++ untuk komputasi.

Batas ukuran stack biasanya berkisar dari 1 hingga 8MB, yang membatasi kedalaman rekursi maksimum. Perhatikan bahwa sistem 64-bit menggunakan pointer 8-byte sedangkan 32-bit menggunakan 4-byte, yang menggandakan ukuran struktur pointer. Untuk mempelajari lebih lanjut tentang bagaimana data berdimensi tinggi memengaruhi kinerja algoritme, lihat tutorial kami: Kutukan Dimensionalitas dalam Machine Learning.

Hirarki memori dan efek cache

Penggunaan ruang algoritme dan kinerja sangat bergantung pada hirarki memori. Akses RAM memakan waktu sekitar 100 nanodetik dan akses cache CPU memakan 1 hingga 10 nanodetik, yang 100 kali lebih cepat. Selain itu, akses memori berurutan memanfaatkan cache line di mana biasanya 64 byte dimuat bersamaan.

Algoritme dengan localitas spasial yang baik mencapai kinerja lebih baik melalui efisiensi cache. Jadi, saat bekerja pada himpunan besar yang melampaui kapasitas, hal itu menyebabkan thrashing, yang sangat menurunkan kinerja.

Garbage collection dan manajemen memori

Salah satu alat yang membantu untuk manajemen memori adalah garbage collection, yang memungkinkan Anda membersihkan data yang tidak lagi berguna. Dengan kata lain, garbage collector menambahkan overhead memori untuk pelacakan objek dan manajemen generasi.

Puncak penggunaan memori melampaui ukuran data hidup karena alokasi yang dibuat sebelum siklus koleksi. Selain itu, GC generasional mengoptimalkan untuk objek berumur pendek dengan menjaga generasi muda di ruang yang lebih kecil. Namun, jika Anda menginginkan kontrol ruang yang lebih deterministik, Anda dapat menggunakan manajemen memori manual, tetapi Anda harus menyadari risikonya, seperti memory leak dan fragmentasi.

Kesimpulan dan Rekomendasi

Terima kasih telah membaca artikel saya tentang kompleksitas ruang. Saya tinggalkan beberapa tips terakhir:

• Selalu perjelas apakah analisis ruang mencakup ukuran input untuk mencegah miskomunikasi dalam wawancara dan ulasan kode.
• Prioritaskan kebenaran terlebih dahulu, lalu optimalkan ruang hanya ketika profiling mengungkapkan bottleneck nyata.
• Usahakan mempertimbangkan batasan perangkat keras dan memori sejak dini dalam desain sistem untuk menghindari refactoring yang mahal.
• Selalu pilih alat profiling yang sesuai dengan bahasa untuk memvalidasi analisis teoretis terhadap perilaku aktual dan menyeimbangkan optimasi ruang dengan keterbacaan kode. Optimasi yang terlalu cerdik dapat merugikan keberlanjutan juga.