＜数据结构与算法＞效率分析专项总结_算法效率分析

一.前言

我们在这之前已经学了一些数据结构与算法，如何评价一个算法的好换，不同类型的算法的评价指标不一样，例如针对排序算法我们有稳定性的判断，对于数据结构我们有存储结构方式不同导致的效率不同，今天在这里博主针对考研408范围内出现的数据结构和算法进行专门的效率分析和总结，同时还会加入一些自己的分析和理解以及必须要记忆的一些结论，全是干货，大学生群体一定要收藏哦。

二.时间复杂度和空间复杂度

虽然不同的算法还有其他的评价指标，但是无论是什么算法，评价它的效率，那么它的时间复杂度和空间复杂度都是必不可少的，这里我们先复习一下时间复杂度和空间复杂度的知识点。

1.时间复杂度

一个 语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n),它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。算法中基本运算(最深层循环内的语句)的频度与T(n)同数量级，因此通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度。因此，算法的时间复杂度记为T(n)= O(f(n))，式中，O的含义是T(n)的数量级，其严格的数学定义是:若T(n)和f(n)是定义在正整数集合上的两个函数，则存在正常数C和n₀ ， 使得当n≥n₀ 时，都满足0≤T(n)≤Cf(n)。

时间复杂度的计算规则：

2.空间复杂度

算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n的函数。记为S(n)= O(g(n))，一个程序 在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一- 些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空间。

算法原地工作是指算法所需的辅助空间为常量，即0(1)。和时间复杂度的计算共用相同的计算规则。

3.分析一般算法

博主觉得各位应该都练习过相关的题目了，一般的题目分析都会，这里我分享两道关于递归的简单效率分析题。

1. 求整数n（n>=0)的阶乘的算法如下，其时间复杂度为为？

   int fact(int n){
   	if(n<=1) return 1;
   	return n*fact(n-1);
   }
   1
   2
   3
   4

   解：对于这种含有递归算法在内的题，你可以开始写一些简单的n的实现过程，每次递归调用时fact()的参数减1，递归的出口为fact(1)，一共执行n次递归调用fact()，所以T(n)=O(n)。

2. 下列这段程序的时间复杂度是？

   int sum=0;
   for(int i=1;i<n;i*=2)
   	for(int j=0;j<i;j++)
   		sum++;
   1
   2
   3
   4

   解：当外层循环的变量i取不同值时，内层循环就执行多少次，因此总循环次数为i的所有取值之和。假设外层循环共执行k次，当i=1,2,4,…2^k-1 (2^k-1 <n≤2^k )时，内层循环执行i次，因此总循环次数T=1+2+4+8+…+2^k-1 =2^k -1， 即n<T< 2n.时间复杂度为0(n)。

   相较于第一题，第二题才是重点这里重复执行的语句sum++部分。

三.数据结构篇

1.顺序表

这里的最好、最坏情况比较好理解，即要插入的元素、删除的元素、查找的元素均在顺序表的第一个（最后一个），自己稍微分析一下应该可以理解。

2.单链表

• 1.这里头插法（尾插法）建立单链表重复执行的是插入结点操作，插入一个结点的时间复杂度为1，插入n个结点的时间复杂度是O(n)，注意理解这里的最好（最坏）情况。
• 2.这里按序号查找重复执行的是p=p->next后移操作，在计数器的帮助下找到第n个结点。
• 3.按值查找操作同顺序表一样理解。
• 4.删除（插入）结点也比较好理解，单独处理一个结点的复杂度肯定是O(1)，但是链表不能随机存取，所以它们的主要时间复杂度是查找操作。

3.栈

看到我的标题有的人会问，为什么不分顺序栈和链栈来考虑啦，这是因为栈的特殊性，栈和后面的队列本身就是一种特殊的线性表，栈它的出栈和进栈都是在栈顶进行操作的，而栈存在一个栈顶指针，在上面我们也理解过针对单独一个元素（结点）的插入和删除单操作而言它们的时间复杂度是O(1)，所以在栈中的出栈和进栈操作（无论是顺序栈还是单链栈）它们的时间复杂度都是常数级O(1)。

