算法设计与分析复习.docx

算法设计与分析复习（2015）考试题型与范围1.单选题、判断题、填空题、简答题、分析题、计算题。2.不含5.2近似串匹配，7.3-5第1章 算法设计与分析基础1、 算法概念、特征、与程序的区别2、 问题、问题求解、问题求解过程（理解问题、设计方案、实现方案、回顾复查）、系统生命周期（分析、设计、编码、维护）3、 算法问题求解过程（设计、表示、确认、分析）4、 好的算法特性（正确性、简明性、效率、最优性）5、 影响运行时间的因素（3点）6、 算法复杂度、时间复杂度、空间复杂度、最好、最坏和平均时间复杂度7、 渐进表示法：大O记号、记号、记号8、 算法按时间复杂度分类：多项式时间算法和指数时间算法 O(1)O(logn)O(nlogn)O(n2)O(n3)O(2n)O(n!O(nn)9、 了解非递归算法的时间复杂性分析。要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。非递归算法分析的一般步骤是：（1）决定用哪个（或哪些）参数作为算法问题规模的度量。（2）找出算法的基本语句。（3）检查基本语句的执行次数是否只依赖问题规模。（4）建立基本语句执行次数的求和表达式。（5）用渐进符号表示这个求和表达式。10、 常见的重要问题类型排序问题、查找问题、图问题、组合问题、几何问题、数值问题其他问题11、 常用的基本数据结构 线性结构：栈、队列、数组 非线性：树、图12、 常用的算法设计方法 数值计算方法：迭代法、插值法、差分法、归纳法、递推法、减半递推技术、递归法 非数值计算方法：列举法分治法、贪心法、动态规划法、回溯法、分支限界法13、 递归、递归算法、递归设计结构、归纳证明第2章 递归法1、 递归算法特性、执行过程2、 递推关系分析算法复杂度3、 计算递推式三种方法：替换方法、迭代方法、主方法4、 掌握扩展递归技术和通用分治递推式的使用。扩展递归技术：通用分支递归式：第3章 分治法1、设计思想：将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。2、步骤：（1）划分（2）求解子问题（3）合并3、分治法的代表算法及时间复杂度：排序问题（归并排序、快速排序）O(nlogn)，折半查找 O(logn)、选择问题O(n)，最大子段和O(n3)、棋盘覆盖问题O(4k)第4章 贪心法1、可行解、最优解、最优量度标准、可行解判断函数2、设计思想贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出局部最优选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。3、贪心法的关键在于决定贪心策略。4、贪心法两个基本要素：最优子结构性质和贪心选择性质5、贪心法解决的问题（可求最优解）：背包问题，活动安排问题，多机调度问题，单源最短路径，最小代价生成树的两种贪心算法：prim算法和kruskal算法。第5章 动态规划法1、设计思想：将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解。2、步骤：（1）刻画最优解的结构特性；（2）递归定义最优解值；（3）以自底向上方式计算最优解；（4）根据计算得到的信息构造一个最优解。3、两个要素：最优子结构性质和子问题重叠性质4、动态规划法解决的问题（可求最优解）：多段图问题（n+e），每对结点间的最短路径O（n3）最长公共子序列，最优二叉搜索树O（n3），0/1背包问题O（2n），流水作业调度O(nlogn)。第6章 回溯法1、 设计思想：从解空间树根结点出发，按照深度优先策略遍历解空间树，在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。直到搜索到叶子结点，则得到问题的一个可能解。2、 显约束、隐约束、解状态、约束函数、剪枝函数等3、步骤：（1）针对所给问题，定义问题的解空间； （2）确定易于搜索的解空间结构；（3）按深度优先方式搜索解空间，且在搜索过程中利用剪枝函数避免无效搜索。从所有的可能解中确定最优解。4、回溯法解决的问题（可求所有解、一个解、最优解）：属于组合问题和排列问题中求最优解的问题都可以用回溯法解决，例如：八皇后问题（4皇后问题），0/1背包问题，子集合和数，图着色问题，TSP问题，深度优先搜索。第7章 分支限界法1、设计思想：1）首先确定一个合理的限界函数，并根据限界函数确定目标函数的界down, up ，并确定限界函数；2）然后按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的限界函数的可能取值；3）如果某孩子结点的限界函数可能取得的值超出目标函数的界，则将其丢弃；否则，将其加入待处理结点表（以下简称表PT）中；4）依次从表PT中选取使限界函数的值是极值的结点成为当前扩展结点；5）重复上述过程，直到找到搜索到叶子结点，如果叶子结点的限界函数的值是极值，则就是问题的最优解，否则，找到其他极值结点重复扩展搜索。2、步骤：确定解空间树确