本文总结了计算机专业保研面试中经常考的算法题目，也是博主当时的参考资料。 如果这篇文章对你有帮助的话，请给博客发赞以鼓励。
排序算法综述
标准时间复杂度评估：移动/交换，最优/最差/平均空间复杂度比较：是否就地排序稳定性：顺序问题常见算法插入排序(稳定) while向前移动
背心： O(N )； 最差： o(n^2) .选择排序(不稳定)每次选择最小的要素交换
一种实现方法：
最佳： o(n ) 2，最差： o(n )2)鼓泡排序)稳定化)每次比较相邻元素进行交换
o(n )最坏o ) n^2)合并排序(稳定)平均(最高，最坏) o ) nlogn )每次合并时使用临时数组，然后将数据复制到原始数组中快速排序)不稳定)平均时间复杂度为o ) nllogn 最坏情况下的时间复杂度为o )每次选择n^2)进行递归计数排序(可以是稳定的，也可以不是不稳定的)，用额外的数组记录输入数据中各数据出现的次数，按每个出现频率取出数据并使其稳定将数组分配给有限的时段，并按时段分别排序。
数组元素n、m个桶。 每桶的元素数量为k=n/m个。 如果在桶中使用快速排序，则总时间复杂度为nlog(n/m )。 如果桶的数量接近元素的数量，则桶排序的时间复杂度为o(n )。 当所有元素进入桶中时，时间复杂度退化为o(nlogn )。 基数排序(稳定)整数排序算法是将整数按比特分为不同的数字)，按比特分别进行比较。 设定10个桶，分别保存位数为0-9的要素。 遍历初始排列，将元素放入不同桶中按照桶的顺序，将桶中的元素全部取出组装成一个排列，重复2、3步至最高位。 排序结束后，将排序对象列作为n个记录，将序列中最大值的位数作为d，将数字的基数作为r，进行连锁基数排序的时间的复杂度为o(d ) nr ) ) )。 按固定间隔对希尔排序(改进的插入排序、不稳定)序列进行分组，每组直接使用插入排序； 随着间隔的减小，直到1，整个序列的有序时间复杂度变得复杂、有序化、不稳定。 shift_dowmpop从最后一个非叶节点开始。 最后一个节点提到根，shift_down根节点在最坏情况和平均情况下的时间复杂度都是o(nlogn ) p问题， NP问题) Polynnnng问题即在多项式时间内用算法可解的问题NP问题：所谓非确定型多项式时间(nondeterministicpolynomial-time )问题，虽然不知道是否存在多项式时间的求解算法， 只要多项式时间内可验证一个推测解正确性的问题任何一个NP完全问题在多项式时间内求解，则所有的NP问题都可以在多项式时间内解决NPC类问题，且所有的NP问题都可以在多项式时间复杂度内逼近
主要方法求解递推公式的时间复杂度
最短路径算法Dijkstra求解单源、负无权重最短路径松弛操作时间复杂度o(n^2) Floyd，求解多源、负无权重边的最短路径从I号顶点到j号顶点只通过前k点
Bellman-Ford求单源最短路，能判断有无负序电路是我小班教学中讲的，在每次扫描过程中，对所有边进行扫描判断
无序排列搜索中值线性选择算法：对于高速递归处理分割的两边，线性选择只对其中的一部分进行处理。 具体的步骤是通过A[p.r]随机的分割函数得到枢轴q，分割出的两个区间A[p.q-1]、A[q]、A[q 1.r]到=A[q]的元素数k=q-p 1
如果你想得到字符串本身：
当对应的字符相等时，(中p1=p2时，(中p1=p2时，)将最长公共字符串设为A[i]！=B[j]，DP[I][j]=0a[I]==b[j]，I=0|||j=0时，如果不是dp[i][j]=1，则DP [ I ] [ j ]=DP [ I-1 ]
伯特兰数适用题型：有一个规模为n的大问题a。 要解决这个问题，运用分治的思想，首先固定其中一个要素，把剩下的n-1个要素分割成两个小问题。 这两个小问题的规模分别为0，n-1，n-2，2，n-3， n将剩下的n-1个节点分割为左右子树从1到n可以构筑的BST的数量的三角形分割问题。 凸(n 2 )边形可以分割成n个三角形。 首先固定一条边)即一个三角形。 这个三角形是这个) n 2 )把方形分割成两个小的多边形递归式。
通式：
第k大的数通过最小堆，将堆的大小保持为k，o(nlogk )基于快速排序，只关注位置k，o ) n