4.队列

相较于栈来说，队列的相关操作略微有点不一样。队列的入队（enqueue）和出队（dequeue）操作的时间复杂度在顺序队列和链式队列中略有不同：

1. 顺序队列：顺序队列通常使用数组实现，有两个指针分别表示队头和队尾。入队操作在队尾进行，时间复杂度为 O(1)。出队操作在队头进行，理论上时间复杂度为 O(n)，因为在出队后需要将队列中剩余的元素向前移动一位。但在实际应用中，常使用循环队列来优化顺序队列，使得出队操作的时间复杂度也为 O(1)。
2. 链式队列：链式队列使用链表实现，有两个指针分别表示队头和队尾。入队操作在链表尾部进行，时间复杂度为 O(1)。出队操作在链表头部进行，时间复杂度也为 O(1)。

总之，在循环队列和链式队列中，入队和出队操作的时间复杂度都是常数级别，即 O(1)。而在普通顺序队列中，出队操作的时间复杂度为 O(n)，但这种情况在实际应用中较少使用。

5.串的匹配算法

关于串，408里面最重点的应该是它的模式匹配算法，它的基础操作几乎不提。

模式匹配算法：

​ 这里匹配存在成功和失败的情况，在可以匹配成功的情况下，最好的情况不就是从第一个开始就匹配成功的嘛，刚好比较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)。在匹配失败的情况下，我们可以同样分析。

6.二叉树

除了满二叉树或完全二叉树可以用顺序存储结构存储，一般而言，我们二叉树采用的都是链式存储结构，因此在这里我们不予讨论二叉树的顺序存储结构。

• 对于遍历来说，无论哪种遍历，我们每个结点都访问一遍，重复执行的是访问操作，所以时间复杂度都是O(n)，这里的n是二叉树的总结点数。

• 这里主要难以理解的是顺序（先序、中序、后序）遍历时，空间复杂度的理解，这里我们都是用的递归的方法来实现的，不可避免的要使用递归栈的空间，递归栈的深度就是我们空间的复杂度的大小，而递归栈的深度又在这里等于二叉树的高度。这里我后面手绘一张图，大家可以理解啦。

• 对于层次遍历的空间复杂度来说，因为它是基于队列来完成的，在同一时刻队列里最多是二叉树的宽度（结点最多的那一层的结点数），无论是最好还是最坏情况，都是基于完全二叉树来进行的，对于总结点数为n的二叉树，最多结点的应该是最后一层，其刚好占n+1的一半。

二叉树除了这些操作之外，还有线索化的操作，这个也比较好理解，前提是理解了这里的的几种遍历的效率分析。我们知道有三种线索树，分别对应三种线索化，时间复杂度我们可以理解为把每个结点重复进行线索化，那么时间复杂度是不是就是O(n)，同理如果我们递归的进行线索化，空间复杂度是不是就和递归栈的深度也就是树的高度有关，这不就和三种循序遍历一个样嘛。

7.图

图中最重要的除了后面的图的应用，例如最小生成树的（Prim算法和Kruskal算法）、最短路径的（Dijkstra算法和Floyd算法）以及有向无环图和关键路径的求解之外，最重要的就是图的两种遍历算法（广度优先遍历和深度优先遍历）和图的拓扑排序，这里重点我们探究这三种操作。

