一、空间复杂度衡量什么空间复杂度衡量的是算法执行过程中额外申请的内存空间不包括输入数据本身占用的空间。我们关注的是当数据规模 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; }内存中的栈帧分布以 N4 为例栈顶 | 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总时间是累加的。空间可以复用第一层递归的栈帧在函数返回后就被销毁了这块内存可以留给后面的递归层使用。因此空间复杂度只看同时存在的最大空间不是累计申请的空间。六、快速判断口诀代码特征空间复杂度判断要点固定数量的局部变量O(1)与 N 无关长度为 N 的辅助数组O(N)额外数组大小递归每次规模减1O(N)递归深度 N递归每次规模减半O(log N)递归深度 log N递归深度 log N 每层固定数组O(log N)空间可复用看最大同时占用七、练习题题目1void s1(int N) { int a, b, c; for (int i 0; i N; i) { a i; } }空间复杂度是多少题目2void s2(int N) { int temp[N]; // 额外数组 for (int i 0; i N; i) { temp[i] i; } }空间复杂度是多少题目3void s3(int N) { if (N 1) return; s3(N - 1); }空间复杂度是多少题目4void s4(int N) { if (N 1) return; s4(N / 2); }空间复杂度是多少题目5void s5(int N) { if (N 1) return; int arr[100]; // 固定大小100的数组 s5(N / 2); }空间复杂度是多少注意每层都有 arr[100]但空间可复用答案与解析题号空间复杂度解析1O(1)只有固定变量 a, b, c, i2O(N)申请了长度为 N 的辅助数组3O(N)递归深度为 N每次减14O(log N)递归深度为 log N每次减半5O(log N)递归深度为 log N。虽然每层有 arr[100]但栈帧是先后使用的不是同时存在最大同时空间为 100 × log N即 O(log N)