空间复杂度与时空权衡

本节目标

掌握空间复杂度的分析方法
理解"空间换时间"与"时间换空间"
认识原地（in-place）算法与均摊分析

空间复杂度：算法运行需要的额外内存随 n 增长的阶（通常不含输入本身）。和数据规模无关的固定变量是 O(1)，复制一份数组是 O(n)。

// 运行环境：Node.js 14+
// 保存为 dsa-l2.js，执行：node dsa-l2.js

// O(1)：只用了常数个变量
function sum(arr) { let s = 0; for (const x of arr) s += x; return s }

// O(n)：复制了一份数组
function reverseCopy(arr) {
  const out = []
  for (let i = arr.length - 1; i >= 0; i--) out.push(arr[i])
  return out
}

// O(n²)：二维矩阵
function matrix(n) {
  return Array.from({ length: n }, () => new Array(n).fill(0))
}

// 递归的空间 = 调用栈深度：factorial(1000) 会压 1000 层栈 → 空间 O(n)
function factorial(n) { return n <= 1 ? 1 : n * factorial(n - 1) }

// 空间换时间：两数之和 暴力 O(n²) vs 哈希 O(n)
function twoSum(nums, target) {
  const seen = new Map()          // 额外空间 O(n)，换来 O(n) 时间
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i]
    if (seen.has(need)) return [seen.get(need), i]
    seen.set(nums[i], i)
  }
  return []
}

console.log(reverseCopy([1, 2, 3])) // [3, 2, 1]
console.log(twoSum([2, 7, 11, 15], 9)) // [0, 1]

原地算法（in-place）：在输入数组上直接修改，额外空间 O(1)。例：双指针反转数组、快排分区、堆排序。

均摊分析（Amortized）：某些操作偶尔很贵（如数组扩容），但把代价摊到每次操作上就是 O(1)。例：push 到 JS 数组是均摊 O(1)（动态扩容翻倍，偶尔 O(n) 拷贝，摊薄后常数）。

权衡决策：面试和工程里优先保证时间达标；内存吃紧（大数据 / 低端设备）时再用空间换回来。学会说"这里用 O(n) 空间把查找从 O(n²) 降到 O(n)"。

名词解释

空间复杂度（Space Complexity）：算法除输入外额外占用的内存随 n 增长的趋势。类比：租仓库——你自带 n 箱货不算，额外又租了几间房才是"额外空间"。
原地算法（In-place Algorithm）：直接在原数据结构上修改、几乎不申请额外空间的算法，空间 O(1)。优点是省内存，缺点是会破坏原数据（有时需要保留副本）。
均摊分析（Amortized Analysis）：把少数"昂贵操作"的代价平均分摊到一系列"廉价操作"上，得到每次操作的平均成本。典型：动态数组扩容。

课后练习

原地反转数组（双指针，O(1) 空间）怎么写？
- 答案：let l=0,r=arr.length-1; while(l<r){[arr[l++],arr[r--]]=[arr[r],arr[l]]} —— 左右对撞交换，只用两个指针。
爬楼梯 DP 为什么空间能从 O(n) 降到 O(1)？
- 答案：dp[i]=dp[i-1]+dp[i-2] 只依赖前两项，不必保留整个数组，用两个滚动变量即可：let a=1,b=1; for(...){[a,b]=[b,a+b]}。

总结

时空权衡是算法世界最朴素也最深刻的辩证法：绝大多数性能优化的本质，都是"用更多内存换更少时间"，或者反过来在内存受限时"用更多时间省下内存"。一个成熟的工程师不会死守某一边，而是先问"瓶颈到底是 CPU 还是内存"。哈希表是最经典的"空间换时间"——它把 O(n) 查找压成 O(1)，代价是多存一份索引；而原地算法（如双指针反转）则是"时间换空间"的代表，几乎零额外内存。理解均摊分析还能破除一个常见误解：JS 数组 push 看似每次都追加，其实因为翻倍扩容策略，平均仍是 O(1)。学会这套权衡语言，你在面试里讲算法就不只是"能跑"，而是"知道为什么这么设计"。