前言：Hello！大家好，我是@每天都要敲代码，从今天起开始更新数据结构了，看到很多大佬都早已开始更数据结构的博文，所以我也要准备更新数据结构，向大佬看齐；接下来我们一起学习第一课，时间复杂度和空间复杂度；在学这个之间我们首先要弄明白这两个的定义：

时间复杂度：不是计算时间，是计算大概的运算次数；O(1)代表运算的次数是常数个。
空间复杂度：不是计算空间，是计算大概定义的变量个数；O(1)代表定义常数个变量，并不是单只1个。

时间复杂度：

算法中的基本操作的执行次数======》大O的渐进表示法

另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

例1：

解析：我们要求func1函数的时间复杂度，首先我们要分析代码的组成成分；第一部分是两个for循环，时间复杂度也就是O( $N^{2}$ )；第二部分是O(2)；第三部分是循环10次，时间复杂度为O(1)；所以func1函数的执行次数是：F(N)= $N^{^2}$ +2+10，时间复杂度为O( $N^{^2}$ )+O(2) +O(1) ；我们只取幂数高的，并且省略其前面的系数，最终时间复杂度就为O( $N^{2}$ )。

例2：

解析：第一个循环时间复杂度为O(M)；第二个时间复杂度为O(N)；因为M，N都是未知数，我们也并不知道M、N的大小关系；所以func2()函数的时间复杂度为O(M+N)。假设给了条件呢？M远大于N，此时就是O(N)；M和N差不多大，此时就是O(M)或O(N)啦。

例3：

解析：我们发现k的取值范围是具体常数，所以对于func3时间复杂度就是O(1)。

例4：strchr在一个串中查找给定字符的第一个匹配之处

解析： 我们发现这道题就有意思了，如果我们第一次就查到了，时间复杂度就是O(1)；如果到尾才插到或者到尾都没查到，时间复杂度为O(N)；如果是在中间查到，时间复杂度为O(N/2)，其实也就是O(N)；那么我们取哪一种呢？当然是最坏的情况啦！所以这道题的时间复杂度为O(N)。

例5：冒泡排序的时间复杂度？

解析：对于冒泡排序，最好的情况是我们遍历一遍数组，发现都不需要交换，n-1次，时间复杂度为O(N)；如果最坏的情况下，需要排n-1趟那么一共要交换的次数是1+2+3+….n-1===>n(n-1)/2时间复杂度为O( $N^{2}$ )

例6：二分查找(折半查找)的时间复杂度？

解析：最好情况下，第一次就找到了，时间复杂度为O(1)；最复杂的情况，我们每次查好都少减一半数据；假设找了X次，那么1*2*2*…..2 = N， $2^{X}$ =N，X=log $2^{N}$ ，时间复杂度为O(log $2^{N}$ )
并且对于需要left和right状态的时候，要保持一致，
比如：int left=0; int right = strlen(arr)======>while(left<right) 都是开区间
int left=0; int right = strlen(arr)-1======>while(left<=right) 都是闭区间

例7：计算阶乘递归Factorial的时间复杂度？
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N – 1) * N; //这里用的三目运算符
}
解析：对于递归函数，总共递归了N次 = 递归次数*每次递归运算的次数，每次递归函数是一次；所以整体时间复杂度是O(N)

例8：计算斐波那契数列Fibonacci(递归)的时间复杂度
#include <stdio.h>
long long Fibonacci(size_t N)
{
   return N < 2 ? N : Fibonacci(N – 1) + Fibonacci(N – 2);
}
int main()
{
   printf(“%lld\n”, Fibonacci(10));
   return 0;
}
解析：这里比较复杂需要画图去理解，这里我们为了画图方便，我们就假设求Fibonacci(5)；

我们发现其实是一个类似于二叉树的形式，所以用递归方式求斐波那契数列的时间复杂度

O( $2^{N}$ )。

复杂度对比：

空间复杂度：

不计算空间，计算大概定义的变量个数(哪怕类型不同)；也是使用大O渐进表示法

注意：时间是累计的，空间是不累计的；循环走了N次，重复利用的是一个空间。

比如：1.冒泡排序，定义了常数个变量，这里实参和形参都要算上；空间复杂度为O(1)

2. 用malloc动态开辟空间时，一般都是O(N)

3.上面例7递归方式求阶乘；对于递归函数，递归几次，空间复杂度就是多少；值得注意的是，递归往下走的时候，所创建的空间不会被销毁，但是回朔的过程会销毁！

补充两个经典例题：

例题1：消失的数字

数组nums包含从0到n的所有整数，但其中缺一个。请找出那个缺失的整数，在O(n)完成，例如：输入[3,0,1]; 输出2。传送门

方法1：和-和

解析：

当你读完题目时，你可能没有读懂什么意思，也没什么思路；但是当你看完他给你的例子，我相信你的思路是不是来了呢？[3,0,1]是3个数，其实就是arr[3]={3,0,1}，缺少个2；3下标从0开始就是{0,1,2,3}；这样是不是有点想法？求和相减不就好了吗？

具体代码：

方法2：异或(^)

解析：

有了上面的思路，我们发散一下思维，我们和-和的形式，是不是相当于把相同的数据减掉，最终保留的是只出现一次的数据；那我们是不是就可以使用异或来求？按位异或：相同为0，相异为1；所以两个相同数异或就是0；0与任何数异或还是任何数！！！

具体代码：

总结：

这道题很简单，也很容易理解；如果没有时间复杂度O(N)的限制，其实我们还可以有第三种方法：先排序，然后遍历整个数组，看后一个数是不是比前一个数大1；这样同样能找出来；但是用到排序的话，最快的排序—快排时间复杂度也要O( $N*log^{N}$ )；所以是不满足题意的；这里的代码读者可以自己尝试写一写；如果写不出来可以来@我！