空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是计算程序占用了多少字节的空间，算的是变量的个数，也使用大O渐进表示法。
举例1:
1. //计算冒泡排序的空间复杂度 2. #define _CRT_SECURE_NO_WARNINGS 1 3. #include<stdio.h> 4. #include<assert.h> 5. void Swap(int *p1, int *p2) 6. { 7. int temp = *p1; 8. *p1 = *p2; 9. *p2 = temp; 10. } 11. 12. void BubbleSort(int* a,int n) 13. { 14. assert(a); 15. int end = 0; 16. for (end = n; end > 0; --end) 17. { 18. int exchange = 0; 19. for (int i = 1; i < end; i++) 20. { 21. if (a[i - 1] > a[i]) 22. { 23. Swap(&a[i - 1], &a[i]); 24. exchange = 1; 25. } 26. } 27. 28. if (exchange == 0) 29. { 30. break; 31. } 32. } 33. }
计算空间复杂度时，不考虑输入数组的空间，计算的是算法运行中额外使用的空间。对于时间来说，是累计的，但是空间是不累计的，可以复用的(如定义了一个end变量，当执行for循环end不断--时，依旧使用end变量的空间)。该算法定义了4个变量：end、exchage、i、temp，因此额外使用了4个空间，即额外使用了常数个空间，根据大O渐进表示法，空间复杂度为O(1)。
举例2：
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #include<stdio.h> 3. long long* Fibonacci(size_t n) 4. { 5. if (n == 0) 6. { 7. return NULL; 8. } 9. 10. long long* fibArray = (long long*)malloc(sizeof(long long) * (n + 1)); 11. fibArray[0] = 0; 12. fibArray[1] = 1; 13. for (int i = 2; i <= n; i++) 14. { 15. fibArray[i] = fibArray[i - 1] + fibArray[i - 2]; 16. } 17. 18. return fibArray; 19. }
动态开辟了n+1个空间，空间复杂度为O(N)。
递归算法空间复杂度的计算
递归算法的空间复杂度等于递归的深度(递归的层数)，递归多少层就建立多少个栈帧，每建立一个栈帧空间复杂度就是O(1)，即建立常数个空间。
1. long long Factorial(size_t N) 2. { 3. return N < 2 ? N : Factorial(N - 1) * N; 4. }
递归的层数为N，空间复杂度为O(N)。
空间复杂度应用
1.力扣网-移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
分析：空间复杂度为O(1)，即不允许创建额外数组，在原数组上进行操作。可以使用快慢指针的原理，当快指针当前指向的元素值如果不等于val，对快指针+1，如果等于val，将快指针的值赋给慢指针，将快指针和慢指针都+1。
代码：
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #include<stdio.h> 3. 4. int removeElement(int* nums, int numsSize, int val) 5. { 6. if (numsSize == 0) 7. { 8. return 0; 9. } 10. int src = 0; 11. int dst = 0; 12. 13. int i = 0; 14. for (i = 0; i < numsSize; i++) 15. { 16. if (nums[i] != val) 17. { 18. nums[dst] = nums[src]; 19. src++; 20. dst++; 21. } 22. else 23. { 24. src++; 25. } 26. } 27. return dst; 28. } 29. 30. int main() 31. { 32. int arr[] = { 6,3,2,5,2,1,3,2 }; 33. int len = sizeof(arr) / sizeof(arr[0]); 34. int i = 0; 35. int ret = removeElement(arr, len, 2); 36. for (i = 0; i < ret; i++) 37. { 38. printf("%d ", arr[i]); 39. } 40. return 0; 41. }
执行结果：
2.力扣网-删除有序数组中的重复项
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
要求不要使用额外的数组空间，你必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。
分析：要求不要使用额外的数组空间，就必须在原数组上进行操作。使用3个指针，cur指向数组不同元素的第一个，next寻找下一个不同的元素，dst指向新的存放的不同元素的位置。当next和cur指向的元素值不同时，就把next指向的元素存放到dst的位置，cur、next、dst都++，当next和cur指向的元素值相同时，next++直到next指向的元素和cur指向的元素不相等，将dst++,cur=next,next++
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #include<stdio.h> 3. int removeDuplicates(int* nums, int numsSize) 4. { 5. if (numsSize == 0) 6. { 7. return 0; 8. } 9. 10. int cur = 0; 11. int next = 1; 12. int dst = 0; 13. while (next < numsSize) 14. { 15. if (nums[next] != nums[cur]) 16. { 17. nums[dst++] = nums[cur++]; 18. next++; 19. } 20. else 21. { 22. //nums[next] = nums[cur]，不用做操作，next++，直到nums[next] != nums[cur] 23. while ((next < numsSize) && (nums[next] == nums[cur])) 24. { 25. next++; 26. } 27. 28. //现在nums[next] != nums[cur],nums[dst] = nums[cur] 29. nums[dst] = nums[cur]; 30. 31. //dst向后移动一个位置 32. dst++; 33. 34. //cur直接移动到next的位置 35. cur = next; 36. 37. //next向后移动一个位置 38. next++; 39. 40. } 41. } 42. 43. //当next走完整个数组后，直接将cur位置的值赋值给dst++位置 44. if (cur < numsSize) 45. { 46. nums[dst++] = nums[cur]; 47. } 48. return dst; 49. } 50. int main() 51. { 52. int arr[] = { 1,1,2,3,4,4,9,9,9,10 }; 53. int len = sizeof(arr) / sizeof(arr[0]); 54. int ret = removeDuplicates(arr, len); 55. 56. int i = 0; 57. for (i = 0; i < ret; i++) 58. { 59. printf("%d ", arr[i]); 60. } 61. return 0; 62. }
执行结果：
