空间复杂度
- 空间复杂度涉及的空间类型有：
- 输入空间： 存储输入数据所需的空间大小；
- 暂存空间： 算法运行过程中，存储所有中间变量和对象等数据所需的空间大小；
- 输出空间： 算法运行返回时，存储输出数据所需的空间大小；
- 通常情况下，空间复杂度指在输入数据大小为 N 时，算法运行所使用的
「暂存空间」+「输出空间」的总体大小；
![]( "空间复杂度")
- 根据不同来源，算法使用的内存空间分为三类：
- 指令空间：编译后，程序指令所使用的内存空间；
- 数据空间：算法中的各项变量使用的空间，包括：声明的常量、变量、动态数组、动态对象等使用的内存空间；
class Node { constructor(val, next) { this.val = val; this.next = next; } } function algorithm(N) { let num = N; // 变量 let nums = new Array(N); // 动态数组 let node = new Node(N, null); // 动态对象 } - 栈帧空间：程序调用函数是基于栈实现的，函数在调用期间，占用常量大小的栈帧空间，直至返回后释放；
JSJS
function test() { return 0; } function algorithm(N) { // 每轮调用 test() 返回后，栈帧空间已被释放，因此空间复杂度仍为 O(1) for (let i = 0; i < N; i++) { test(); } }function algorithm(int N) { if (N <= 1) return 1; // 通过递归调用，会同时存在 N 个未返回的函数 algorithm() ，此时累计使用 O(N) 大小的栈帧空间 return algorithm(N - 1) + 1; }
符号表示
-
通常情况下，空间复杂度统计算法在 最差情况 下使用的空间大小，以体现算法运行所需预留的空间量，使用符号 O 表示；
-
最差情况有两层含义，分别为「最差输入数据」、算法运行中的「最差运行点」，例如以下代码：
function algorithm(N) { let num = 5; // O(1) let nums = new Array(10); // O(1) if (N > 10) { nums = new Array(N); // O(N) } }- 最差输入数据： 当 N≤10 时，数组 nums 的长度恒定为 10 ，空间复杂度为
O(1)；当 N>10 时，数组 nums 长度为 N ，空间复杂度为O(N)；因此，空间复杂度应为最差输入数据情况下的O(N)； - 最差运行点： 在执行 nums = [0] * 10 时，算法仅使用
O(1)大小的空间；而当执行 nums = [0] * N 时，算法使用O(N)的空间；因此，空间复杂度应为最差运行点的O(N)；
- 最差输入数据： 当 N≤10 时，数组 nums 的长度恒定为 10 ，空间复杂度为
常见种类
常数 O(1)
普通常量、变量、对象、元素数量与输入数据大小 N 无关的集合，皆使用常数大小的空间
function test() {
return 0;
}
function algorithm(N) {
// 每轮调用 test() 返回后，栈帧空间已被释放，因此空间复杂度仍为 O(1)
for (let i = 0; i < N; i++) {
test();
}
}
线性 O(N)
元素数量与 N 呈线性关系的任意类型集合（常见于一维数组、链表、哈希表等）或者递归调用，皆使用线性大小的空间
function algorithm(int N) {
if (N <= 1) return 1;
// 通过递归调用，会同时存在 N 个未返回的函数 algorithm() ，此时累计使用 O(N) 大小的栈帧空间
return algorithm(N - 1) + 1;
}
平方 O(N^2)
元素数量与 N 呈平方关系的任意类型集合（常见于矩阵）或递归调用并占用内存与 N 呈线性关系，皆使用平方大小的空间
.jpg "平方 O(N^2)")
function algorithm(N) {
if (N <= 0) return 0;
let nums = new Array(N);
return algorithm(N - 1);
}
指数 O(2^N)
指数阶常见于二叉树、多叉树；
- 例如，高度为 N 的「满二叉树」的节点数量为 2^N ，占用
O(2^N)大小的空间- 同理，高度为 N 的「满 m 叉树」的节点数量为 m^N ，占用
O(m^N)大小的空间
.jpg "指数 O(2^N)")
对数 O(logN)
对数阶常出现于分治算法的栈帧空间累计、数据类型转换等，例如：
- 快速排序 ，平均空间复杂度为
Θ(logN)，最差空间复杂度为O(N)；拓展知识：通过应用 尾递归优化，可以将快速排序的最差空间复杂度限定至O(N)；- 数字转化为字符串，设某正整数为 N ，则字符串的空间复杂度为
O(logN)；推导如下：正整数 N 的位数为 log10^N ，即转化的字符串长度为 log10^N ，因此空间复杂度为O(logN)；
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
算法基础🔮 时间复杂度
上一篇
评论
