算法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;
}
**算法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);
}
代码分析:
第1层调用: n=5, flag[5]
第2层调用: n=4, flag[4]
第3层调用: n=3, flag[3]
第2层调用: n=2, flag[2]
第1层调用: n=1, flag[1]
空间复杂度: