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

时间复杂度：不是计算时间，是计算大概的运算次数；O(1)代表运算的次数是常数个。

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

时间复杂度：

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

另外有些算法的时间复杂度存在最好、平均和最坏情况：

最坏情况：任意输入规模的最大运行次数(上界)

平均情况：任意输入规模的期望运行次数

最好情况：任意输入规模的最小运行次数(下界)

例如：在一个长度为N数组中搜索一个数据x

最好情况：1次找到

最坏情况：N次找到

平均情况：N/2次找到

在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

例1：

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

例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，=N，X=log，时间复杂度为O(log)

   并且对于需要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( )。

复杂度对比：

空间复杂度：

不计算空间，计算大概定义的变量个数(哪怕类型不同)；也是使用大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( )；所以是不满足题意的；这里的代码读者可以自己尝试写一写；如果写不出来可以来@我！

例题2：旋转数组

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。这道题来源于力扣的第189.旋转数组传送门；例如：输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 实际上这里是右转。解析：

这道题目我曾遇到过类似的，旋转数组包括左转和右转，无论是哪种旋转方式，我们都要掌握；如果不理解的小伙伴可以看我的这一篇博客传送门；这篇博客里有思路的详解，这里就不在多赘述，直接上代码：

具体代码：

总结：

数据结构第一课就结束啦！相信大家看完上面的例题，就会对时间复杂度和空间复杂度有一定的理解。以后会坚持更新数据结构的，下一篇让我们一起学习线性表--->顺序表；欢迎大家一起学习进步！！！下面送给大家一张美照，放松一下眼睛吧。