算法设计与分析考试重点.docxVIP

算法重点：第一章：算法的特征输入，输出，确定性，能行性，有穷性。辗转相除P2第二章：好算法的特征正确性，简明性，效率，最优性，健壮性（输入不合法时），可靠性 影响程度运行时间的因素程序所依赖的算法（根本的），问题规模和输入数据，计算机系统性能 算法的渐进时间复杂度P17 最好最好时间复杂度P16 课后习题2.8 多项式时间复杂度 O(1)O(log n)O(n)O(nlog n)O(n^2)O(n^3) 第五章：分治法特征该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题；（这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用。）利用该问题分解出的子问题的解可以合并为该问题的解；（能否利用分治法完全取决于问题是否具有这条特征。如果具备了前两条特征，而不具备这一特征，则可以考虑贪心法或动态规划法。）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。（这条特征涉及到分治法的效率。如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划法较好。）对半有哪些信誉好的足球投注网站 序列 P70时间复杂度分析 快速排序P81 p76矩阵相乘 原理 填空题通过减少子矩阵的乘法次数来降低时间复杂度。O（n^2.81）第六章：贪心法的要素贪心选择性质和最优子结构性质。一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。根据题意，选定一种最优量度标准，作为选择当前分量值的依据。这种选择准则称为，最优量度标准或者贪心准则，或者贪心选择性质。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。分布决策：贪心法在求解问题上的每一步做出决策，产生n-元组解的一个分量。一般背包问题 最佳合并模式P92 P102普里姆 克利斯卡尔 最小生成树普利姆，P106，O（n^2），克鲁斯卡尔，P109，O(eloge)第七章：动态规划算法适用子问题重叠性质最优子结构性质备忘录方法P136备忘录方法的控制结构与自顶向下直接递归方法的控制结构相同。区别在于备忘录方法为每个已解过的子问题建立了备忘录进行保存，以备需要时直接查看，之后不再重复计算。是动态规划法的一种变形。当一个问题的所有子问题都至少要解一次时，选用动态规划法较好，此时没有任何多余的计算，还可利用规则的表格存取方式，减少时间和空间需求。当一个问题只有部分子问题需要求解时，选用备忘录法较好，它只解那些确实需要求解的子问题。多段图P124，自底向上。关键路径P128最长公共子序列P137第八章：回溯法使用 与分支限界法的区别剪枝函数，深度优先有哪些信誉好的足球投注网站的是回溯法，广度优先有哪些信誉好的足球投注网站的是分枝限界法。分枝限界法与回溯法的区别（1）求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有可行解；而分枝限界法的求解目标则是找出满足约束条件的一个可行解，或某种意义下的最优解。（2）有哪些信誉好的足球投注网站方式不同：回溯法以深度优先的方式有哪些信誉好的足球投注网站解空间树，而分枝限界法则以广度优先的方式有哪些信誉好的足球投注网站解空间树。（3）对当前扩展结点的扩展方式不同：回溯法中的每个活结点可能多次成为当前扩展结点，纵深方向扩展其一个儿子，然后再回溯后扩展其他儿子；而分枝限界法中每一个活结点只有一次机会成为扩展结点，一次产生所有孩子结点，自身成为死结点，之后无需再返回该结点处。蒙特卡罗 估算节点数P163子集和数问题 P167哈密顿环P172第九章：分支限界法P18215迷问题P185第十章：NP完全 P问题 NP问题P211第十三章：密码学P257对称密码体制，非对称密码体制。RSA