Ruimtecomplexiteit en afwegingen
Meet de hulpruimte voor call stacks en aanvullende datastructuren en herken tijd-ruimteafwegingen bij memoisation en in-place-algoritmen.
Ruimtecomplexiteit en afwegingen is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 4 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat meet ruimtecomplexiteit?
Ruimtecomplexiteit meet het extra geheugen naast de invoer, ook wel hulpgeheugen genoemd. Enkele variabelen zijn O(1); een resultatenarray of hashmap is O(n). Bekijk de code.
# 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]Ruimte van de aanroepstack bij recursie
Elke recursieve aanroep voegt een stackframe toe, dus de diepte bepaalt de benodigde ruimte. Lineaire recursie is O(n); DFS op een gebalanceerde boom is O(log n). Met een iteratieve versie kun je dit beter beheersen.
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)) # 5050Ruimte van mergesort: O(n)
Mergesort heeft O(n) extra ruimte nodig voor tijdelijke arrays. Dat is de prijs van een stabiele sortering van O(n log n) — heapsort bespaart ruimte, maar is niet stabiel. Bekijk de code.
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 nIn-place-algoritmen: O(1) ruimte
Een in-place-algoritme wijzigt de invoer rechtstreeks zonder extra opslag die evenredig met de invoer groeit — bijvoorbeeld door een array met twee pointers om te keren. Daardoor blijft de ruimte O(1). Bekijk de code.
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]Tijd-ruimteafweging: Two-Sum
De tijd-ruimteafweging komt overal voor. Two-Sum kost O(n^2) tijd en O(1) ruimte, of O(n) tijd en O(n) ruimte met een hashmap. Noem beide opties en vraag wat belangrijker is.
# 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]Ruimtegebruik van memoization versus tabulatie
Top-down memoization kost O(n) voor de memo en O(n) voor de stack; bottom-up tabulatie gebruikt geen stack. Door alleen de laatste paar rijen te bewaren, verklein je dit tot O(1) — ruimtegeoptimaliseerde dynamische programmering.
# 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)) # 55Ruimte van een hashmap: O(n)
Een hashmap is de gebruikelijke ruimteprijs van O(n) in oplossingen: een verzameling bezochte elementen om bezochte elementen bij te houden en een frequentietabel om te tellen. Vermeld dit altijd — "O(n) tijd, O(n) ruimte" is het volledige antwoord.
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']))Ruimteanalyse voor graafalgoritmen
Grafen kosten echte ruimte: een adjacentielijst is O(V + E), een verzameling bezochte knopen en een wachtrij voor BFS zijn O(V), en recursie bij DFS kan O(V) diep worden. Druk de ruimte voor grafen uit in V en 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]Valkuilen bij toewijzing van strings en arrays
Verborgen toewijzingen kunnen O(n) ruimte veroorzaken: slicing maakt een nieuwe lijst en + op strings in een lus is O(n^2). sorted() maakt een kopie, maar lst.sort() blijft in-place. Bekijk de code.
# 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]Ruimteafwegingen herkennen in sollicitatiegesprekken
Noem je ruimtecomplexiteit meteen. Als de interviewer minder ruimte wil gebruiken, zijn veelvoorkomende opties bottom-up dynamische programmering in plaats van memoization, of een sortering in-place in plaats van een hashmap. Bekijk de code.
# 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 FalseSjabloon voor een volledige complexiteitsuitspraak
Geef altijd de volledige uitspraak — tijd en ruimte: "O(n) tijd, O(1) extra ruimte." Noem bestaande afwegingen. Dat onderscheidt ervaren kandidaten van de rest.
# 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]]Korte controle
Korte controle — kijk hoe goed de ideeën over ruimtecomplexiteit zijn aangekomen. Je bent hier klaar voor. ✅
Samenvatting van de les
Samenvatting: hulpgeheugen wordt los van de invoer geteld, recursie gebruikt O(depth) stackruimte en de tijd-ruimteafweging bepaalt de meeste keuzes bij het ontwerpen van algoritmen.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Ruimtecomplexiteit en afwegingen” gratis?
Ja — de volledige tekst van “Ruimtecomplexiteit en afwegingen” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Ruimtecomplexiteit en afwegingen”?
Meet de hulpruimte voor call stacks en aanvullende datastructuren en herken tijd-ruimteafwegingen bij memoisation en in-place-algoritmen. Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Ruimtecomplexiteit en afwegingen”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Big-O-notatie vanaf de basis
- Lussen en geneste lussen analyseren
- Recursie en de recursieboom-methode
- Ruimtecomplexiteit en afwegingen