数据结构第一课-----------数据结构的介绍-1
https://developer.aliyun.com/article/1498067
空间复杂度
空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
// 计算BubbleSort的空间复杂度？ void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; ++i) { if (a[i-1] > a[i]) { Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; } }
这里的变量创建了3个空间复杂度s
在计算空间复杂度时，形参通常不会被考虑在内。空间复杂度主要关注的是算法执行过程中所使用的额外空间，而形参通常是在函数调用时传递的参数，不会占用额外空间。因此，在计算空间复杂度时，通常只考虑算法中使用的变量、数据结构和临时空间等。
// 计算Fibonacci的空间复杂度？ // 返回斐波那契数列的前n项 long long* Fibonacci(size_t n) { if(n==0) return NULL; long long * fibArray = (long long *)malloc((n+1) * sizeof(long long)); fibArray[0] = 0; fibArray[1] = 1; for (int i = 2; i <= n ; ++i) { fibArray[i] = fibArray[i - 1] + fibArray [i - 2]; } return fibArray; }
这里主要是创建了n+1个空间进行存储，空间复杂度是O(n)
那下面我来推荐一道题
这道题我们可以通过创建额外的空间让时间复杂度降低, 数组中的元素充当额外数组的下标,遍历一遍额外数组找出不存在的,就可以解出来,空间复杂度是O(n).时间复杂度是O(n)
// 计算阶乘递归Fac的空间复杂度？ long long Fac(size_t N) { if(N == 0) return 1; return Fac(N-1)*N; }
这里主要是递归，函数里面调用函数
调用情况：
一共调用了N次，总共创建了N个空间，空间复杂度是O（N）
而我们计算斐波那契数的空间复杂度也是O(N)
因为递归的空间复杂度,也是空间的累计,但是不同的是空间是重复利用,为啥要这样说呢?
因为函数调用是一个个调用的,不是一下子调用全部函数
下面的代码可以演示
#include<stdio.h> #include<string.h> int fun(int N) { int a = 0; printf("%p\n", &a); } int fun1(int N) { int a = 0; printf("%p\n", &a); } int main() { fun(1); fun1(1); return 0; }
总结
时间复杂度和空间复杂度就介绍到这里了,感兴趣的小可爱可以私聊我