• 进行图的BFS时，无论是邻接表还是邻接矩阵，我们都借助了一个辅助队列，遍历每个顶点所以每个顶点都需要入队一次，当最坏的情况下辅助队列可能需要存储所有顶点，所以最坏情况下空间复杂度为O(V)。同理，后面的DFS我们需要借助一个递归工作栈，一样的分析。
• 采用邻接表的方式时，无论是BFS还是DFS，每个顶点都需要搜索一次，时间复杂度为O(V)，在查找该节点的邻接结点时，它的每条边至少访问一次，这里的时间复杂度为O(E)，所以总体的时间复杂度为O(V+E)。
• 采用邻接矩阵时，无论是BFS还是DFS，由于我们的边都以矩阵的形式存储，首先每个顶点同样需要搜索一次，时间复杂度为O(V)，在在查找该节点的邻接结点时，我们需要访问该节点所在的一整行，刚好又是O(V)，所以最后的时间复杂度是O(V² )。
• 针对拓扑排序的空间复杂度，我们需要一个栈或队列来存储入度为0的顶点，在某种最坏的情况下，我们需要考虑存储所有的顶点，所以其空间复杂度为O(V)。
• 针对拓扑排序的时间复杂度，由于输出每个顶点的同时还需要删掉它的边，所以也需要访问它的边，两种存储方式的不同其访问边的时间复杂度也不同。

四.查找算法篇

在查找算法这里，我们按查找的数据结构进行分析，线性结构包括顺序查找、折半查找、分块查找，而树形结构包括二叉排序树、二叉平衡树、红黑树、B树、B+树，散列结构主要是散列表的哈希查找，查找算法除了我们之前分析的时间复杂度和空间复杂度之外，还引入了一个新的效率指标----平均查找长度（分查找成功、查找失败两种情况讨论。

1.线性结构

顺序查找：

• 空间复杂度：不需要额外的空间，就算有也是一个temp临时变量，明显是常数级O(1)
• 时间复杂度：最好情况时，线性表的第一个元素即是我们要查找的元素，时间复杂度为O(1)；最坏情况时，我们要查找的元素恰好是最后一个或者不在线性表中，此时时间复杂度为O(n)，假设查找概率相等且在线性表中随机，平均的时间复杂度为O(n/2)。
• 平均查找长度：在查找成功的情况下，我们定位到第i个元素需要比较n-i+1次关键字，在每个元素的查找概率相等时，成功的平均查找长度为$\frac{n+1}{2}$；查找失败我们显然要对所有关键字进行比较，即平均查找长度为n。

折半查找：

• 空间复杂度：这里我们使用的是while循环，并没有使用递归，因此不存在递归栈的问题，所以空间复杂度为常数级O(1)。

• 时间复杂度：在折半查找过程中，每次查找都会将搜索范围缩小一半。因此，最多需要log₂(n)次查找才能找到目标元素（或确定元素不存在于数组中），所以时间复杂度为O(log n)，其中n为数组的长度。

• 平均查找长度：折半查找的过程可以用一个树来描述，即判定树。折半查找的判定树显然是一棵平衡二叉树，无论判断成功或失败其比较次数最多不会超过树的高度，这就涉及到平衡二叉树的树高问题了。其计算公式是**$\lceil {\log }_2(n+1)\rceil$**或$\lfloor {\log }_2(n)\rfloor$+1。

  ​ 这里需要补充的是，关于折半查找的平均查找长度我们要学会计算，表格中的数据可能教材不同表达不同，但是手算的结果是不会出现偏差的。

分块查找：

• 空间复杂度：分块查找把带查找表均匀地分为b块，每块s个记录。它的查找步骤是先进行索引查找再进行块内查找，索引查找需要建立一个索引表，其空间大小为O(b)。
• 时间复杂度：索引查找因为可以随机存取，其时间复杂度为O(1)，而块内查找采用的是顺序查找，其时间复杂度是O(s)，所以综合最后的时间复杂度是O(s)。
• 平均查找长度：分块查找的平均查找长度ASL可以看作是索引查找和块内查找的平均查找长度相加，ASL=$\frac{b+1}{2}$+$\frac{s+1}{2}$=$\frac{s^2+2s+n}{2s}$。此时，这就相当于一个数学问题了，要使平均查找长度最小，可以取s=$\sqrt{n}$=b，这时平均查找长度最小为$\sqrt{n}$+1。所以有的地方直接把O(b)=O(s)=$\sqrt{n}$，此外我们一般不计算分块查找失败时的平均查找长度。

