目录
1.什么是时间复杂度和空间复杂度？
2.如何计算时间复杂度和空间复杂度？
3.有复杂度要求的算法题练习。
要想了解时间复杂度和空间复杂度，我们得知道什么是时间复杂度和空间复杂度！
有的人看到这就明白了，而有的人却去追求它的内涵：
见名知意嘛，时间复杂度不就是表示一个算法运行完所需要的时间？这还用问？错错错！
我来举一个很简单的例子：你家隔壁老王买了一台 i9 12900k 和 RTX3080Ti 整个64GB的内存，你眼瞅着你 4G的内存，洋垃圾的处理器，打开个PS都要冒烟的那种，来来来，你跟我说说能比吗？
所以简单来说，时间复杂度主要衡量的是一个算法的运行速度，在计算机科学中，算法的时间复杂度其实是一个函数，他定量描述了该算法的运行时间。一个算法执行所耗费的时间。从理论上来说，是不能被算出来的，只有你把你的程序放在机器上跑起来才能知道，但是我们不需要每个算法都上机测试，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。
我们再来看空间复杂度-->
有了上面的案例，我们要做一个有内涵的程序猿，空间复杂度绝不是一个程序占用了多少bytes的空间！
空间复杂度是用来衡量一个算法所需的额外空间！我们早期的计算机容量很小，在那个时候对空间复杂可谓是很在乎，但是现在随着计算机的发展，现在我们都是在用空间换时间，所以我们如今已经不需要再特别关注一个算法的空间复杂度！
简单做个总结:时间复杂度算的是基本操作的执行次数，空间复杂度算的是变量的个数！
有的小伙伴看到这蛮开心，懂了。
但是不着急，我们下面来看如何计算常见的空间复杂度和时间复杂度！
我们直接上代码！
// 请计算一下Func1基本操作执行了多少次？ 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 = 10; while (M--) { ++count; } printf("%d\n", count); }
算Func1执行了多少次？由上面讲的可知，要我们算的就是时间复杂度！
我们可以看到第一个大for循环执行次数是N²次，第二个for循环执行次数是2*N次，下面while 循环M是等于10的，所以会执行10次，由此可见 F(N) = N² + 2 * N + 10
但是实际中我们计算时间复杂度时，我们并不需要计算准确的执行次数，只需要大概执行次数，这里我们用大O的渐进表示法。
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
推导大O阶的方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
使用大O的渐进表示法以后，Func1的时间复杂度为：O(N²)
另外有些算法的时间复杂度存在最好、平均和最坏情况：
比如：在一个长度为N数组中搜索一个数据 x
最好情况：一次找到 最坏情况：N次找到 平均情况：N/2次找到
我们在实际中一般情况关注的是算法的最坏运行情况！，所以数组中搜索数据时间复杂度为O(N)
我们接着上代码！
// 计算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; } }
由上边可知，空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。
据题意我们可知，形参*a， n 函数内部创建了变量 end， i， exchange使用了5个额外空间，所以根据推导大O阶的方法可知空间复杂度为O(1)。
下面给大家总结下复杂度对比的图：
相信看完上边的小伙伴们已经按耐不住想要写代码了，接下来我们来看两道有复杂度要求的算法题练习题，相信你听我分析完会竖起大拇指说：妙啊！
话不多说直接上题目！！！
题目1：数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
输入：[9,6,4,2,3,5,7,0,1]
输出：8
思路1：先排序 -> 0 1 2 3 4 5 6 8 9 然后直接遍历，判断后一个数是不是比前一个数大1，就直 接找到了！但是！时间复杂度不符合题目要求，最快的排序 O(N*logN)
思路2：把0~N的数加起来结果是ret1,再把数组中的数加起来是ret2，ret1-ret2就是我们要找的数!
思路3：异或 - 数组中的数依次跟0~N的有所数异或，最后剩下的数据就是缺的那个数字！
最后我们来实现这道题的代码：
int missingNumber(int* nums, int numsSize) { int x = 0; //先跟数组中的值异或 for (int i = 0; i < numsSize; ++i) { x ^= nums[i]; } //再跟[0, N]之间的数异或 for (int j = 0; j < numsSize + 1; ++j) { x ^= j; } return x; }
看到这先别说妙，我们接着看下一道题！
题目2：给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
你可以使用空间复杂度为 O(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]
思路1： 旋转k次，先把数组nums最后一个元素放到一个临时变量tmp，然后从倒数第二个元素往后移动，再把 tmp 存的最后一个元素的值赋给数组nums[0]。缺陷：效率低，时间复杂度为O(N*K)
思路2：用空间换时间，开辟一个跟nums一样大的数组出来，先把后k个放到新数组，再把前k个接着放入新数组，时间复杂度为O(N)，但是空间复杂度为O(N)，不符合题意！
思路3：后k个逆置，前n-k个逆置，再整体逆置！
最后我们来实现这道题的代码：
void Revers(int* nums, int left, int right) { while (left < right) { int tmp = nums[left]; nums[left] = nums[right]; nums[right] = tmp; ++left; --right; } } void rotat(int* nums, int numsSize, int k) { if (k >= numsSize) { k %= numsSize; } Revers(nums, numsSize - k, numsSize - 1); Revers(nums, 0, numsSize - k - 1); Revers(nums, 0, numsSize- 1); }
