前言
1.什么是数据结构?
数据结构是计算机存储,组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合.
✨通俗来讲：数据结构是在内存中以某一种组织来管理数据
组织：树形结构，链式结构…
管理：增删查改
2.什么是算法?
算法就是定义良好的计算过程,它取一个或者一组值作为输入,并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果
比如说排序/二分查找
3.时间复杂度
1.算法的时间复杂度是一个数学函数式
2.算法中的基本操作的执行次数,为算法的时间复杂度
3.1 实例1:请计算一下Func1中++count语句总共执行了多少次？
时间复杂度函数式–>衡量它跑多少次
F(N)=NN+2N+10 （Func1准确的基本操作执行次数）
注意：实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，也就是说估算出它是哪个level级别的，那么这里我们使用大O的渐进表示法。
大O的渐进表示法–>估算
大O的渐进表示法总结
1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中，只保留最高阶项
3.如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶
4.有些算法的时间复杂度存在最好情况，最坏情况，平均情况，在实际中一般情况关注的是算法的最坏运行情况，这样做的目的是降低预期，底线思维
其中：
最好情况：1次找到
最坏情况：最大运行次数找到
平均情况=把各种情况全都覆盖/查找次数
实例2:计算Func2的时间复杂度
答案：O(N)
准确的来说是2N+10
N越大，N的系数对结果的影响越小，忽略系数，时间复杂度用大O渐进法表示为O(N)
实例3:计算Func3的时间复杂度？
答案：O(M+N)
无法评估M,N的大小关系，只能写成O(M+N)
如果给出M远大于N,结果可写成O(M)
如果给出N远大于M,结果可写成O(N)
实例4:计算Func4的时间复杂度？
答案：O(1)
准确的来说是100,但是只要执行次数是常数，在时间复杂度面前就用1代替
✨O(1)代表的不是1次，代表的是常数次
实例5:计算strchr的时间复杂度？
答案：O(N)
相当于在字符数组里面查找一个字符的算法
while(*str){ if(*str==character) return str; else ++str; }
另外有些算法的时间复杂度存在最好,平均和最坏的情况:
最坏情况:任意输入规模的最大运行次数(上界)
平均情况:任意输入规模的期待运行次数
最好情况:任意输入规模的最小运行数(下界)
在实际中一般情况关注的是算法的最坏运行情况
所以数组中搜索数据时间复杂度为O(N)
(降低预期,底线思维)
实例6:计算BubbleSort的时间复杂度？(冒泡排序）
答案：时间复杂度O(N^2)
准确的时间复杂度:
比较次数
第一趟 n-1次
第二塘 n-2次
第三趟 n-3次
…
4
3
2
余两数 1次
每个次数构成一个等差数列,准确的总次数=N*(N-1)/2
时间复杂度O(N^2)
✨补充知识点：快速排序qsort的时间复杂度是 O(N*logN)
对比冒泡排序和快速排序的效率
实例7:二分查找的时间复杂度
答案：
区间有N个值，每找一次就缩小一半
找一次 剩余N/2个值
找两次 剩余N/2/2个值
… …
找了多少次，就要除以多少个2
假设找了x次,那么除以x个2
N/2/2/2/2…/2=1
N / (2^x) =1
N=2^x
x=log2(N)
二分查找的效率有多高，下面来对比一下暴力查找（顺序查找）和二分查找
实例8:计算阶乘递归Fac的时间复杂度
答案是O(N)
Fac(N)
调用
Fac(N-1)
调用
Fac(N-2)
…
…
Fac(2)
调用
Fac(1)
调用
Fac(0)
实际总共调用了N+1次,每一次里面判断一次,加起来就是O(N)
变形：在函数中加入一个for循环
答案：时间复杂度O(N^2)
每次调用的时候里面判断也可以算一次,但是影响很小可以忽略
所以大概算一下量级是O(N^2)
实例9:计算斐波那契递归Fib的时间复杂度
答案：时间复杂度为O(2^N)
斐波那契数递归的过程：
时间复杂度计算过程:
今日寄语：
那些看似不起波澜的日复一日，终会在某天让你看见拿到坚持的意义。
共勉🐍
