我们在这之前已经学了一些数据结构与算法，如何评价一个算法的好换，不同类型的算法的评价指标不一样，例如针对排序算法我们有稳定性的判断，对于数据结构我们有存储结构方式不同导致的效率不同，今天在这里博主针对考研408范围内出现的数据结构和算法进行专门的效率分析和总结，同时还会加入一些自己的分析和理解以及必须要记忆的一些结论，全是干货，大学生群体一定要收藏哦。
虽然不同的算法还有其他的评价指标，但是无论是什么算法，评价它的效率，那么它的时间复杂度和空间复杂度都是必不可少的，这里我们先复习一下时间复杂度和空间复杂度的知识点。
一个 语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n),它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。算法中基本运算(最深层循环内的语句)的频度与T(n)同数量级，因此通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度。因此，算法的时间复杂度记为T(n)= O(f(n))，式中，O的含义是T(n)的数量级，其严格的数学定义是:若T(n)和f(n)是定义在正整数集合上的两个函数，则存在正常数C和n0 ， 使得当n≥n0 时，都满足0≤T(n)≤Cf(n)。
时间复杂度的计算规则：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8IbaKVaS-1690183618694)(C:\Users\洪泽林\AppData\Roaming\Typora\typora-user-images\image-20230623143231827.png)]
算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n的函数。记为S(n)= O(g(n))，一个程序 在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一- 些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空间。
算法原地工作是指算法所需的辅助空间为常量，即0(1)。和时间复杂度的计算共用相同的计算规则。
博主觉得各位应该都练习过相关的题目了，一般的题目分析都会，这里我分享两道关于递归的简单效率分析题。
求整数n（n>=0)的阶乘的算法如下，其时间复杂度为为？
int fact(int n){
if(n<=1) return 1;
return n*fact(n-1);
}
解：对于这种含有递归算法在内的题，你可以开始写一些简单的n的实现过程，每次递归调用时fact()的参数减1，递归的出口为fact(1)，一共执行n次递归调用fact()，所以T(n)=O(n)。
下列这段程序的时间复杂度是？
int sum=0;
for(int i=1;i<n;i*=2)
for(int j=0;j<i;j++)
sum++;
解：当外层循环的变量i取不同值时，内层循环就执行多少次，因此总循环次数为i的所有取值之和。假设外层循环共执行k次，当i=1,2,4,…2k-1 (2k-1 <n≤2k )时，内层循环执行i次，因此总循环次数T=1+2+4+8+…+2k-1 =2k -1， 即n<T< 2n.时间复杂度为0(n)。
相较于第一题，第二题才是重点这里重复执行的语句
sum++部分。
| 操作 | 时间复杂度（最好） | 时间复杂度（最坏） | 时间复杂度（平均） | 说明 |
|---|---|---|---|---|
| 插入元素 | O(1) | O(n) | O(n) | 重复执行的是后移操作 |
| 删除元素 | O(1) | O(n) | O(n) | 重复执行的是前移操作 |
| 按值查找 | O(1) | O(n) | O(n) | 重复执行的是比较值部分 |
这里的最好、最坏情况比较好理解，即要插入的元素、删除的元素、查找的元素均在顺序表的第一个（最后一个），自己稍微分析一下应该可以理解。
| 操作 | 时间复杂度（最好） | 时间复杂度（最坏） | 时间复杂度（平均） | 说明 |
|---|---|---|---|---|
| 头插法建立单链表 | O(1) | O(n) | O(n) | 重复执行的是插入操作 |
| 尾插法建立单链表 | O(1) | O(n) | O(n) | 重复执行的是插入操作 |
| 按序号查找 | O(1) | O(n) | O(n) | 重复执行的是后移操作 |
| 按值查找 | O(1) | O(n) | O(n) | 重复执行的是比较和后移操作 |
| 插入结点 | O(1) | O(n) | O(n) | 重复执行的是查找操作 |
| 删除结点 | O(1) | O(n) | O(n) | 重复执行的是查找操作 |
p=p->next后移操作，在计数器的帮助下找到第n个结点。看到我的标题有的人会问，为什么不分顺序栈和链栈来考虑啦，这是因为栈的特殊性，栈和后面的队列本身就是一种特殊的线性表，栈它的出栈和进栈都是在栈顶进行操作的，而栈存在一个栈顶指针，在上面我们也理解过针对单独一个元素（结点）的插入和删除单操作而言它们的时间复杂度是O(1)，所以在栈中的出栈和进栈操作（无论是顺序栈还是单链栈）它们的时间复杂度都是常数级O(1)。
相较于栈来说，队列的相关操作略微有点不一样。队列的入队（enqueue）和出队（dequeue）操作的时间复杂度在顺序队列和链式队列中略有不同：
总之，在循环队列和链式队列中，入队和出队操作的时间复杂度都是常数级别，即 O(1)。而在普通顺序队列中，出队操作的时间复杂度为 O(n)，但这种情况在实际应用中较少使用。
关于串，408里面最重点的应该是它的模式匹配算法，它的基础操作几乎不提。
| 模式匹配方法 | 时间复杂度（最好） | 时间复杂度（最坏） | 时间复杂度（平均） | 说明 |
|---|---|---|---|---|
| 暴力匹配算法（成功） | O(m) | O((n-m+1)*m) | O(n*m) | ---- |
| 暴力匹配算法（失败） | O(n) | O((n-m+1)*m) | O(n*m) | ---- |
| KMP匹配算法（成功） | O(m) | 0(n+m) | O(n+m) | ---- |
| KMP匹配算法（失败） | O(n) | O(n+m) | O(n+m) |
模式匹配算法：
? 这里匹配存在成功和失败的情况，在可以匹配成功的情况下，最好的情况不就是从第一个开始就匹配成功的嘛，刚好比较m次就成功啦；而最坏情况下，从第一个开始就非常像，但是每次匹配到第m个失败，指针回溯到第二个，直到主串最后一个长度为m的子串才是我们要匹配的。
? 这里的n是主存的长度，m是模式串的长度，其实最坏情况下的
O((n-m+1)*m)最后就是O(n*m)，因为一般情况下，我们要匹配的主串长度n远远大于m，这里这么写是为了方便理解最好、最坏情况下的分析。
KMP匹配算法：
? 这里主要要和暴力匹配算法相比，KMP匹配算法不需要进行无谓的指针回溯，在可以匹配成功的情况下，最好情况应该也是从第一个开始匹配就直接成功，而最坏的情况下应该也是和暴力匹配算法匹配成功情况下的最坏情况一样的，但是它多了一个next(nextval)数组，可以避免回溯在某次匹配失败后i指针不用回溯，j指针根据next(nextval)数组跳转，这是一个常数项，所以单就匹配过程而言它只有O(n)，但是我们计算next(nextval)数组也是存在O(m)的时间复杂度的，因此总的时间复杂度应该是O(n+m)。在匹配失败的情况下，我们可以同样分析。
除了满二叉树或完全二叉树可以用顺序存储结构存储，一般而言，我们二叉树采用的都是链式存储结构，因此在这里我们不予讨论二叉树的顺序存储结构。
| 操作 | 时间复杂度 | 空间复杂度（最好） | 空间复杂度（最坏） | 说明 |
|---|---|---|---|---|
| 先序遍历 | O(n) | O(log n) | O(n) | ---- |
| 中序遍历 | O(n) | O(log n) | O(n) | ---- |
| 后续遍历 | O(n) | O(log n) | O(n) | ---- |
| 层次遍历 | O(n) | O(n+1/2) | O(n/2) | ---- |
对于遍历来说，无论哪种遍历，我们每个结点都访问一遍，重复执行的是访问操作，所以时间复杂度都是O(n)，这里的n是二叉树的总结点数。
这里主要难以理解的是顺序（先序、中序、后序）遍历时，空间复杂度的理解，这里我们都是用的递归的方法来实现的，不可避免的要使用递归栈的空间，递归栈的深度就是我们空间的复杂度的大小，而递归栈的深度又在这里等于二叉树的高度。这里我后面手绘一张图，大家可以理解啦。
对于层次遍历的空间复杂度来说，因为它是基于队列来完成的，在同一时刻队列里最多是二叉树的宽度（结点最多的那一层的结点数），无论是最好还是最坏情况，都是基于完全二叉树来进行的，对于总结点数为n的二叉树，最多结点的应该是最后一层，其刚好占n+1的一半。
二叉树除了这些操作之外，还有线索化的操作，这个也比较好理解，前提是理解了这里的的几种遍历的效率分析。我们知道有三种线索树，分别对应三种线索化，时间复杂度我们可以理解为把每个结点重复进行线索化，那么时间复杂度是不是就是O(n)，同理如果我们递归的进行线索化，空间复杂度是不是就和递归栈的深度也就是树的高度有关，这不就和三种循序遍历一个样嘛。
图中最重要的除了后面的图的应用，例如最小生成树的（Prim算法和Kruskal算法）、最短路径的（Dijkstra算法和Floyd算法）以及有向无环图和关键路径的求解之外，最重要的就是图的两种遍历算法（广度优先遍历和深度优先遍历）和图的拓扑排序，这里重点我们探究这三种操作。
| 操作 | 时间复杂度 | 空间复杂度（最坏） | 说明 |
|---|---|---|---|
| BFS（邻接表） | O(V+E) | O(V) | ---- |
| BFS（邻接矩阵） | O(V2 ) | O(V) | ---- |
| DFS（邻接表） | O(V+E) | O(V) | ---- |
| DFS（邻接矩阵） | O(V2 ) | O(V) | ---- |
| 拓扑排序（邻接表） | O(V+E) | O(V) | ---- |
| 拓扑排序（邻接矩阵） | O(V2 ) | O(V) | ---- |
在查找算法这里，我们按查找的数据结构进行分析，线性结构包括顺序查找、折半查找、分块查找，而树形结构包括二叉排序树、二叉平衡树、红黑树、B树、B+树，散列结构主要是散列表的哈希查找，查找算法除了我们之前分析的时间复杂度和空间复杂度之外，还引入了一个新的效率指标----平均查找长度（分查找成功、查找失败两种情况讨论。
| 查找方式 | 时间复杂度 | 空间复杂度 | 平均查找长度（成功） | 平均查找长度（失败） | 说明 |
|---|---|---|---|---|---|
| 顺序查找 | O(n) | O(1) | n + 1 2 \frac{n+1}{2} 2n+1? | n | 线性表都可 |
| 折半查找 | O(log2 n) | O(1) | (log2 (n+1))-1 | log2 (n) | 有序顺序表 |
| 分块查找 | O(s) | O(b) | LI + Ls | ----- | 二者结合 |
顺序查找：
- 空间复杂度：不需要额外的空间，就算有也是一个
temp临时变量，明显是常数级O(1)- 时间复杂度：最好情况时，线性表的第一个元素即是我们要查找的元素，时间复杂度为O(1)；最坏情况时，我们要查找的元素恰好是最后一个或者不在线性表中，此时时间复杂度为O(n)，假设查找概率相等且在线性表中随机，平均的时间复杂度为O(n/2)。
- 平均查找长度：在查找成功的情况下，我们定位到第i个元素需要比较n-i+1次关键字，在每个元素的查找概率相等时，成功的平均查找长度为 n + 1 2 \frac{n+1}{2} 2n+1?；查找失败我们显然要对所有关键字进行比较，即平均查找长度为n。
折半查找：
空间复杂度：这里我们使用的是while循环，并没有使用递归，因此不存在递归栈的问题，所以空间复杂度为常数级O(1)。
时间复杂度：在折半查找过程中，每次查找都会将搜索范围缩小一半。因此，最多需要log2(n)次查找才能找到目标元素（或确定元素不存在于数组中），所以时间复杂度为O(log n)，其中n为数组的长度。
平均查找长度：折半查找的过程可以用一个树来描述，即判定树。折半查找的判定树显然是一棵平衡二叉树，无论判断成功或失败其比较次数最多不会超过树的高度，这就涉及到平衡二叉树的树高问题了。其计算公式是** ? log ? 2 ( n + 1 ) ? \lceil\log_2(n+1)\rceil ?log2?(n+1)?**或 ? log ? 2 ( n ) ? \lfloor\log_2(n)\rfloor ?log2?(n)?+1。
? 这里需要补充的是，关于折半查找的平均查找长度我们要学会计算，表格中的数据可能教材不同表达不同，但是手算的结果是不会出现偏差的。
分块查找：
- 空间复杂度：分块查找把带查找表均匀地分为b块，每块s个记录。它的查找步骤是先进行索引查找再进行块内查找，索引查找需要建立一个索引表，其空间大小为O(b)。
- 时间复杂度：索引查找因为可以随机存取，其时间复杂度为O(1)，而块内查找采用的是顺序查找，其时间复杂度是O(s)，所以综合最后的时间复杂度是O(s)。
- 平均查找长度：分块查找的平均查找长度ASL可以看作是索引查找和块内查找的平均查找长度相加，ASL= b + 1 2 \frac{b+1}{2} 2b+1?+ s + 1 2 \frac{s+1}{2} 2s+1?= s 2 + 2 s + n 2 s \frac{s^2 + 2s + n}{2s} 2ss2+2s+n?。此时，这就相当于一个数学问题了，要使平均查找长度最小，可以取s= n \sqrt{n} n?=b，这时平均查找长度最小为 n \sqrt{n} n?+1。所以有的地方直接把O(b)=O(s)= n \sqrt{n} n?，此外我们一般不计算分块查找失败时的平均查找长度。
这里因为我们主要探索的时查找算法，针对这种树形结构我们不可避免的要去构造对应的数据结构，构造这些数据结构的函数算法效率就不分析了，我们主要分析相应的数据结构对应的查找算法效率。
| 结构 | 空间复杂度 | 时间复杂度 | 平均查找长度（成功） | 说明 |
|---|---|---|---|---|
| 二叉排序树（BST） | O(n) | O(log n) | O(n) | 动态查找 |
| 平衡二叉树（AVL） | O(n) | O(log n) | O(log n) | 一种特殊的二叉排序树 |
| 红黑树 | O(n) | O(log n) | ------ | 难！！！ |
| B树 | O(n) | O(log n) | O(log n) | 记得复习 |
| B+树 | O(n) | O(log n) | O(log n) | 同B树一样 |
二叉排序树：
- 空间复杂度：存储n个结点，空间复杂度为O(n)。
- 时间复杂度：最好情况二叉排序时完全平衡的，此时高度为O(log n)，其时间复杂度也为O(log n)；最坏情况下，二叉排序树退化为一个线性单链表，其时间复杂度为O(n)；综合其时间复杂度为O(log n)。
- 平均查找长度：类似于时间复杂度讨论的最好、最坏两种情况，其对应的平均查找长度分别为O(log n)、O(n)。
当有序表时是静态查找表时，适合用顺序表作为存储结构，而采用二分查找实现其查找操作；若有序表是动态查找表，应选择二叉排序树作为其逻辑结构。
平衡二叉树：
- 空间复杂度：同上。
- 时间复杂度：由于平衡二叉树的高度始终保持在O(log n)的范围内（n为节点数），因此查找、插入和删除操作的时间复杂度都为O(log n)。
- 平均查找长度：树形结构，其最大平均查找长度不会超过树的深度，可以证明还有n个结点的平衡二叉树的最大深度是O(log 2 n)，因此平衡二叉树的平均查找长度也为O(log 2 n)。
红黑树：
- 时间复杂度：红黑树的高度始终保持在O(log n)的范围内（n为节点数），因此查找、插入和删除操作的时间复杂度都为O(log n)。这是因为红黑树在插入和删除操作时会通过旋转和重新着色来保持树的平衡，从而确保树的高度始终接近于最低可能值。
- 空间复杂度：红黑树的空间复杂度为O(n)，因为需要存储所有的n个节点以及每个节点的颜色信息。空间复杂度主要取决于树的结构和节点数。
- 平均查找长度：不考虑这个。
散列查找（Hashing）是一种基于散列函数将关键字映射到散列表（Hash table）中的位置的查找方法。散列查找的时间复杂度、空间复杂度和平均查找长度如下：
时间复杂度：
空间复杂度：散列查找的空间复杂度为O(n)，因为需要存储所有的n个关键字以及散列表的额外空间。空间复杂度主要取决于散列表的大小和负载因子（即散列表中已填充的元素数与散列表大小的比值）。
平均查找长度（ASL）：散列查找的平均查找长度取决于散列函数的质量、冲突解决策略以及散列表的负载因子。在理想情况下，如果散列函数将关键字均匀地映射到散列表中，且负载因子较低，那么平均查找长度将接近1。然而，在实际应用中，平均查找长度可能会受到各种因素的影响，因此需要根据具体情况进行评估。
散列查找的优势在于其查找速度非常快，尤其是在关键字数量较大时。然而，它也需要一个高质量的散列函数以及合适的冲突解决策略，以确保查找性能的稳定性。
同查找算法的平均查找长度一样，在排序算法里，我们也引入了一个新的评价指标-----稳定性。
这里不考虑外部排序算法
| 算法种类 | 时间复杂度（最好） | 时间复杂度（最坏） | 时间复杂度（平均） | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 折半插入排序 | O(n) | O(n2 ) | O(n2 ) | O(1) | 是 |
| 直接插入排序 | O(n) | O(n2 ) | O(n2 ) | O(1) | 是 |
| 希尔排序 | ---- | ---- | ---- | O(1) | 否 |
| 冒泡排序 | O(n) | O(n2 ) | O(n2 ) | O(1) | 是 |
| 快速排序 | O(nlog2 n) | O(n2 ) | O(nlog2 n) | O(log2 n) | 否 |
| 简单选择排序 | O(n2 ) | O(n2 ) | O(n2 ) | O(1) | 否 |
| 堆排序 | O(nlog2 n) | O(nlog2 n) | O(nlog2 n) | O(1) | 否 |
| 2路归并排序 | O(nlog2 n) | O(nlog2 n) | O(nlog2 n) | O(n) | 是 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O? | 是 |
直接插入排序：
- 空间复杂度：直接插入排序仅用了常数个辅助单元，因而空间复杂度为O(1)。
- 时间复杂度：在排序过程中，每一趟操作可以分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态。最好情况下，表中元素已经有序，我们进行n-1趟比较但每次比较不需要移动元素，时间复杂度为O(n)；最坏情况下，表中元素刚好与排序结果相反，每次不仅需要比较的同时还要移动元素，总的时间复杂度为O(n2 )。
- 稳定性：因为它是顺序存取比较的，所以不会出现相同元素相对位置发生变化的情况。
折半插入排序：
- 空间复杂度：不需要额外的辅助空间。
- 时间复杂度：同直接插入排序的分析一样，它相较于直接插入排序仅减少了比较元素的，注意这里它修改的是第二步移动元素的比较次数而不是第一步比较关键字的次数，我们还是需要进行n-1趟关键字比较，所以它的最好情况和最坏情况结果与直接插入排序一样。
- 稳定性：也是顺序比较关键字的，所以不会出现相同元素相对位置发生变化的情况。
希尔排序：
- 空间复杂度：仅用了常数个辅助单元。
- 时间复杂度：这个是数学上的一个难题，大部分教材书并未对此有过分析，博主查阅相关资料，在最坏情况下，希尔排序的时间复杂度可以达到O(n2 )，这里大家仅供参考。
- 稳定性：会产生交换次序的问题，所以不稳定。
冒泡排序：
- 空间复杂度：仅用了常数个辅助单元。
- 时间复杂度：当最好情况时，一趟冒泡排序后的
flag依然还是false，直接跳出循环，比较次数为n-1，移动次数为0，时间复杂度为O(n)；最坏情况时，初始序列为逆序，需要进行n-1趟排序，第i趟排序需要进行n-i次比较，且每次比较需要前后移动三次，从而比较次数与移动次数均达到了n2 的级别。- 稳定性：挨个比较，肯定是稳定的。
快速排序：
- 空间复杂度：快速排序是通过递归实现的，需要借助一个递归工作栈来实现的，这个我们已经不陌生了，其容量与递归调用的最大深度一致。最好情况下可以看作一棵完全二叉树，树高O(log2 n)；最坏情况下退化到一个单链表需要n-1趟递归调用，此时栈的深度为O(n)。这里请注意，虽然一般平均情况和最坏情况的数量级一样，但是在这里平均情况下，空间复杂度还是O(log2 n)。
- 时间复杂度：快速排序的运行时间和划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含n-1个元素和0个元素时（此时排序表基本有序或逆序），此时每一程递归的工作量就大约是n，最后计算时间复杂度相当于n项求和， 达到了 O(n2 )；最好情况，递归工作栈只有O(log2 n)层，每一层工作量是O(n)，最后达到O(nlog2 n)。这里注意O(nlog2 n)和O(n2 )取平均数量级还是O(nlog2 n)。
- 稳定性：这个举个反例就行，可以自己举例证明。
简单选择排序：
- 空间复杂度：仅用了常数个辅助单元。
- 时间复杂度：与初始序列无关，固定为O(n2 )。
- 稳定性：选择排序都是不稳定的。
堆排序：
- 空间复杂度：虽然这里我们“建立”了堆这种结果，但这是分析过程，实际代码操作中我们并没有建立堆而是把排序表看成一个堆来修改它，所以仅使用了常数量级的辅助空间。
- 时间复杂度：建堆时间为O(n)，之后有n-1次向下调整，每次调整的时间复杂度为O(h)，故在最好、最坏和平均情况下，堆排序的时间复杂度均为O(nlog2 n)。
- 稳定性：选择排序都是不稳定的。
2路归并排序：
- 空间复杂度：在
merge()操作中，辅助空间刚好为n个辅助单元，所以算法的空间复杂度为O(n)。- 时间复杂度：每趟归并的时间复杂度为O(n)，共需要进行 ? log ? 2 n ? \lceil\log_2n\rceil ?log2?n?趟归并，所以最后的算法时间复杂度为O(nlog2 n)。
- 稳定性：稳定。
基数排序：
- 空间复杂度：建立r个辅助队列。
- 时间复杂度：要进行d趟分配和收集，一趟分配要O(n)，一趟收集需要O?，所以基数排序的时间复杂度是O(d(n+r))。
- 稳定性：稳定。
写完第五部分已经8000多字了，也算是对这段时间学习数据结构的一个简单总结，签后忙活了差不多一天（早上九点到晚上10点），虽然你可能看到的只是一个简单的总结表格，但是总结过程中的分析讨论，不仅要重新复习代码思路，还要分情况讨论，更要尽量写清楚。如果还有哪个部分的效率分析不理解，可以查看我的同系列专栏，结合相应的代码按照我的思路进行分析。我在CSDN上搜索了一下，都没有这个部分的总结，全是放在零散的章节里，这应该是第一份了吧。
创作不易，请大家多多支持。