计算机专业保研面试备考：计算机算法（必看）

分手后的思念是犯贱 2023-01-23 11:56 20阅读 0赞

本文总结了计算机专业保研面试中较为常考的算法题目，也是博主当年的备考材料。如果这篇文章对你有帮助，请给博主点个赞鼓励一下吧。

*  排序算法
    
     *  综述
        
        ![eac6d20d75039f94becb297e16d4364f.png][]
     *  评价标准
        
         *  时间复杂度：比较+移动/交换，最好/最坏/平均
         *  空间复杂度：是否原地排序
         *  稳定性：顺序的问题
     *  常见算法
        
         *  插入排序（稳定）
            
             *  通过while向前移动
                
                ![54ff3efe9b9c74ce14e43d9cbb4f7315.png][]
             *  ![79f91af28a8d20dd510ceb85a8db7928.png][]
             *  最好：O(n)；最坏：O(n^2).
         *  选择排序（不稳定）
            
             *  每次选择最小的元素交换
                
                ![cbcd5e35f0a673e1a803ae95622b17fc.png][]
             *  一种实现方式：
                
                ![3f77826520cde4140ad1fa2eae150156.png][]
             *  最好：O(n^2)，最坏：O(n^2)
         *  冒泡排序（稳定）
            
             *  每次比较相邻元素并交换
                
                ![346be9adeae0b1bbdc6e1712516d9f92.png][]
             *  ![1063b18aab86d423692f7750e66c67b2.png][]
             *  最好O(n) 最坏O(n^2)
         *  归并排序（稳定）
            
             *  平均、最好、最坏：O(nlogn)
             *  分+排+合
             *  每次合并都要用到一个临时数组，之后将数据拷贝到原数组
         *  快速排序（不稳定）
            
             *  平均时间复杂度是 O（nlogn），最坏情况下的时间复杂度是 O（n^2）
             *  每次选择第一个为基准数，两个哨兵i、j，每次先移动j；递归
         *  计数排序（可以稳定，可以不稳定）
            
             *  不稳定：用额外的数组记录输入数据中各数据出现的次数，然后将数据按出现频数取出
             *  稳定：将count改为累计，使用临时数组存储结果，反向填充数组
         *  桶排序（稳定）
            
             *  桶代表的是一个区间范围。将数组分配到有限量的桶里，然后对每个桶分别进行排序。
                
                ![db6a35a98a5640bbe609b6730fe06713.png][]
             *  数组元素n，m个桶。平均每个桶的元素个数为k = n/m个。如果在桶内我们使用快速排序，总的时间复杂度即为nlog(n/m)。如果桶的数量接近元素的数量，桶排序的时间复杂度就是O(n) 了。如果所有的元素都到了一个桶了，时间复杂度退化成 O(nlogn) 。
         *  基数排序（稳定）
            
             *  整数排序算法，将整数按位切割成不同的数字（分桶），然后按每个位数分别比较。
                
                 *  设定10个桶，分别存放位数为0-9的元素。
                 *  遍历初始序列，将元素放入不同的桶中
                 *  按照桶的顺序，把桶中元素全部拿出来重新组装成一个序列
                 *  重复2、3步骤，直到最高位。即可完成排序
             *  设待排序列为n个记录，序列中最大值的位数为d，数字的基数为 r，则进行链式基数排序的时间复杂度为O(d(n+r))。
         *  希尔排序（改进的插入排序，不稳定）
            
             *  把序列按一定间隔分组，对每组使用直接插入排序；随着间隔减小，一直到1，使得整个序列有序
             *  时间复杂度复杂
         *  堆排序（不稳定）
            
             *  建堆：从最后一个非叶结点开始shift\_dowm
             *  pop：最后一个结点提到根部，shift\_down根节点
             *  最好最坏以及平均情况下的时间复杂度均为O(nlogn)
 *  P问题、NP问题
    
     *  P问题：Polynomial-time问题，能够在多项式时间内用算法求解的问题
     *  NP问题：非确定型多项式时间（nondeterministic polynomial-time）问题，指不确定是否存在多项式时间的求解算法，但可以在多项式时间内验证一个猜测解的正确性的问题
     *  任意一个NP完全问题如果能够在多项式时间内解决，则所有的NP问题都能在多项式时间内解决
     *  NPC类问题（Nondeterminism Polynomial complete），指所有NP问题都能在多项式时间复杂度内归约到的NP问题
     *  NP难问题，指所有NP问题都能在多项式时间复杂度内归约到的问题
     *  ![9e72cbea1da2fdbaaff50d8c07cee801.png][]
 *  主方法
    
     *  求解递推式的时间复杂度
        
        ![4a8ecc054e142ae5d7aee7b01a8f4511.png][]
        
        ![a3d6c6feb91731f0fcd6ac9adbb31e0b.png][]
 *  最短路径算法
    
     *  Dijkstra
        
         *  求单源、无负权的最短路
         *  松弛操作
         *  时间复杂度O(n^2)
     *  Floyd
        
         *  求多源、无负权边的最短路
         *  从i号顶点到j号顶点只经过前k号点的最短路程
            
            ![1d23ba177425b7cfdbda63b0206412bb.png][]
     *  Bellman-Ford
        
         *  求单源最短路，可以判断有无负权回路
         *  就是我小班课讲过的东西：在每次的遍历过程中，对所有的边进行遍历判断
            
            ![1770d2a8e0818869123dc33d881abf86.png][]
 *  无序数组寻找中位数
    
     *  线性选择算法：快排递归处理划分的两边，而线性选择只对其中的一个部分进行处理。具体步骤为：
        
         *  A\[p...r\]通过随机划分函数得到枢轴q
         *  根据划分的两个区间A\[p...q-1\],A\[q\],A\[q+1...r\]
         *  然后判断<=A\[q\]的元素数量k=q-p+1 与 需要寻找的第i小的关系，决定处理左面还是右面
         *  O(n)
 *  最长公共子序列
    
     *  c\[i\]\[j\]表示串1前i个字符、串2前j个字符的最长公共子序列长度
        
        ![c96664cbb3b8fe8be1e3493b551e0ef9.png][]
     *  如果想要得到串本身：
        
        ![54c3a9cbafc08cd494a4b859e5581686.png][]
        
         *  在对应字符相等的时候，用↖标记
         *  在p1 >= p2的时候，用↑标记
         *  在p1 < p2的时候，用←标记
 *  最长公共字串
    
     *  当A\[i\] != B\[j\]，dp\[i\]\[j\] = 0
     *  当A\[i\] == B\[j\]，
        
         *  若i = 0 || j == 0，dp\[i\]\[j\] = 1
         *  否则 dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] + 1
 *  01背包问题
    
     *  ![0ba522efcb7ebec8c2af4dd1e71c3190.png][]
 *  卡特兰数
    
     *  适用题型：有一个大问题A，规模为n，要解决这个问题，可以用分治的思想，首先固定其中某一个元素，将剩下的n-1个元素拆分成两个小问题，这两个小问题的规模分别是(0,n-1) (1,n-2) (2,n-3) ... (n-1,0)
     *  如：
        
         *  二叉树计数，n个结点的二叉树，首先固定根节点，将剩下的n-1个结点拆分给左右子树
         *  从1到n可以构建的BST的数目
         *  三角形划分问题，凸(n+2)边形可以划分为n个三角形，首先固定一条边（即一个三角形），这个三角形将这个(n+2)边形拆分成两个更小的多边形
     *  递推式：
        
        ![8ef81cd05703997d4b92a4d4d9c6d140.png][]
     *  通项公式：
        
        ![7f9bb468463dc226944506c911164d9c.png][]
 *  第K大的数
    
     *  借助最小堆，保持堆的大小为K，O(nlogk)
     *  基于快速排序，只关注位置k，o(n)

