【10月更文挑战第21天】
空间复杂度也是⼀个数学表达式，是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占⽤了多少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;
}
}
/*
外面的for循环内局部变量end，内部还有变量exchange
内循环的变量i，总共三个变量
所以这里的空间复杂度是O(1)
*/
三个变量，那么这个空间复杂度就是O(3)
// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
if (N == 0)
return 1;
return Fac(N - 1) * N;
}
/*
F(N)->F(N-1)->....->F(1)->F(0)
总共的空间复杂度就是O(N)
*/
//通过动态申请内容也会涉及到空间复杂度的计算的
int func(int n)
{
int arr[n] = malloc(sizeof(int) * n);
}
//这里的空间复杂度也是O(N)
https://leetcode.cn/problems/rotate-array/description/
思路一:
首先将最后一位数进行保存，再将剩下的数字往右移一位，然后再将保存的数放到第一位
/*给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
进阶：
尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？*/
void rotate(int* nums, int numsSize, int k)
{
while(k--)
{
int end=nums[numsSize-1];//创建一个临时变量将数组中最后一个数的值进行保存
for(int i=numsSize-1;i>0;i--)//将数组中的数整体右移一位
{
nums[i]=nums[i-1];//在右移的时候我们要从后向前移，我们现将倒数第二个数赋值到最后一个数的位置上，然后随着i的变化进行右移操作
}
nums[0]=end;//最后我们将之前保存的值放到以一个位置上
}
}
//但是这个存在限制，虽然这个代码没有问题，算法虽然没问题，但是超过时间限制，一但遇到大的数据，时间就变长了
但是这个题有时间的限制，一但给到了一个很大的数字，那么就要消耗很多的时间，就不满足题目要求了 将numsSize看作是N
这个代码的外层循环是k，内层循环是N-1,那么时间复杂度就是O(K*N),其实可以将K看做是N，都是变量，没啥区别，那么时间复杂度就是O(N^2)，这个时间复杂度效率很低，所以在提交的时候我们会遇到超出时间限制的错误
既然这里的时间复杂度是O(N^2),空间复杂度是O(1)
那我们能不能先办法将时间复杂度降到O(N)呢？
思路二：空间换时间
申请一个新数组，数组大小为numsSize
假设K=3, 我们将原数组的后三个数字要放到新数组的前面，然后旧数组剩下的数字我们直接搬到新数组内
申请新数组等大的空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组中
最后我们还要将新数组的值挪到原数组中，为为原数组中的每个数进行重新赋值
void rotate(int* nums, int numsSize, int k)
{
int newArr[numsSize];//创建一个数组大小和原先数组大小一样的数组
for (int i = 0; i < numsSize; ++i)
{
newArr[(i + k) % numsSize] = nums[i];
}
for (int i = 0; i < numsSize; ++i)
{
nums[i] = newArr[i];
}
}
/*1 2 3 4 5 6 7
假设k是3，那么就是原数组后3数字放到新数组的前3个位置，原先的前4个数字放到新数组的后4个数字
newArr[(i + k) % numsSize] = nums[i];
第一次时，i=0
newArr[(0 + 3) % 7] = nums[0];
newArr[(3) % 7] = nums[0];
newArr[3] = nums[0];
将原先数组的第一个赋值到新数组的第4个元素的位置
i=3时，就将原先数组的4放到新数组的最后一个位置
当i=4时，那么代码就是newArr[(4 + 3) % numsSize] = nums[4];
newArr[(7) % 7] = nums[4];
newArr[0] = nums[4];
将原先数组的下标为4的数字放到新数组的地址个位置
通过这个代码我们就实现了将原数组后k个数放到新数组的前k个位置，
将原数组的剩下的4个数据放到新数组的后4个位置
在后面的循环中，我们就将新数组中的值重新拿回到原数组内，因为我们打印的是原数组，在原数组中进行改变
*/
那么这个代码的时间复杂度是多少呢？
在第一个循环中，时间复杂度是O(N),在第二个循环中时间复杂度是O(N)
那么总的时间复杂度就是O(2N)，根据规则，消掉系数，那么最后的时间复杂度就是O(N)
这种方法的时间复杂度就达到了O(N)
但是这种思路的空间复杂度也是O(N)
我们申请了新的空间，这个空间大小是N个，那么空间复杂度就是O(N)
这个思路虽然时间复杂度降到了O(N)，但是我们是拿空间复杂度换的
思路三：
让时间复杂度为O(N),空间复杂度是O(1)
就是说明不需要额外申请空间
/*思路三
1 2 3 4 5 6 7
n=7,当前数组内数据为7
旋转的k=3
第一步将前n-k个数据逆置
这里的就是1 2 3 4
那么逆置后的结果就是4 3 2 1
第二步就是将后k个数据进行逆置
这里的就是5 6 7
逆置后的结果就是 7 6 5
那么我们经历了一二步，得到了4 3 2 1 7 6 5
最后一步我们再将整体进行逆置
得到了5 6 7 1 2 3 4
*/
/*
我们在思路三已经想到了通过三步逆置达到效果
那我们就将逆置的函数写出来
我们在需要逆置的数组设置两个下标
最左边的下标是left
最右边的下标是right
那么我们每次将left和right的下标进行交换
交换完成之后我们将left和right进行++操作，逆置下一对数字
直到我们left和right重叠了我们就停止逆置操作
那么，理论成立，实践开始
*/
//逆置函数
void reverse(int *nums, int left,int right)//逆置的数组 逆置开始的起始位置
{
while (left < right)//这里写等于就是多此一举的
{
//left和right指向的数据进行交换
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left++;
right--;
}
}
void rotate(int* nums, int numsSize, int k)
{
k = k % numsSize;//不让k超过numsSize
//前n-k个数据逆置
reverse(nums, 0, numsSize - k - 1);
//后k个数据逆置
reverse(nums, numsSize-k, numsSize-1);
//整体逆置
reverse(nums, 0, numsSize - 1);
}
/*
如果当前数组里面只有-1，但是我们要进行逆置2次，该怎么实现
我们需要对k进行处理，让k余上数组的大小，可以避免多余的逆置操作
一但逆置的次数大于数组的长度，这个步骤就起到了作用，减小了代码的运行时间
k = k % numsSize;//不让k超过numsSize
*/
第一步将前n-k个数据逆置
第二步就是将后k个数据进行逆置
最后一步我们再将整体进行逆置
我们还要对逆置的次数进行取余，保证次数要小于数组的长度
我们对这个代码进行时间复杂度的分析
reverse函数 只有一个变量tmp，那么空间复杂度就是O(1)
对于逆置函数来说，我们调用了三次
第一次调用要交换的次数是(numsSize - k) / 2
第二次交换的次数是k / 2
第三次交换的次数是numsSize / 2
那么总的交换次数就是(numsSize - k) / 2 + k / 2 + numsSize / 2。
所以时间复杂度就是O(N)
对于rotate函数来说，我们调用了三次reverse函数，因为reverse函数的时间复杂度是O(N)，那么我们的rotate函数的时间复杂度就是O(N)
对于空间复杂度来说，rotaet本身仅仅只是调用了三次逆置函数，并没有额外开辟空间创建变量
所以空间复杂度是O(1)
如果对于逆置函数的时间复杂度还不理解的话你可以这么理解
时间复杂度的定义通常是最差的情况下
那么就是我们要进行整个数组的交换，这个就是最差的情况
假设数组有N个元素，那么我们就要交换N/2次，那么我们的时间复杂度就是O(N)
