初阶数据结构（2）:空间复杂度和复杂度算法题

Hello~,欢迎大家来到我的博客进行学习！

1.空间复杂度

根据摩尔定律，每隔一段时间晶体管的数量会增加一倍，即内存会增加，价格会降低。内存就不再是稀缺的东西，但是我们在写程序的时候仍要注意空间浪费的问题

空间复杂度是⼀个数学表达式，是对⼀个算法在运行过程中因为算法的需要额外临时开辟的空间。

空间复杂度不是程序占用了多少bytes的空间，因为常规情况每个对象大小差异不会很大，所以空间复杂度算的是变量的个数。

空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。

注意：
函数运行时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了 ，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

例如：

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，在for循环结束后，这个end就会被释放。往下看还定义了一个整型变量exchange，内层的for循环里定义了一个无符号整型 i，之后就没有额外的申请空间了，这些局部变量都在栈上。

现在我们可以统计申请的空间：无符号整型end、int类型的exchange、无符号整型i。对于这些变量，我们不能精确的计算算出占据多少空间，如整型，一个整型的变量在不同的系统上占用的空间是不一样的，比如在32位的系统上一个整型占据4个字节，在64位系统上是8个字节。则对于空间复杂的计算，我们并不能准确的计算出占据的空间，这里就与我们的时间复杂度类似，我们都不能计算出准确的数字，现在我们用大O接着推理。我们现在看向我们的代码，定义了一个int类型的exchange，我们可以把它看为一个空间，同理无符号整型end和无符号整型i我们也可以用相同的办法。依照思路我们可能会认为该冒泡排序的空间复杂度是O（3），但是依据大O阶的规则，空间复杂度应该为O（1）。

示例：
计算阶乘递归Fac的空间复杂度

long long Fac(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}

空间复杂度只关注函数体里面有没有额外申请空间。Fac（N）里面的N首先进行判断，如果N不为0，就会调用Fac（N -1），此时是在函数体里面调用的，我们需要将其统计在内。函数的调用需要创建函数栈帧，在N不为0之前会一直继续这个过程，注意在Fac（0）这里还会创建Fac（0）的函数栈帧。到这时会从Fac（0）一层层往上释放函数栈帧。

这里就会额外的申请N个空间，空间复杂度就为O（N）。我们可以看出这里递归的时间和空间复杂度部分相同。时间复杂度求解的是执行次数，空间复杂度求解的是申请的空间，在阶乘递归里面，递归需要不断的调用，调用就会涉及到执行次数，调用函数的话这里也会创建函数栈帧，所以在这里我们的空间和时间复杂度是一样的。

2. 常见复杂度对比

这里不分空间和时间，主要是看随着n的变化，复杂度趋势的对比。


根据表格和图像我们可以发现，随着n的增加，logn的变化趋势最小，同时我们可以得出变化快慢的排序（从慢到快）：logn、n、nlogn、n² 、2ⁿ、n！。则logn复杂度最优往后依次递减。
之前我提到过时间只能在程序写好之后就行评估，不能写程序之前通过理论思想进行评估。现在我们有了复杂度这个概念，我们可以在编写程序之前就可以评估出来。当然我们还可以同过下面的题目来理解这一观点，给出思路之后我们可以快速的算出复杂度是多少。

3. 复杂度算法题

3.1 旋转数组

解法一

之前我们写的代码如下；

void rotate(int* nums, int numsSize, int k) {while (k--) {int endNum = nums[numsSize - 1];for (int i = numsSize - 1; i > 0; i--) {nums[i] = nums[i - 1];}nums[0] = endNum;}
}

时间复杂度为O（n²），这里有一个可输入条件k- -，k是会影响复杂度的；内层有一个i，受到数据个数的影响，所以最终时间复杂度为O（n²）。
空间复杂度为O（1），因为这里只了申请常数个空间，这里的申请并没有受到我们数组长度和k的影响。
上次我们提交的时候显示超出了时间限制，我们现在可以理解为什么了，这里的时间复杂度是O（n²），太大了。

解法二

现在我们需要将数据复杂度降下来，我们上面的代码用了循环的嵌套，n*n =n² ，我们会想能不能把这个循环拆开，n+n = 2n，把时间复杂度降为O（n），此时我们的思路就出来了，所以在上一个知识点中，我说可以在编写程序之前就可以评估出来。

我们需要将数组进行轮转3次，这里我们并不在原数组中进行操作，而是在一个新的数组中进行操作。我们定义一个整型变量 i 作为下标，放在数组长度减k的位置，这里计算之后是放在5这里，通过i++不断的拿到后面的数字并放到新数组里面，我们此时完成了对5 、6、7的操作，我们再将1、2、3、4拿下来放置后面就行。

