DSA Interview Prep · Pelajaran

Kompleksitas Ruang dan Pertukarannya

Ukur ruang tambahan untuk tumpukan pemanggilan dan struktur data tambahan, lalu kenali pertukaran waktu-ruang dalam memoization dan algoritma in-place.

Kompleksitas Ruang dan Pertukarannya adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.

Apa yang Diukur oleh Kompleksitas Ruang?

Kompleksitas ruang mengukur memori tambahan di luar input, yang disebut ruang bantu. Beberapa variabel memerlukan O(1); larik hasil atau peta hash memerlukan O(n). Lihat kodenya.

# O(1) auxiliary space
def sum_array(nums):
    total = 0       # one integer variable
    for n in nums:
        total += n  # constant extra space
    return total

# O(n) auxiliary space
def copy_array(nums):
    return list(nums)  # allocates n slots

print(sum_array([1, 2, 3, 4]))  # 10
print(copy_array([1, 2, 3, 4]))  # [1, 2, 3, 4]

Ruang Tumpukan Pemanggilan dalam Rekursi

Setiap pemanggilan rekursif menambahkan bingkai tumpukan, sehingga kedalaman menentukan ruang yang digunakan. Rekursi linear adalah O(n); DFS pada pohon seimbang adalah O(log n). Versi iteratif dapat mengendalikan hal ini dengan lebih baik.

import sys

def recursive_sum(n):
    if n == 0: return 0
    return n + recursive_sum(n - 1)
# Space: O(n) stack frames

def iterative_sum(n):
    total = 0
    while n > 0:
        total += n
        n -= 1
    return total
# Space: O(1)

print(recursive_sum(100))   # 5050
print(iterative_sum(100))   # 5050

Ruang Pengurutan Gabung: O(n)

Pengurutan gabung memerlukan ruang tambahan O(n) untuk larik sementara. Itulah harga yang dibayar untuk pengurutan stabil O(n log n) — pengurutan heap menghemat ruang, tetapi tidak stabil. Lihat kodenya.

import tracemalloc

tracemalloc.start()

def merge_sort(arr):
    if len(arr) <= 1: return arr
    m = len(arr) // 2
    l = merge_sort(arr[:m])    # new list
    r = merge_sort(arr[m:])    # new list
    out, i, j = [], 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]: out.append(l[i]); i+=1
        else:             out.append(r[j]); j+=1
    return out + l[i:] + r[j:]

data = list(range(1000, 0, -1))
merge_sort(data)
_, peak = tracemalloc.get_traced_memory()
print(f'Peak memory: {peak} bytes')  # proportional to n

Algoritma Langsung di Tempat: Ruang O(1)

Algoritma langsung di tempat mengubah input secara langsung tanpa penyimpanan tambahan yang proporsional — seperti membalik larik dengan dua penunjuk. Dengan demikian, ruang yang digunakan tetap O(1). Lihat kodenya.

def reverse_inplace(arr):
    l, r = 0, len(arr) - 1
    while l < r:
        arr[l], arr[r] = arr[r], arr[l]  # swap
        l += 1
        r -= 1
    # Space: O(1) -- only two pointer variables

def rotate_right(arr, k):
    '''Rotate array right by k positions in-place.'''
    n = len(arr)
    k %= n
    arr.reverse()          # O(1) space
    arr[:k] = arr[:k][::-1]
    arr[k:]  = arr[k:][::-1]

a = [1, 2, 3, 4, 5]
rotate_right(a, 2)
print(a)  # [4, 5, 1, 2, 3]

Pertukaran Waktu-Ruang: Two-Sum

Pertukaran waktu-ruang ada di mana-mana. Two-sum memerlukan waktu O(n^2) dengan ruang O(1), atau waktu O(n) dengan ruang O(n) menggunakan peta hash. Sampaikan keduanya dan tanyakan mana yang lebih penting.

# O(n^2) time, O(1) space
def two_sum_slow(nums, target):
    for i in range(len(nums)):          # O(n)
        for j in range(i+1, len(nums)): # O(n)
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

# O(n) time, O(n) space
def two_sum_fast(nums, target):
    seen = {}                    # O(n) space
    for i, n in enumerate(nums):
        comp = target - n
        if comp in seen:         # O(1) lookup
            return [seen[comp], i]
        seen[n] = i
    return []

print(two_sum_fast([2, 7, 11, 15], 9))  # [0, 1]

Ruang Memoisasi vs Tabulasi

Memoisasi dari atas ke bawah memerlukan O(n) untuk memo dan O(n) untuk tumpukan; tabulasi dari bawah ke atas tidak memerlukan tumpukan. Dengan hanya menyimpan beberapa baris terakhir, ruangnya menyusut menjadi O(1) — DP yang dioptimalkan ruangnya.

