空间复杂度与权衡
衡量调用栈和辅助数据结构占用的辅助空间，并认识记忆化与原地算法中的时间—空间权衡。
空间复杂度与权衡 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
空间复杂度衡量什么
空间复杂度衡量输入之外的额外内存，也称为辅助空间。几个变量是 O(1)；结果数组或哈希表是 O(n)。请查看代码。
# 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]递归中的调用栈空间
每次递归调用都会添加一个栈帧，因此空间复杂度由递归深度决定。线性递归是 O(n)；平衡树的 DFS 是 O(log n)。迭代版本可以更好地控制空间。
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归并排序的空间：O(n)
归并排序需要 O(n) 的额外空间来存放临时数组。这是稳定的 O(n log n) 排序所付出的代价——堆排序节省空间，但不稳定。请查看代码。
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原地算法：O(1) 空间
原地算法会直接修改输入，不使用与输入规模成比例的额外存储空间——例如使用两个指针反转数组。这样空间复杂度就能保持为 O(1)。请查看代码。
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]时间与空间的权衡：两数之和
时间与空间的权衡无处不在。两数之和问题可以用 O(n^2) 的时间和 O(1) 的空间解决，也可以借助哈希表用 O(n) 的时间和 O(n) 的空间解决。请同时说明两者，并询问哪一项更重要。
# 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]记忆化与表格法的空间比较
自顶向下的记忆化需要 O(n) 的记忆表空间和 O(n) 的栈空间；自底向上的表格法则不需要栈。只保留最后几行可以将空间降到 O(1)——这就是空间优化的 DP。
# 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哈希表空间：O(n)
哈希表是解题中通常需要 O(n) 空间的结构：可以用记录已访问元素的集合进行访问跟踪，也可以用频率表进行计数。一定要报告这部分空间——“时间 O(n)，空间 O(n)”才是完整答案。
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']))图算法的空间分析
图确实会占用空间：邻接表是 O(V + E)，BFS 的已访问集合和队列是 O(V)，DFS 的递归深度是 O(V)。请用 V 和 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]字符串和数组分配的陷阱
隐藏的内存分配可能会带来 O(n) 的空间：切片会创建新列表，而在循环中对字符串使用 + 会产生 O(n^2) 的成本。排序函数会复制数据，但 lst.sort() 会原地操作。请查看代码。
# 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]面试中识别空间权衡
一开始就说明您的空间复杂度。如果面试官希望减少空间，常见做法包括用自底向上的 DP 替代记忆化，或使用原地排序替代哈希表。请查看代码。
# 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完整复杂度说明模板
一定要给出完整的说明——同时包含时间和空间：“时间 O(n)，额外空间 O(1)。”如果存在权衡，也要说明。这正是资深候选人与其他人的区别。
# 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]]快速检查
快速检查一下——看看空间复杂度的概念掌握得如何。您已经准备好了。✅
课程回顾
回顾：辅助空间要与输入空间分开计算，递归会使用 O(深度) 的栈空间，而时间与空间的权衡影响着大多数算法设计选择。
常见问题解答
「空间复杂度与权衡」课时是免费的吗？
是的 — 「空间复杂度与权衡」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「空间复杂度与权衡」这节课中我会学到什么？
衡量调用栈和辅助数据结构占用的辅助空间，并认识记忆化与原地算法中的时间—空间权衡。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「空间复杂度与权衡」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 从零理解大 O 记法
- 分析循环与嵌套循环
- 递归与递归树法
- 空间复杂度与权衡