【解密算法：时间与空间的博弈】（中）：https://developer.aliyun.com/article/1424859
5.空间复杂度
空间复杂度也是一个数学表达式，是对一个算法在运行过程中额外临时占用存储空间大小的量度。
空间复杂度不是程序占用了多少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; } }
在 BubbleSort 中，输入数组不是额外开辟的空间，不算入到空间复杂度上，其余只使用了很少的额外空间，主要是用来存储一些临时变量，如循环索引、交换标志等。这些额外空间的使用量不会随着输入规模 n 的增加而显著变化。无论输入数组的大小如何，BubbleSort 需要的额外空间是固定的。
因此，BubbleSort 的空间复杂度为 O(1)。
实例二：
// 计算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; }
额外数组的空间： 在 Fibonacci 函数内部，通过动态内存分配 malloc 来创建一个大小为 (n + 1) 的长整型数组 fibArray，用于存储斐波那契数列的前 n 项。这个数组的空间占用是与 n 相关的。
所以，总的空间复杂度由额外数组的空间复杂度决定。
在这种情况下，空间复杂度是 O(N)。
实例三：
// 计算阶乘递归Fac的空间复杂度？ long long Fac(size_t N) { if (N == 0) return 1; return Fac(N - 1) * N; }
阶乘递归函数 Fac 的空间复杂度是 O(N)，因为每次递归调用都会在函数调用栈上创建一个新的递归帧，每个递归帧需要一些内存空间来存储局部变量、返回地址等。
在最坏情况下，当递归深度达到 N 时，需要在栈上保留 N 层递归帧。因此，空间复杂度与递归的深度成正比，为 O(N)。
实例四：
// 计算阶乘递归Fac的空间复杂度？ long long Fac(size_t N) { if (N == 0) return 1; return Fac(N - 1) * N; }
这个斐波那契递归函数的空间复杂度是 O(N)。虽然函数本身没有显式地使用额外的数组或数据结构，但是在递归调用的过程中，每次调用都会在函数调用栈中创建一个新的函数调用帧。由于递归函数会多次调用自身，每次调用都需要分配一些内存来存储函数参数、局部变量以及返回地址等信息，这些内存会随着递归深度的增加而累积。递归深度直接影响了调用栈中需要分配的内存空间数量。
我们拿 Fib(6) 举例，在这个递归实现中，当你调用 Fib(6) 时，它会依次调用 Fib(5) 和 Fib(4)，然而并不是右边那个Fib(4) ，是 Fib(5) 下面的 Fib(4) ，然后这些调用会进一步调用更低层次的函数，以此类推。当调完 Fib(2)后该函数栈帧就销毁了，然后生成 Fib(1)的栈帧， Fib(1)调完后也就释放了，以此类推。由于栈空间是可以复用的，一个栈帧释放空间就还给操作系统了，可以给后面的函数调用留下空闲的空间，整个过程中，递归最深的层数也就是Fib(6)到 Fib(2)了，其余调用的都是使用之前栈帧释放的空间，且深度也低。
因此，递归的空间复杂度通常与递归的深度成正比，即 O(N)。这意味着在最坏情况下，调用栈的深度将达到 N 层，每一层都需要一些内存空间。这也是为什么递归在解决某些问题时可能会导致栈溢出或效率较低的原因之一。
下面这个例子就证明了栈空间是可复用滴。
#include<stdio.h> void Func1() { int a = 0; printf("%p\n", &a); } void Func2() { int b = 0; printf("%p\n", &b); } int main() { Func1(); Func2(); return 0; }
运行结果：
因为在许多编译器和操作系统中，函数调用时会使用相同的堆栈帧空间。这意味着在一个函数结束后，其分配给局部变量的堆栈空间可能会被重用给下一个函数的局部变量。
因此，虽然在逻辑上
Func1和Func2是在不同的函数调用中，它们的局部变量a和b分别被分配到了相同的堆栈空间（因为这两个函数的栈帧在调用时被重用），从而导致它们的局部变量的地址也相同。
6.常见复杂度对比
7.复杂度oj练习
1.消失的数字OJ链接：https://leetcode.cn/problems/missing-number-lcci/
思路一：排序+遍历（后一个数不等于前一个数+1，那么这个数就是消失的数）
复杂度是：O(N*log(N)) - 不符合题意
#include<stdio.h> #include <stdlib.h> #include <assert.h> int compare(const void* a, const void* b) { return (*(int*)a - *(int*)b); } int missingNumber(int* nums, int numsSize) { assert(nums); qsort(nums, numsSize, sizeof(int), compare); if (nums[0] != 0) return 0; for (int i = 0; i < numsSize - 1; i++) { //后一个数不等于前一个数+1，那么这个数就是消失的数 if ((nums[i] + 1) != nums[i + 1]) return nums[i] + 1; } return -1;//不存在缺少的数字 } int main() { int arr[] = { 9,6,4,2,3,5,7,0,1 }; printf("%d\n", missingNumber(arr, sizeof(arr) / sizeof(arr[0]))); return 0; }
思路二：0+N等差公式计算结果 - 数组中的值
复杂度是：O(N) - 符合题意
#include<stdio.h> #include <assert.h> int missingNumber(int* nums, int numsSize) { assert(nums); int result = numsSize * (0 + numsSize + 1) / 2;//计算从0到n的和，一共是n+1个数 for (int i = 0; i < numsSize; i++) { result -= nums[i]; } return result; } int main() { int arr[] = { 9,6,4,2,3,5,7,0,1 }; printf("%d\n", missingNumber(arr, sizeof(arr) / sizeof(arr[0]))); return 0; }
思路三：单身狗思路 - 异或运算 - 相同为0，相异为1
复杂度是：O(N) - 符合题意
#include<stdio.h> #include <assert.h> int missingNumber(int* nums, int numsSize) { assert(nums); //0 1 .... N //数组中的值 //其他数字成对出现，缺少的数字为单身狗 int x = 0;//x为缺失的数字 for (int i = 0; i <= numsSize; i++) { x ^= i; } for (int i = 0; i < numsSize; i++) { x ^= nums[i]; } return x; } int main() { int arr[] = { 9,6,4,2,3,5,7,0,1 }; printf("%d\n", missingNumber(arr, sizeof(arr) / sizeof(arr[0]))); return 0; }
图解：
2.旋转数组OJ链接：https://leetcode.cn/problems/rotate-array/
思路一：暴力求解，直接右旋
时间复杂度是：O(N^2) ，空间复杂度是：O(1)
#include<stdio.h> #include<assert.h> void rotate(int* nums, int numsSize, int k) { assert(nums); int count = k % numsSize; while (count--) { int temp = nums[numsSize - 1]; for (int i = numsSize - 1; i > 0; i--) { nums[i] = nums[i - 1]; } nums[0] = temp; } } int main() { int nums[] = { 1, 2, 3, 4, 5, 6, 7 }; //[7,1,2,3,4,5,6] int k = 0; scanf("%d", &k); rotate(nums, sizeof(nums) / sizeof(nums[0]), k); for (int i = 0; i < sizeof(nums) / sizeof(nums[0]); i++) { printf("%d ", nums[i]); } return 0; }
思路二：新建数组，把数组后k个数先拷贝过来，再把numsSize-k个数拷贝，再拷贝回原数组nums
时间复杂度是：O(N) ，空间复杂度是：O(N)
#include<stdio.h> #include<assert.h> #include<stdlib.h> #include<string.h> void rotate(int* nums, int numsSize, int k) { assert(nums); int* temp = (int*)malloc(sizeof(int) * numsSize); k %= numsSize; if (!temp) { perror("malloc"); return; } memcpy(temp, nums + numsSize - k, sizeof(int) * k); memcpy(temp + k, nums, sizeof(int) * (numsSize - k)); //拷贝回去 memcpy(nums, temp, sizeof(int) * numsSize); free(temp); temp = NULL; } int main() { int nums[] = { 1, 2, 3, 4, 5, 6, 7 }; //[7,1,2,3,4,5,6] int k = 0; scanf("%d", &k); rotate(nums, sizeof(nums) / sizeof(nums[0]), k); for (int i = 0; i < sizeof(nums) / sizeof(nums[0]); i++) { printf("%d ", nums[i]); } return 0; }
思路三：将前numsSize-k逆置，再将后k个逆置，最后整体逆置数组
时间复杂度是：O(N) ，空间复杂度是：O(1)
#include<stdio.h> #include<assert.h> void reverse(int* nums, int left, int right) { assert(nums); { while (left < right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } } } void rotate(int* nums, int numsSize, int k) { assert(nums); k %= numsSize;//防止k大于numsSize reverse(nums, 0, numsSize - k - 1); reverse(nums + numsSize - k, numsSize - k, numsSize - 1); //整体逆置 reverse(nums, 0, numsSize - 1); } int main() { int nums[] = { 1, 2, 3, 4, 5, 6, 7 }; //[7,1,2,3,4,5,6] int k = 0; scanf("%d", &k); rotate(nums, sizeof(nums) / sizeof(nums[0]), k); for (int i = 0; i < sizeof(nums) / sizeof(nums[0]); i++) { printf("%d ", nums[i]); } return 0; }
