【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-1
https://developer.aliyun.com/article/1538357
三、空间复杂度的计算
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少Byte的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
【示例1】：
// 计算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; } }
记住一个点：时间是累计的，空间是不累计的，空间是可以重复利用的，for循环走了N次，重复利用的是一个空间。
即这个算法的空间复杂度为：
O（1）
【示例2】：
// 计算Fibonacci的空间复杂度？ 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 ; }
空间复杂度为：
O（N）
【示例3】：
// 计算阶乘递归Factorial的空间复杂度？ long long Factorial(size_t N) { return N < 2 ? N : Factorial(N-1)*N; }
每次调用都会创建栈帧，调用了N次，每个栈帧使用了常数个空间O（1），其整体的空间复杂度为：
O（N）
四、Leetcode刷题
1. 消失的数
思路一：排序 --> 对于示例输入：0 1 3，后一个数比前一个数大一就说明找到了
这个思路可行，但不符合提议为O（n）
排序 --> 最快排序O（N * logN），不符合。
思路2：把0到n的所有整数加到一起，结果为ret1，把输入示例中数组的数加到一起，结果为ret2，用ret1减去ret2，得到的结果就是所缺失的数。
int missingNumber(int* nums, int numsSize){ int ret1 = 0; // 缺失一个数，那么0到n的所有数的个数就是numsSize的个数加1 for(int i = 0; i < numsSize + 1; i++) { ret1 += i; // 计算0到n之间所有的数的和 } int ret2 = 0; for(int j = 0; j < numsSize; j++) { ret2 += nums[j]; // 计算数组nums中所有数的和 } return ret1 - ret2; }
思路3：按位异或，两个数按位异或（二进制），相同为0，相异为1，两个相同的数按位异或得到的就是0，另外，异或是支持交换律的，这意味着不需要排序直接依次异或即可。我们把从0到n之间的所有数与数组中的数依次按位异或，相同的数按位异或直接就等于0，最后得到的结果就是缺失的数。
int missingNumber(int* nums, int numsSize){ int n = 0; for(int i = 0; i < numsSize; i++) { // 先跟数组中的数异或 n ^= nums[i]; // 0异或任何数还是原来那个数 } for(int j = 0; j < numsSize + 1; j++) { // 在跟[0,n]之间所有的数异或 n ^= j; } return n; }
2. 旋转数组
题意：输入一个数k，将数组中的每个元素向右移动k位，数组的最后一个元素向右移动移位后就成了数组的第一个元素。
思路一：旋转k次，给一个变量tmp用于存数组的最后一个元素，从数组的最后一个元素开始，与他的前面一个元素互换，然后将tmp赋值给数组的首元素，这是旋转一次的过程，最后循环k次就可以了。
缺陷：Leetcode中有些测试样例将数组给的特别大，跑不过。
这种算法的时间复杂度为O（N * K）
思路二：以空间换时间，创建一个和nums同样大的数组，将nums数组的后k位元素与前k位元素进行互换，然后在将新数组中的元素拷贝到nums中。
缺陷：时间复杂度为O（N），空间复杂度为O（N），与题意不相符。
思路三：后k个逆置，前n - k个逆置，最后在整体逆置。假设给定一个数组：[1，2，3，4，5，6，7]，k = 3，前k个逆置之后变成[1，2，3，4，7，6，5]，前n - k个逆置后变成[4，3，2，1，7，6，5]，最后在整体逆置后变成[5，6，7，1，2，3，4]，最后得到的结果就和测试样例中的一样啦。
样例中可能会出现k大于数组元素的个数，对k取数组大小的余数即可。
// 逆置操作 void Reverse(int *nums, int left, int right) { while(left < right) { int tmp = nums[left]; nums[left] = nums[right]; nums[right] = tmp; left++; right--; } } void rotate(int* nums, int numsSize, int k) { if(k >= numsSize) { k %= numsSize; // 如果k大于数组, 对k进行取模操作 } // 数组后k个逆置 Reverse(nums, numsSize - k, numsSize - 1); // 数组前n - k个逆置 Reverse(nums, 0, numsSize - k - 1); // 数组整体逆置 Reverse(nums, 0, numsSize - 1); }
