【数据结构】励志大厂版·初阶（复习+刷题）：复杂度
前引：从此篇文章开始，小编带给大家的是数据结构初阶的刷题讲解 ，此类文章将简略的包含相关知识，详细的思路拆分讲解，分析每一题的难点、易错点，看见题目如何分析，以上就是小编预备的内容，对于数据结构巩固知识的伙伴们来说，可以一试，告别冗杂的知识点，如果伙伴们发现下面哪有有问题，欢迎在评论区指出哦！小编一定会进行修改的！正文开始~
目录
知识点速览
复杂度可以分为时间复杂度、空间复杂度，它们都是度量算法优劣的算级说明，通常是估算，采用大O渐进表示法，例如如O（N）
复杂度计算：
时间复杂度是计算执行次数（估算）；空间复杂度看（变量个数+额外开辟空间数）
复杂度种类：复杂度一般有最坏、最好、平均复杂度之分，我们一般取最坏结果
计算步骤：（1）先算出准确执行次数【时间复杂度】 /（变量个数（函数内）+额外空间数量） 【空间复杂度】（2）再根据规则修改
时间复杂度、空间复杂度计算规则：
（1）用常数 1 取代运行时间中所有的加法常数（常数化1）
（2）只要高阶项，不用低阶项（取大舍小）
（3）不要高阶项系数（去系数）
计算时间复杂度
第一题
void Func1(int N) { int count = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { ++count; } } for (int k = 0; k < 2 * N; k++) { ++count; } int M = 0; while (M--) { ++count; } printf("%d\n", count); }按照上面的计算步骤：先算总的执行次数，可以算出准确次数为：N*N + 2N，再根据计算规则（取大舍小），最终得到它的时间复杂度用大O渐进表示法得到 O（N^2）
第二题
void Func2(int N) { int count = 0; for (int k = 0; k < 2 * N; k++) { ++count; } int M = 0; while (M--) { ++count; } printf("%d\n", count); }根据计算步骤，得到总的执行次数为：2N，再根据计算规则（去系数），得到最后它的时间复杂度用大O渐进表示法表示为O（N）
第三题
void Func3(int N,int M) { int count = 0; for (int k = 0; k < N; ++k) { ++count; } for (int k = 0; k < M; ++k) { ++count; } }按照计算步骤，我们先算出准确的执行次数为N+M，这里出现一个问题，如果按照取大舍小，我们是无法判断的，因为M、N都是未知数
分析：如果M较大，那就舍弃N；如果M较小，那就舍弃M；如果M等于N，那就是2M或者2N
对于这种情况，我们是都不能舍弃的，只能都保存，因此最后的时间复杂度是O（M+N）
第四题
void Func4(int N) { int count = 0; for (int k = 0; k < 100; k++) { ++count; } printf("%d\n", count); }根据计算步骤，我们先算出准确的执行次数为100次，再根据计算规则常数化1，得到最后的时间复杂度用大O渐进表示法表示为O（1）
第五题
const char* strchr(const char* str, char character) { while (*str != '\0') { if (*str == character) { return str; } ++str; } return NULL; }首先根据计算步骤，我们需要先计算准确执行次数，这题同样有一个问题，就是不知道这个字符串的长度，所以我们需要分类：
最好情况：直接出循环，1次执行次数（总执行次数）
最坏情况：假设字符串长度N，它找到底才找到，也就是N次（总执行次数）
按照计算规则，选择最坏情况，时间复杂度表示为O（N）
第六题
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; } } return; }按照计算步骤，先算总的执行次数，通过代码我们看到，还是需要分类考虑
最好情况：进入外面的 for 循环一次，里面的循环需要走 end 次，总的执行次数就是 end+1 次
最坏情况：那就只能把循环走完了！总的执行次数也就是 end^2 次
再根据计算规则，取最坏情况，得到最后的时间复杂度为O（N^2）
易错点：首先小编也经历过这个雷区！经常以为双层for循环就是N^2了，一层for循环就是N次，但是需要避雷这个，具体情况需要具体分析，我们继续向下看！
第七题
int BinarySearch(int* a, int n, int x) { assert(a); int begin = 0; int end = n; while (begin < end) { int mid = begin + ((end - begin) >> 1); if (a[mid] < x) { begin = mid + 1; } else if (a[mid] > x) { end = mid; } else return mid; } return -1; }首先我们先来计算它的总次数，根据这个代码情况，属于二分查找，还是需要分类
最好情况：那肯定就一次找到，总执行次数就是1次
最坏情况：对一组数据一直二分下去，要找的元素在数组最后一个被检查的位置
假设数组长度为N，每经过一次二分，剩余元素为N/2，经过 k 次后，剩余元素为N/ （2^k）
最坏情况也就是当剩余元素为1时，即N/（2^k）=1
解得k=log N（注意log N在复杂度里面是等于㏒以2为底N的对数的）
按照计算规则，取最坏情况，得到最后的时间复杂度为 log N
第八题
long long Factorial(size_t N) { return N < 2 ? N : Factorial(N - 1) * N; }首先根据计算步骤，计算总的执行次数，我们发现这是一个三目操作符，我先来简答解释一下它的运算思路：
如果N<2，为真就得到结果N，如果为假就得到结果 Factorial（N-1）*N
因此我们发现这是一个计算前 n 项阶层的递归函数，下面我们来分析
最好情况：直接执行一次，即计算 1 的前 n 阶层
最坏情况：假设有N个数字，那么它的阶层就是N*（N-1）*（N-2）*（N-3）......，执行了N次
根据计算规则，保留最坏情况，得到最后的时间复杂度为O（N）
计算空间复杂度
第一题
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; } } return; }首先我们按照计算步骤，先算（变量个数+额外空间数），上面总共有3个变量，没有开辟额外的空间，因此准确计算得到数量为3
再按照复杂度的计算规则（常数化1），得到最后的空间复杂度为O（1）
第二题
long long* Fibonacci(size_t n) { if (n == 0) { return NULL; } long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long)); } 首先我们按照计算步骤，先算（变量数+额外空间数），这个函数没有变量，但是它额外开辟了（n+1）的空间个数，因此总的数量就是 0+（n+1）= N+1
根据计算规则（舍大取小），得到最后的空间复杂度为O（N）
第三题
long long Factorial(size_t N) { return N < 2 ? N : Factorial(N - 1) * N; }这是一个计算 N 的阶层积的函数，比如N*（N-1）*（N-2）*（N-3）*........
每次递归都需要开辟函数栈帧空间，这里是从N-1开始调用递归函数的，因此是N-1个额外空间，没有其它变量，所以得到总的数量是0+（N-1）= N-1
根据计算规则（舍大取小），得到最后的空间复杂度为O（N）
复杂度的实际应用
话不多说我们通过两道例题来看看复杂度的实际应用
第一题
上面我们看到它的要求是时间复杂度不能超过O（N），这就是复杂度在实际的应用，题目可能会规定一定的时间复杂度、空间复杂度，下面我们开始解决这个问题！
（1）最简单的方法就是：计算 0~N 的数字之和，再减去题目中已有的数字，这样我们就找到了 那个缺失的数字，大家不能理解的话欢迎在评论区留言啊！下面我们来实现代码：
int missingNumber(int* nums, int numsSize) { int sum = 0; //求和 for (int i = 0; i <= numsSize; i++) { sum += i; } //求差 for (int i = 0; i < numsSize; i++) { sum -= nums[i]; } return sum; }（2）算法解法：我们先来了解一个运算符^ ,它比较的是二进制位，相同为0，相异为1，例如：
3的二进制是：00000000 00000000 00000000 00000011
1的二进制是：00000000 00000000 00000000 00000001
1^2^3的二进制是：00000000 00000000 00000000 00000011
将1^2^3的二进制分别与3、2的二进制去异或，这样我们就得到了中间的2的二进制
算法实现：我们把0~N的数字去分别异或，然后再将异或得到的结果与题目中数组的每个元素异或，那样就找到了少的那个数字（一般用0去开始异或，因为0与任何数异或都为那个数字）
int missingNumber(int* nums, int numsSize) { //0与任何数异或都为那个数，不会产生影响 int n = 0; //分别异或0~N的数字 for (int i = 0; i <= numsSize; i++) { n ^= i; } //再与0~N-1的数字异或，得到差值 for (int i = 0; i < numsSize; i++) { n ^= nums[i]; } return n; }第二题
首先我们我们来说一下几种解法：
（1）暴力解法：一次旋转一位数字，通过移动其余元素达到目标，但是效率上无法通过
（2）间接解法：将后k个元素拷贝到另外一个数组，再将前n-k个元素拷贝过来，再进行整体拷 贝，但是这样就不是原地了，也无法达到更高的进阶要求
（3）算法解法：我们先将数组的前n-k个元素旋转交换位置，再将后k个元素旋转位置，再整体旋 转交换位置，拿时间换取空间。例如下面这样：
void Exchange(int* p1, int* p2) { int num = *p1; *p1 = *p2; *p2 = num; } int* missNumber(int* nums, int numsSize) { //旋转前numsSize-k个元素 int i = 0; int j = numsSize - k - 1; while (i < j) { Exchange(&nums[i], &nums[j]); i++; j--; } //旋转后k个元素 i = numsSize - k - 1; j = numsSize - 1; while (i < j) { Exchange(&nums[i], &nums[j]); i++; j--; } //旋转整体 i = 0; j = numsSize - 1; while (i < j) { Exchange(&nums[i], &nums[j]); i++; j--; } return nums; }
