算法复习易错点总结

1、一、判断题（F）一个完全多项式近似方案是一个近似方案A，其中每一个算法A，在输入实例I的规模的多项式时间内运行。（F）若近似算法A求解某极小化问题一实例的解为s，且已知该问题的最优解为s/3，则该近似算法的性能比为3。（Y）若P2多项式时间转化为P1，则P2至少与P1一样难。（F）快速排序算法的平均时间复杂度是O（nlogn），使用随机化快速排序算法可以将平均时间复杂度降得更低。（Y）若f（n）=O（g（n），则g（n）=Omiga（f（n）。（Y）类似这种关系均成立。（T）O(f(n)+O(g(n) = O(maxf(n),g(n)（F）随机化快速排序的worst case 出现于输入数组恰

2、好为已按非降序排列的情况（假设输出的排序结果也要求是非降序）。（出现在所有数都相同的情况下）二、问答题1、二叉查找树属于减治策略的三个变种中哪一个应用？什么情况下二叉查找树表现出最差的效率？此时的查找和插入算法的复杂性如何？答：减可变规模；树是严格歪斜的情况下，效率最差；此时查找和插入效率均为大theta（n）。2、构造AVL树和2-3树的主要目的是什么？它们各自有什么样的查找和插入的效率？答：二叉查找树仅在平均情况下效率比较高，为了弥补这一缺点，产生了这两种方案。能使树的左右子树更加平衡，目的是减小树的层数，使平均搜索效率更高。AVL：最差情况下，查找和插入操作的效率属于(lgn)。2-3树

3、：无论在最差情况还是在平均情况，查找、插入和删除的时间效率都属于（log n)。3、写出0/1背包问题的一个多项式等价的判定问题，并说明为什么它们是多项式等价的。答：是否存在价值至少为k的可行解。若原问题有多项式时间内的算法可以解决，则该判定问题有解。若判定问题在多项式时间内有解，原问题也可以转化为判定问题。因此成为多项式等价。4、何谓伪多项式算法？如何将一Monte Carlo算法转化为Las Vegas算法？以子集和问题为例说明伪多项式时间算法 和FPAS可以有的关系。答：单概率为0的Monte Carlo算法就是Las Vegas算法。算法的时间复杂度是输入数据的多项式表达，但却是输入数

4、据长度的指数时间表达。一个完全多项式近似方案（FPAS）是一个近似方案A， 其中每个算法A在以输入实例的规模和1/两者的多项式时间内运行。伪多项式时间算法是一种算法，它在L值的多项式时间内运行，其中L是输入实例中的最大数值。为NP难问题找到一个FPAS的想法对存在伪多项式时间算法的问题来说是很典型的。子集和问题是背包问题的特例，就是在背包问题中各项的值和它们的重量（尺寸）相同：给出大小为s1, s2, , sn的n个项和背包容量正整数C， 找出这些项的一个子集，使得它们大小的总和最大化，且不超过背包的容量C。5、下面问题是否属于NP问题？为什么？给定图G=（N，A）中的两个点p、q，整数c和t

5、，图G中每条边的长度cij及遍历这条边的时间tij，问图G中是否存在一条由p到q的路径，使得其长度大于C，且遍历时间小于t？答：属于NP问题，因为对该问题的每一个肯定实例，均存在一个多项式时间内的验证。6、简述Las Vegas算法和Monte Carlo算法的主要区别。答：前者不一定总能给出解，但给出的解一定是正确的。后者总能给出解，但是给出的解可能是错误的。7、基于比较的寻找数组A中最大最小元素问题的最紧的下界答：3n/2-28、请给出基于比较的对数组A进行排序问题的最紧的下界，并写出两个平均时间复杂度为该下界的排序算法的名称。答：O（nlogn），快速排序和随机化的快速排序。9、说一个有

6、最优解的贪心算法答：最短路径，DIJKSTRA，哈夫曼编码10、说出两个NP问题答：电路可满足性问题，布尔公式可满足性问题，3合取范式的布尔公式的可满足性问题，团问题，顶点覆盖问题，哈密顿回路问题，TSP问题，子集和问题。11、请列举三种求问题下界的方法。答：计数论证法和归约方法。三、算法分析题1、迪杰斯特拉算法时间复杂度O（n2）；2、多数问题，比较其蛮力算法，并用变治思想求解。答：蛮力O（n2）。变治思想，进行预排序。时间复杂度O（nlogn）。O（n）时间效率的解法是：随机化算法提示：任取两个元素，如果不相同，则同时抛弃。3、P:We say that a recognition pro

7、blem P1 belongs to class P if some polynomial-time algorithm solves problem P1. 存在求解判定问题P1的多项式算法.NP:Roughly speaking, we say that a recognition problem P1 is in the class NP, if for every yes instance I of P1, there is a short (i.e., polynomial length) verification that the instance is a yes instanc

8、e.对P1的每一个肯定实例，均存在一个多项式时间内的验证。P1中所有问题均属于NP.NPC:A recognition problem P1 is said to be NP-complete if :1) P1NP, and all other problems in the class NP polynomially transform to P1.2) NP中其它所有问题多项式转化为P1NP-Hard: A recognition problem P1 is said to be NP-hard if all other problems in the class NP polynomially reduce to P1. The class NP-hard is broader than the class NP-complete because it includes the class NP as well as problems that are not i