[eac6d20d75039f94becb297e16d4364f.png]: /images/20221004/6657f3404f6e458cb2bf2a70d1e20d17.png
[54ff3efe9b9c74ce14e43d9cbb4f7315.png]: /images/20221004/51621f152068481d8220d7e40b0fac57.png
[79f91af28a8d20dd510ceb85a8db7928.png]: /images/20221004/4a16e5533d6b416197df81423875f3ea.png
[cbcd5e35f0a673e1a803ae95622b17fc.png]: /images/20221004/3cf77271ea6a409cadc9f7a50daaa626.png
[3f77826520cde4140ad1fa2eae150156.png]: /images/20221004/e83fd997246c4423bbdcd40416a6818f.png
[346be9adeae0b1bbdc6e1712516d9f92.png]: /images/20221004/e8c446e6d75f4e9e9d810cc1dc534700.png
[1063b18aab86d423692f7750e66c67b2.png]: /images/20221004/7a05d35d666d4bf5b8decd415c75f627.png
[db6a35a98a5640bbe609b6730fe06713.png]: /images/20221004/bcecb0494f3a4094b3713c0a36d33780.png
[9e72cbea1da2fdbaaff50d8c07cee801.png]: /images/20221004/375c655ba4f54647bfc3b78c1c90f900.png
[4a8ecc054e142ae5d7aee7b01a8f4511.png]: /images/20221004/cea0c071c5de47958b9af180c2b3b699.png
[a3d6c6feb91731f0fcd6ac9adbb31e0b.png]: /images/20221004/a3d8a9dc3ee14bb8b44bf643c22f85dd.png
[1d23ba177425b7cfdbda63b0206412bb.png]: /images/20221004/e6b7751fc6184fb0ba53db4427cf2e3f.png
[1770d2a8e0818869123dc33d881abf86.png]: /images/20221004/5c0e7a56c5294fcb9a8c3837c1c96f61.png
[c96664cbb3b8fe8be1e3493b551e0ef9.png]: /images/20221004/4f8d36e8b16c4e2197758003d0569b00.png
[54c3a9cbafc08cd494a4b859e5581686.png]: /images/20221004/f6a60e8c37ea4b33b4673e633bd7d50c.png
[0ba522efcb7ebec8c2af4dd1e71c3190.png]: /images/20221004/57ed58f84d2f4323b946ac45de3a5361.png
[8ef81cd05703997d4b92a4d4d9c6d140.png]: /images/20221004/e4dbf3e44e8d4e268888b0a9c736d6f3.png
[7f9bb468463dc226944506c911164d9c.png]: /images/20221004/280451a019fc49a0aec6f0a651935c0c.png