Platzkomplexität und Abwägungen
Messen Sie den zusätzlichen Speicher für Aufrufstapel und zusätzliche Datenstrukturen und erkennen Sie Zeit-Speicher-Abwägungen bei Memoisation und In-Place-Algorithmen.
Platzkomplexität und Abwägungen ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was misst die Speicherkomplexität?
Die Speicherkomplexität misst den zusätzlichen Speicher über die Eingabe hinaus, den sogenannten Hilfsspeicher. Einige wenige Variablen benötigen O(1); ein Ergebnis-Array oder eine Hash-Map benötigt O(n). Sehen Sie sich den Code an.
# 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]Speicher des Aufruf-Stacks bei Rekursion
Jeder rekursive Aufruf fügt einen Stack-Frame hinzu, daher bestimmt die Tiefe den Speicherbedarf. Lineare Rekursion benötigt O(n); die Tiefensuche in einem balancierten Baum O(log n). Eine iterative Variante lässt sich besser kontrollieren.
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)) # 5050Speicherbedarf von Merge Sort: O(n)
Merge Sort benötigt O(n) zusätzlichen Speicher für seine temporären Arrays. Das ist der Preis für ein stabiles Sortierverfahren mit O(n log n) — Heap Sort spart Speicher, ist aber nicht stabil. Sehen Sie sich den Code an.
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-Algorithmen: O(1) Speicher
Ein in-place-Algorithmus verändert die Eingabe direkt, ohne zusätzlichen Speicher proportional zur Eingabe zu benötigen — etwa beim Umkehren eines Arrays mit zwei Zeigern. Dadurch bleibt der Speicherbedarf bei O(1). Sehen Sie sich den Code an.
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]Zeit-Speicher-Abwägung: Two Sum
Die Zeit-Speicher-Abwägung begegnet Ihnen überall. Two Sum benötigt mit O(1) Speicher O(n^2) Zeit oder mit einer Hash-Map O(n) Zeit und O(n) Speicher. Nennen Sie beide Varianten und fragen Sie, was wichtiger ist.
# 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]Speicher bei Memoization und Tabulation
Top-down-Memoization benötigt O(n) für die Memoization und O(n) für den Stack; Bottom-up-Tabulation kommt ohne den Stack aus. Wenn Sie nur die letzten Zeilen behalten, sinkt der Speicherbedarf auf O(1) — speicheroptimierte dynamische Programmierung.
# 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)) # 55Speicherbedarf einer Hash-Map: O(n)
Eine Hash-Map ist bei Lösungen häufig der Grund für einen Speicherbedarf von O(n): eine Menge bereits besuchter Elemente oder eine Häufigkeits-Map zum Zählen. Geben Sie ihn immer an — „Zeit O(n), Speicher O(n)“ ist die vollständige Antwort.
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']))Speicheranalyse für Graphalgorithmen
Graphen benötigen tatsächlich Speicher: Eine Adjazenzliste benötigt O(V + E), eine bei BFS verwendete Menge besuchter Knoten und die Warteschlange benötigen O(V), und die Rekursion bei DFS kann O(V) tief werden. Geben Sie den Speicherbedarf von Graphen in V und E an.
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]Fallstricke bei der String- und Array-Speicherbelegung
Versteckte Speicherbelegungen können O(n) Speicher verursachen: Slicing erstellt eine neue Liste, und + bei Strings in einer Schleife ist O(n^2). sorted() erstellt eine Kopie, aber lst.sort() arbeitet weiterhin In-Place. Sehen Sie sich den Code an.
# 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]Speicher-Abwägungen in Interviews erkennen
Nennen Sie Ihre Speicherkomplexität gleich zu Beginn. Wenn der Interviewer weniger Speicher wünscht, sind häufige Ansätze Bottom-up-DP statt Memoization oder ein In-Place-Sortierverfahren statt einer Hash-Map. Sehen Sie sich den Code an.
# 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 FalseVorlage für eine vollständige Komplexitätsangabe
Geben Sie immer die vollständige Angabe an — Zeit und Speicher: „Zeit O(n), zusätzlicher Speicher O(1).“ Erwähnen Sie vorhandene Abwägungen. Das unterscheidet erfahrene Kandidaten von anderen.
# 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]]Schnelltest
Schnelltest — sehen wir, wie gut die Ideen zur Speicherkomplexität angekommen sind. Sie sind bereit dafür. ✅
Zusammenfassung der Lektion
Zusammenfassung: Hilfsspeicher wird unabhängig von der Eingabe gezählt, Rekursion verwendet O(depth) Stack-Speicher, und die Zeit-Speicher-Abwägung bestimmt die meisten Entscheidungen beim Entwurf von Algorithmen.
Häufig gestellte Fragen
Ist die Lektion „Platzkomplexität und Abwägungen“ kostenlos?
Ja — der vollständige Text von „Platzkomplexität und Abwägungen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Platzkomplexität und Abwägungen“?
Messen Sie den zusätzlichen Speicher für Aufrufstapel und zusätzliche Datenstrukturen und erkennen Sie Zeit-Speicher-Abwägungen bei Memoisation und In-Place-Algorithmen. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „Platzkomplexität und Abwägungen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Big-O-Notation von Grund auf
- Schleifen und verschachtelte Schleifen analysieren
- Rekursion und die Rekursionsbaum-Methode
- Platzkomplexität und Abwägungen