(02)王道数据结构-空间复杂度

算法1：逐步递增型爱你

#include<stdio.h>
void loveYou(int n);
int main(void) {
    loveYou(3000);
    return 0;
}

void loveYou(int n) {  //n为问题规模   
    int i = 1;         //爱你的程度
    while (i <= n) {   //每次+1
        i++;
        printf("I Love You %d\n", i);
    }
    printf("I Love You More Than %d\n", n);
}

代码分析：

(1)程序运行时，会将程序代码装载进内存中，而内存中存放程序代码的部分大小是固定的，与问题规模无关

(2)本程序中，装入内存的变量有局部变量i和参数n,他们所占内存空间大小是不变的

(3)本程序空间复杂度: S(n) = O(1)

算法2：数组的空间复杂度

#include<stdio.h>
int main(void) {
    int flag[n];  //声明一个长度为n的数组,此时时间复杂度S(n) = O(n)
  
    /*
    下列代码空间复杂度度：S(n) = O(n*n) + O(n) + O(1) = O(n*n)
    */
      int flag[n][n];  
    int other[n];
      int i;
    return 0;
}

$$ 加法规则：T(n) = T_1(n) + T_2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n))) $$

算法2：递归型爱你

#include<stdio.h>
void loveYou(int n);
int main(void) {
    loveYou(5);
    return 0;
}

void loveYou(int n) {  //n为问题规模   
    int a,b,c;        //声明一系列局部变量
    if(n > 1) {
        loveYou(n-1);
    }
    printf("I Love You %d\n", n);
}

代码分析：

第1层调用: n=5, a, b, c

第2层调用: n=4, a, b, c

第3层调用: n=3, a, b, c

第2层调用: n=2, a, b, c

第1层调用: n=1, a, b, c

空间复杂度：等于递归调用的深度，S(n) = O(n) （去掉了常数项5）

算法3：递归型爱你

#include<stdio.h>
void loveYou(int n);
int main(void) {
    loveYou(5);
    return 0;
}

void loveYou(int n) {  //n为问题规模   
    int flag[n];       //声明一个数组
    if(n > 1) {
        loveYou(n-1);
    }
    printf("I Love You %d\n", n);
}