江
江小南
V1
2023/02/03阅读:16主题:萌绿
【数据结构】空间复杂度
阅读本文,需要对算法的基本概念有所了解,可以阅读以下文章进行学习。
1. 算法效率的度量

时间复杂度参考下列文章:
2. 空间复杂度
空间复杂度研究算法空间开销(内存开销)与问题规模n之间的关系。记为:
S(n)=O(f(n))
S表示“Space”。

说明:空间复杂度就是研究与问题规模有关的数据部分。
算法原地工作:算法所需内存空间为常量。
运算规则
-
加法规则
多项相加,只保留最高阶的项,且系数变为1。
-
乘法规则
多项相乘,都保留。
注意
-
只需关注存储空间大小和问题规模相关的变量。 -
函数递归调用时:空间复杂度与递归调用的深度有关。 -
如果算法运行所需的内存空间是固定的常量,则空间复杂度为O(1)。 -
空间复杂度计算忽略高阶项系数和低阶项。
示例1
#include <stdio.h>
// 逐步递增型爱你
void loveyou(int n){ // n为问题规模
int i=1; // 爱你的程度
while (i<=n){
i++; // 每次加1
printf("I Love You %d\n",i);
}
printf("I Love You More Than %d\n",n);
}
int main() {
loveyou(3000);
return 0;
}
分析:这里为参数n和变量i,都是int类型,共8个字节。无论问题规模怎么变,算法运行所需的内存空间都是固定的常量,算法空间复杂度为:
S(n)=O(1)
示例2
void test(int n){
int flag[n]; // 声明一个长度为n的数组
int i;
// 次数省略很多代码
}
分析:int类型参数n和变量i占4+4=8个字节。而int类型数组占用4n个字节。则所需内存空间=4+4n+4=4n+8。
我们只关注存储空间大小与问题规模相关的变量4n,忽略系数,所以空间复杂度为:
S(n)=O(n)
示例3
void test(int n){
int flag[n][n]; // 声明 n*n 的二维数组
int other[n]; // 声明一个长度为n的数组
int i;
// 此处省略很多代码
}
分析:由于参数n和变量i占用8个字节空间,为常量。而flag二维数组占用空间为4n*4n个字节。other数组占用空间为4n个字节。占用内存=16n平方+4n+8,忽略系数,所以空间复杂度为:

示例4
#include <stdio.h>
// 递归型爱你
void loveYou(int n){
int flag[n]; // 声明一系列局部变量
// 省略代码
if(n>1){
loveYou(n-1);
}
printf("I Love You %d\n",n);
}
int main() {
loveYou(5);
return 0;
}
分析:

参数n占用空间为4字节,大小不变,而flag数组每调用一次会增加一个新的flag[n]数组。

忽略高阶项系数和低阶项,所以空间复杂度为:

3. 小结

作者介绍
江
江小南
V1