【数据结构】空间复杂度

阅读本文，需要对算法的基本概念有所了解，可以阅读以下文章进行学习。

【数据结构】算法的基本概念

1. 算法效率的度量

时间复杂度参考下列文章：

【数据结构】时间复杂度

2. 空间复杂度

空间复杂度研究算法空间开销（内存开销）与问题规模n之间的关系。记为：

S(n)=O(f(n))

S表示“Space”。

说明：空间复杂度就是研究与问题规模有关的数据部分。

算法原地工作：算法所需内存空间为常量。

运算规则

1. 加法规则

多项相加，只保留最高阶的项，且系数变为1。

2. 乘法规则

多项相乘，都保留。

注意

1. 只需关注存储空间大小和问题规模相关的变量。
2. 函数递归调用时：空间复杂度与递归调用的深度有关。
3. 如果算法运行所需的内存空间是固定的常量，则空间复杂度为O(1)。
4. 空间复杂度计算忽略高阶项系数和低阶项。

示例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. 小结