我们首先创建一个新的数组newArr，它的大小与原数组一致就行。借助for循环将原数组中后k个数据放到新数组前面的位置，i 从 numsSize - k 开始，i不断的++，但是 i 要小于 numsSize。我们将原数组 i 中国位置的数据给新数组 j 这个位置，j也和i一样不断的++，这样我们就把5、6、7放到了前面。
此时的代码：

void rotate(int* nums, int numsSize, int k)
{int newArr[numsSize] = { 0 };int j = 0;for (int i = numsSize - k; i < numsSize; i++){newArr[j++] = nums[i];}
}

下一步需要将原数组size-k个数据放到newArr剩下的位置，这里我们可以再写一个循环数据，但是也可以把两步合在一起。代码如下：

void rotate(int* nums, int numsSize, int k)
{int newArr[numsSize] ;for (int i = 0; i < numsSize; i++){newArr[(i + k) % numsSize] = nums[i];}
}

理解：
主要的疑点就是(i + k) % numsSize这一部分，可以代值进行理解。一开始i=0、k=3，3%7=3，此时我们就将原数组位置为0的数据赋值给了新数组位置为3的位置。之后依次写一下，我们就会发现我们先将1、2、3、4放到了新数组的后面，而5、6、7置于前面。

此时我们的新数组里面的数据是满足题目要求的，但是原数组并没有发生变化。函数的返回类型是void，所以我们需要将新数组里面的值给到原数组里面去，我们的代码就可以完成。
代码：

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];}
}

此时我们的代码的时间复杂度为O（n），空间复杂度为O（n）。时间复杂度相较于前一篇文章已经降下来了，但是空间复杂度提高了，这里我们采用了空间换时间的方式来提高算法性能。

解法三

虽然空间多，也不能进行随意的浪费。我们现在要求时间复杂度为O（N），空间复杂度度为O(1) 。
该方法需要逆置3次，如图：

从图中我们可以看出第一次我们访问0到3下标的数据，第二次我们访问4到6位置的数据，第三次我们访问0到6下标的数据。每一次访问的数据位置都不同，我们就需要begin和end来记住这些位置，并进行交换，这里设置一个int类型的tmp来交换数据。当然begin需要++，end需要 - - ，同时借助while来进行不断的访问，当begin < end
进入循环。此时我们就完成了可以进行逆置的函数reverse。

void reverse(int* arr, int begin, int end)
{while (begin < end){int tmp = arr[begin];arr[begin] = arr[end];arr[end] = tmp;begin++;end--;}
}

我们对reverse调用3次就可以完成我们需要的结果。
第一次调用，我们需要将nums，0，numSize-k-1这些参数传过去，目的是完成前n-k个数据的逆置。
第二次调用，我们需要将nums，numSize-k，numSize-1这些参数传过去，目的是完成后k个数据的逆置。
第三次调用，我们需要将nums，0，numSize-1这些参数传过去，目的是完成整体的逆置。
完成以后的代码：

void reverse(int* arr, int begin, int end)
{while (begin < end){int tmp = arr[begin];arr[begin] = arr[end];arr[end] = tmp;begin++;end--;}
}void rotate(int* nums, int numsSize, int k)
{reverse(nums, 0, numsSize - k - 1);reverse(nums, numsSize - k, numsSize - 1);reverse(nums, 0, numsSize - 1);
}

这里提示我们越界了，当nums=-1时要逆置2次 ，虽然还是-1，但是我们的代码就有点问题了。数组里面只有一个数据-1，下标为0，此时numsSize-k-1=1-2-1=-2，我们的代码效果为逆置0到-2这个区间的数据，这不是一个有效的范围。
我们现在对k进行处理，当我们的k大于我们的numsSize时，我们使k = k%numsSize。如果为上图的情况，我们的k = 2 %1 =0，begin和end都为0就不进行处理。
最后的代码：

void reverse(int* arr, int begin, int end)
{while (begin < end){int tmp = arr[begin];arr[begin] = arr[end];arr[end] = tmp;begin++;end--;}
}void rotate(int* nums, int numsSize, int k)
{k = k % numsSize;reverse(nums, 0, numsSize - k - 1);reverse(nums, numsSize - k, numsSize - 1);reverse(nums, 0, numsSize - 1);
}

现在我们已经学会了时间复杂度为O（N），空间复杂度度为O(1)的代码了。

好了，我们的数据结构知识就讲到这里。如果文章内容有误，请大佬在评论区斧正！谢谢大家！