2.树形结构

这里因为我们主要探索的时查找算法，针对这种树形结构我们不可避免的要去构造对应的数据结构，构造这些数据结构的函数算法效率就不分析了，我们主要分析相应的数据结构对应的查找算法效率。

二叉排序树：

• 空间复杂度：存储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 ₂ n)，因此平衡二叉树的平均查找长度也为O(log ₂ n)。

红黑树：

• 时间复杂度：红黑树的高度始终保持在O(log n)的范围内（n为节点数），因此查找、插入和删除操作的时间复杂度都为O(log n)。这是因为红黑树在插入和删除操作时会通过旋转和重新着色来保持树的平衡，从而确保树的高度始终接近于最低可能值。
• 空间复杂度：红黑树的空间复杂度为O(n)，因为需要存储所有的n个节点以及每个节点的颜色信息。空间复杂度主要取决于树的结构和节点数。
• 平均查找长度：不考虑这个。

3.散列结构

散列查找（Hashing）是一种基于散列函数将关键字映射到散列表（Hash table）中的位置的查找方法。散列查找的时间复杂度、空间复杂度和平均查找长度如下：

时间复杂度：

• 最好情况下，散列函数将关键字均匀地映射到散列表中，没有发生冲突，查找的时间复杂度为O(1)。
• 最坏情况下，所有关键字都映射到同一个位置，导致冲突严重，查找的时间复杂度为O(n)（n为关键字数量）。
• 平均情况下，散列查找的时间复杂度接近O(1)，但这取决于散列函数的质量和冲突解决策略。

空间复杂度：散列查找的空间复杂度为O(n)，因为需要存储所有的n个关键字以及散列表的额外空间。空间复杂度主要取决于散列表的大小和负载因子（即散列表中已填充的元素数与散列表大小的比值）。

平均查找长度（ASL）：散列查找的平均查找长度取决于散列函数的质量、冲突解决策略以及散列表的负载因子。在理想情况下，如果散列函数将关键字均匀地映射到散列表中，且负载因子较低，那么平均查找长度将接近1。然而，在实际应用中，平均查找长度可能会受到各种因素的影响，因此需要根据具体情况进行评估。

散列查找的优势在于其查找速度非常快，尤其是在关键字数量较大时。然而，它也需要一个高质量的散列函数以及合适的冲突解决策略，以确保查找性能的稳定性。

五.排序算法

同查找算法的平均查找长度一样，在排序算法里，我们也引入了一个新的评价指标-----稳定性。

这里不考虑外部排序算法

1.插入排序

直接插入排序：

• 空间复杂度：直接插入排序仅用了常数个辅助单元，因而空间复杂度为O(1)。
• 时间复杂度：在排序过程中，每一趟操作可以分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态。最好情况下，表中元素已经有序，我们进行n-1趟比较但每次比较不需要移动元素，时间复杂度为O(n)；最坏情况下，表中元素刚好与排序结果相反，每次不仅需要比较的同时还要移动元素，总的时间复杂度为O(n² )。
• 稳定性：因为它是顺序存取比较的，所以不会出现相同元素相对位置发生变化的情况。

折半插入排序：

• 空间复杂度：不需要额外的辅助空间。
• 时间复杂度：同直接插入排序的分析一样，它相较于直接插入排序仅减少了比较元素的，注意这里它修改的是第二步移动元素的比较次数而不是第一步比较关键字的次数，我们还是需要进行n-1趟关键字比较，所以它的最好情况和最坏情况结果与直接插入排序一样。
• 稳定性：也是顺序比较关键字的，所以不会出现相同元素相对位置发生变化的情况。

希尔排序：

