【数据结构与算法】空间复杂度从入门到面试：不仅会算，还要会解释

张开发
• 2026/4/15 23:31:27 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【数据结构与算法】空间复杂度从入门到面试：不仅会算，还要会解释
‍ 关于作者会编程的土豆“不是因为看见希望才坚持而是坚持了才看见希望。”你好我是会编程的土豆一名热爱后端技术的Java学习者。正在更新中的专栏《数据结构与算法》《leetcode hot 100》《数据库mysql》作者简介后端学习者很多人学算法时都会有一个真实问题时间复杂度还能勉强分析但空间复杂度一问就容易卡住尤其一遇到递归、容器就开始不确定。其实空间复杂度并不难它的核心只有一句话程序运行过程中额外占用了多少随输入规模 n 增长的内存。这篇文章不讲空话直接结合代码把空间复杂度一层一层讲清楚。一、最基础什么是空间复杂度先看一个最简单的例子int sum(int n) { int s 0; for (int i 1; i n; i) { s i; } return s; }这段代码只用了s和i两个变量不管 n 多大变量数量不变所以空间复杂度是O(1)二、空间“跟着 n 变”的情况再看一个例子vectorint buildArray(int n) { vectorint a(n); for (int i 0; i n; i) { a[i] i; } return a; }这里关键点vectorint a(n)开辟了 n 个空间n 越大占用空间越大所以空间复杂度 O(n)三、二维情况更高维空间vectorvectorint matrix(int n) { vectorvectorint a(n, vectorint(n)); return a; }这里开了一个 n × n 的二维数组空间复杂度 O(n²)四、最容易忽略的重点递归栈来看一个经典递归int dfs(int n) { if (n 0) return 0; return dfs(n - 1) 1; }这个函数会dfs(n) → dfs(n-1) → dfs(n-2) → ... → dfs(0)一共调用 n 层每一层都会占用栈空间。所以空间复杂度 O(n)再看一个更典型的例子二叉树int maxDepth(TreeNode* root) { if (!root) return 0; return max(maxDepth(root-left), maxDepth(root-right)) 1; }这里递归深度取决于树的高度平衡树高度 ≈ log n → O(log n)极端链式树高度 n → O(n)五、辅助数据结构的空间比如 BFSvectorvectorint levelOrder(TreeNode* root) { vectorvectorint res; if (!root) return res; queueTreeNode* q; q.push(root); while (!q.empty()) { int n q.size(); vectorint level; for (int i 0; i n; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } res.push_back(level); } return res; }这里用到了队列queue结果数组res最坏情况下空间复杂度 O(n)六、经典案例堆排序的空间复杂度很多人会误判这个题。代码递归版 heapifyvoid heapify(vectorint arr, int i, int heapSize) { int largest i; int left 2*i 1; int right 2*i 2; if (left heapSize arr[left] arr[largest]) largest left; if (right heapSize arr[right] arr[largest]) largest right; if (largest ! i) { swap(arr[i], arr[largest]); heapify(arr, largest, heapSize); } }分析没有开新数组 → O(1)但是有递归 → 深度 ≈ log n所以空间复杂度 O(log n)优化改成迭代写法void heapify(vectorint arr, int i, int heapSize) { while (true) { int largest i; int left 2*i 1; int right 2*i 2; if (left heapSize arr[left] arr[largest]) largest left; if (right heapSize arr[right] arr[largest]) largest right; if (largest i) break; swap(arr[i], arr[largest]); i largest; } }此时空间复杂度 O(1)七、常见误区总结1. 把输入算进去vectorint nums(n);这个不算空间复杂度。2. 忽略递归dfs(n)必须考虑调用栈。3. 忽略容器queue / stack / map这些通常都是 O(n)。八、通用判断模板面试直接用判断空间复杂度可以按这个顺序有没有 new / vector / 数组 → 看是否 O(n)有没有递归 → 看深度n / log n有没有辅助结构队列、栈、哈希表取最大的一项九、一句话总结空间复杂度本质就是额外空间 递归调用栈谁增长最快就看谁。

更多文章