企业官网建设流程全解析

一、空间复杂度衡量什么

空间复杂度衡量的是算法执行过程中额外申请的内存空间，不包括输入数据本身占用的空间。我们关注的是：当数据规模 N 增大时，额外内存是否随之增长。

二、O(1)：固定额外空间

如果算法只使用了固定数量的变量，无论 N 多大，内存占用都不变，就是 O(1)。

#include <stdio.h> /* * 功能：查找数组中的最大值 * 空间复杂度：O(1) * * 只使用了 maxVal 和 i 两个变量 * 没有申请与 N 相关的额外空间 */ int findMax(int arr[], int N) { int maxVal = arr[0]; // 固定变量1 for (int i = 1; i < N; i++) { // 固定变量2 if (arr[i] > maxVal) { maxVal = arr[i]; } } return maxVal; }

三、O(N)：额外数组空间

当算法需要创建一个与输入规模 N 相当的新数组来存储中间结果时，空间复杂度为 O(N)。

#include <stdio.h> /* * 功能：复制数组并反转 * 空间复杂度：O(N) * * 创建了一个长度为 N 的辅助数组 helper * 额外空间随 N 线性增长 */ void reverseCopy(int arr[], int N) { int helper[N]; // 额外申请 N 个空间 for (int i = 0; i < N; i++) { helper[i] = arr[N - 1 - i]; } for (int i = 0; i < N; i++) { printf("%d ", helper[i]); } printf("\n"); }

四、递归的栈空间（重点）

递归函数的空间复杂度不是看代码里定义了几个变量，而是看递归调用栈的深度。每次递归调用，系统都会在内存栈中创建一个"栈帧"来保存局部变量和返回地址。

4.1 递归深度为 N（每次减1）

#include <stdio.h> /* * 功能：递归递减，演示 O(N) 空间复杂度 * * 递归过程： * recurse(4) -> recurse(3) -> recurse(2) -> recurse(1) * * 每一层递归都会占用一个栈帧，同时存在的栈帧最多有 N 个 * 因此空间复杂度为 O(N) */ void recurseDown(int N) { if (N <= 1) { printf("到达底部\n"); return; } int local = N; // 局部变量，存在当前栈帧中 printf("递归层 N=%d\n", N); recurseDown(N - 1); // 每次减1，深度为 N } int main() { recurseDown(4); return 0; }

内存中的栈帧分布（以 N=4 为例）：

栈顶 | recurse(1) | <- 最先创建，最后释放 | recurse(2) | | recurse(3) | 栈底 | recurse(4) | <- 最后创建，最先释放

同时存在的栈帧有 4 个，即 N 个。

4.2 递归深度为 log N（每次减半）

#include <stdio.h> /* * 功能：递归折半，演示 O(log N) 空间复杂度 * * 递归过程： * recurse(16) -> recurse(8) -> recurse(4) -> recurse(2) -> recurse(1) * * 深度为 log₂N，同时最多只存在 log N 个栈帧 * 因此空间复杂度为 O(log N) */ void recurseHalve(int N) { if (N <= 1) { printf("到达底部\n"); return; } int local = N; printf("递归层 N=%d\n", N); recurseHalve(N / 2); // 每次规模减半，深度为 log N } int main() { recurseHalve(16); // 深度为 4 (16->8->4->2->1) return 0; }

4.3 二分查找的递归版本

#include <stdio.h> /* * 功能：递归版二分查找 * 时间复杂度：O(log N) * 空间复杂度：O(log N) <- 注意这里！ * * 虽然代码里只有 left, right, mid 三个变量 * 但递归深度为 log N，每层栈帧都要保存这些变量 * 因此总空间复杂度由递归深度决定 */ int binarySearchRec(int arr[], int left, int right, int target) { if (left > right) { return -1; // 没找到 } int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { return binarySearchRec(arr, mid + 1, right, target); } else { return binarySearchRec(arr, left, mid - 1, target); } }

五、时间与空间的本质区别

理解空间复杂度时，必须牢记一个关键区别：

• 时间不能复用：第一次循环花了 10ms，第二次循环又花 10ms，总时间是累加的。

• 空间可以复用：第一层递归的栈帧在函数返回后就被销毁了，这块内存可以留给后面的递归层使用。因此空间复杂度只看同时存在的最大空间，不是累计申请的空间。

六、快速判断口诀

七、练习题

题目1：

void s1(int N) { int a, b, c; for (int i = 0; i < N; i++) { a = i; } }

空间复杂度是多少？

题目2：

void s2(int N) { int temp[N]; // 额外数组 for (int i = 0; i < N; i++) { temp[i] = i; } }

空间复杂度是多少？

题目3：

void s3(int N) { if (N <= 1) return; s3(N - 1); }

空间复杂度是多少？

题目4：

void s4(int N) { if (N <= 1) return; s4(N / 2); }

空间复杂度是多少？

题目5：

void s5(int N) { if (N <= 1) return; int arr[100]; // 固定大小100的数组 s5(N / 2); }

空间复杂度是多少？（注意：每层都有 arr[100]，但空间可复用）

答案与解析