• 空间复杂度：仅用了常数个辅助单元。
• 时间复杂度：这个是数学上的一个难题，大部分教材书并未对此有过分析，博主查阅相关资料，在最坏情况下，希尔排序的时间复杂度可以达到O(n² )，这里大家仅供参考。
• 稳定性：会产生交换次序的问题，所以不稳定。

2.交换排序

冒泡排序：

• 空间复杂度：仅用了常数个辅助单元。
• 时间复杂度：当最好情况时，一趟冒泡排序后的flag依然还是false，直接跳出循环，比较次数为n-1，移动次数为0，时间复杂度为O(n)；最坏情况时，初始序列为逆序，需要进行n-1趟排序，第i趟排序需要进行n-i次比较，且每次比较需要前后移动三次，从而比较次数与移动次数均达到了n² 的级别。
• 稳定性：挨个比较，肯定是稳定的。

快速排序：

• 空间复杂度：快速排序是通过递归实现的，需要借助一个递归工作栈来实现的，这个我们已经不陌生了，其容量与递归调用的最大深度一致。最好情况下可以看作一棵完全二叉树，树高O(log₂ n)；最坏情况下退化到一个单链表需要n-1趟递归调用，此时栈的深度为O(n)。这里请注意，虽然一般平均情况和最坏情况的数量级一样，但是在这里平均情况下，空间复杂度还是O(log₂ n)。
• 时间复杂度：快速排序的运行时间和划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含n-1个元素和0个元素时（此时排序表基本有序或逆序），此时每一程递归的工作量就大约是n，最后计算时间复杂度相当于n项求和， 达到了 O(n² )；最好情况，递归工作栈只有O(log₂ n)层，每一层工作量是O(n)，最后达到O(nlog₂ n)。这里注意O(nlog₂ n)和O(n² )取平均数量级还是O(nlog₂ n)。
• 稳定性：这个举个反例就行，可以自己举例证明。

3.选择排序

简单选择排序：

• 空间复杂度：仅用了常数个辅助单元。
• 时间复杂度：与初始序列无关，固定为O(n² )。
• 稳定性：选择排序都是不稳定的。

堆排序：

• 空间复杂度：虽然这里我们“建立”了堆这种结果，但这是分析过程，实际代码操作中我们并没有建立堆而是把排序表看成一个堆来修改它，所以仅使用了常数量级的辅助空间。
• 时间复杂度：建堆时间为O(n)，之后有n-1次向下调整，每次调整的时间复杂度为O(h)，故在最好、最坏和平均情况下，堆排序的时间复杂度均为O(nlog₂ n)。
• 稳定性：选择排序都是不稳定的。

4.其他

2路归并排序：

• 空间复杂度：在merge()操作中，辅助空间刚好为n个辅助单元，所以算法的空间复杂度为O(n)。
• 时间复杂度：每趟归并的时间复杂度为O(n)，共需要进行$\lceil {\log }_{2}n\rceil$趟归并，所以最后的算法时间复杂度为O(nlog₂ n)。
• 稳定性：稳定。

基数排序：

• 空间复杂度：建立r个辅助队列。
• 时间复杂度：要进行d趟分配和收集，一趟分配要O(n)，一趟收集需要O®，所以基数排序的时间复杂度是O(d(n+r))。
• 稳定性：稳定。

六.说明

写完第五部分已经8000多字了，也算是对这段时间学习数据结构的一个简单总结，签后忙活了差不多一天（早上九点到晚上10点），虽然你可能看到的只是一个简单的总结表格，但是总结过程中的分析讨论，不仅要重新复习代码思路，还要分情况讨论，更要尽量写清楚。如果还有哪个部分的效率分析不理解，可以查看我的同系列专栏，结合相应的代码按照我的思路进行分析。我在CSDN上搜索了一下，都没有这个部分的总结，全是放在零散的章节里，这应该是第一份了吧。

创作不易，请大家多多支持。

数据结构与算法专栏