江小南

V1

2023/02/03阅读:16主题:萌绿

【数据结构】空间复杂度

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

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

1. 算法效率的度量

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

【数据结构】时间复杂度

2. 空间复杂度

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

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

S表示“Space”。

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

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

运算规则

  1. 加法规则

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

  1. 乘法规则

多项相乘,都保留。

注意

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

分类:

后端

标签:

数据结构与算法

作者介绍

江小南
V1