# Fibonacci: O(n) space with full table
def fib_table(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# O(1) space: keep only last two values
def fib_optimal(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print(fib_table(10))    # 55
print(fib_optimal(10))  # 55

Ruang Peta Hash: O(n)

Peta hash biasanya menjadi biaya ruang O(n) dalam solusi: himpunan yang telah dilihat untuk pelacakan kunjungan, dan peta frekuensi untuk penghitungan. Selalu laporkan — “waktu O(n), ruang O(n)” adalah jawaban lengkapnya.

def contains_duplicate(nums):
    # O(n) time, O(n) space
    seen = set()
    for n in nums:
        if n in seen: return True
        seen.add(n)
    return False

def group_anagrams(words):
    # O(n*m) time, O(n) space  (m = avg word length)
    from collections import defaultdict
    groups = defaultdict(list)
    for w in words:
        groups[tuple(sorted(w))].append(w)
    return list(groups.values())

print(contains_duplicate([1,2,3,1]))  # True
print(group_anagrams(['eat','tea','tan','ate','nat','bat']))

Analisis Ruang untuk Algoritma Graf

Graf memerlukan ruang nyata: daftar ketetanggaan adalah O(V + E), himpunan visited dan antrean BFS adalah O(V), dan rekursi DFS memiliki kedalaman O(V). Laporkan ruang graf menggunakan V dan E.

from collections import deque

def bfs(graph, start):
    # Space: O(V) for visited set + O(V) for queue
    visited = set()      # O(V)
    queue = deque([start])  # O(V) max
    order = []
    while queue:
        node = queue.popleft()
        if node in visited: continue
        visited.add(node)
        order.append(node)
        for nb in graph.get(node, []):
            queue.append(nb)
    return order

g = {0:[1,2], 1:[3], 2:[3], 3:[]}
print(bfs(g, 0))  # [0, 1, 2, 3]

Jebakan Alokasi String dan Larik

Alokasi tersembunyi dapat menyelipkan penggunaan ruang O(n): pengirisan membuat larik baru, dan + pada string di dalam perulangan memiliki kompleksitas O(n^2). sorted() membuat salinan, tetapi lst.sort() tetap bekerja di tempat. Lihat kodenya.

# Hidden allocations:
nums = [1, 2, 3, 4, 5]

# Creates a NEW list -- O(n) space
slice_copy = nums[1:4]  # [2, 3, 4]

# Creates a NEW sorted list -- O(n) space
sorted_copy = sorted(nums)  # nums unchanged

# Sorts IN PLACE -- O(1) extra space
nums.sort()

print(slice_copy)   # [2, 3, 4]
print(sorted_copy)  # [1, 2, 3, 4, 5]
print(nums)         # [1, 2, 3, 4, 5]

Mengenali Pertukaran Ruang dalam Wawancara

Sampaikan kompleksitas ruang Anda sejak awal. Jika pewawancara menginginkan penggunaan ruang yang lebih kecil, langkah yang umum adalah DP dari bawah ke atas sebagai pengganti memo, atau pengurutan di tempat sebagai pengganti peta hash. Lihat kodenya.

# Problem: find if array has duplicates
# Option 1: O(1) time-per-check, O(n) space
def has_dup_hash(nums):
    return len(nums) != len(set(nums))

# Option 2: O(n log n) time, O(1) extra space
def has_dup_sort(nums):
    nums_copy = sorted(nums)  # O(n) space -- still!
    for i in range(1, len(nums_copy)):
        if nums_copy[i] == nums_copy[i-1]:
            return True
    return False

# Option 3: truly O(1) extra -- sort in-place
def has_dup_inplace(nums):
    nums.sort()               # modifies original
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]: return True
    return False

Templat Pernyataan Kompleksitas Total

Selalu berikan pernyataan yang lengkap — waktu dan ruang: “waktu O(n), ruang tambahan O(1).” Sebutkan pertukaran jika ada. Itulah yang membedakan kandidat berpengalaman.

# Complete complexity example: Merge Intervals
def merge_intervals(intervals):
    # Time: O(n log n) for sort + O(n) for merge = O(n log n)
    # Space: O(n) for output (could be n/2 to n intervals)
    intervals.sort(key=lambda x: x[0])  # O(n log n)
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]

Pemeriksaan Singkat

Pemeriksaan singkat — mari lihat seberapa baik gagasan tentang kompleksitas ruang telah Anda pahami. Anda siap mengerjakannya. ✅

Rangkuman Pelajaran

Rangkuman: ruang bantu dihitung terpisah dari input, rekursi menggunakan ruang tumpukan O(kedalaman), dan pertukaran waktu-ruang mendorong sebagian besar pilihan dalam desain algoritma.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Kompleksitas Ruang dan Pertukarannya” gratis?

Ya — teks lengkap “Kompleksitas Ruang dan Pertukarannya” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Kompleksitas Ruang dan Pertukarannya”?

Ukur ruang tambahan untuk tumpukan pemanggilan dan struktur data tambahan, lalu kenali pertukaran waktu-ruang dalam memoization dan algoritma in-place. Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?

Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.

Berapa lama pelajaran “Kompleksitas Ruang dan Pertukarannya” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?

Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

← Kembali ke DSA Interview Prep