《各种算法的归纳》由会员分享，可在线阅读，更多相关《各种算法的归纳（4页珍藏版）》请在金锄头文库上搜索。
1、算法名设计思想代表算法及时间复杂度需掌握的内容蛮力法蛮力法依赖的基本技术扫扌田技术，即米用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解；关键依次处理所有元素顺序查找，O(n)串匹配(BFO(n*m)，KMPO(n+m)，BMO(n*m)，选择排序，O(n2)冒泡排序，O(n2)生成排列对象(排列问题)，O(n!)生成子集(组合问题)，O(2n)0/1背包属于组合问题。任务分配，哈密顿回路，TSP问题属于排列问题。最近对问题O(n2),凸包问题O(n3)1. 掌握BF和KMP算法的原理，能够画出比较过程。2. 要求给出一串字符串，能够求出对应的next数组，并能使用KMP算法进
2、行比较匹配。3. 掌握选择排序和冒泡排序算法描述和时间复杂性，要求能够写出伪代码。分治法将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。归并排序，O(nlog2n)快速排序，O(nlog2n)最大子段和，O(nlog2n)最近对问题，O(nlog2n)凸包问题，O(nlog2n)棋盘覆盖，O(4k)循环赛日程安排，O(4k)1. 掌握归并排序和快速排序算法的算法伪代码2. 掌握最
3、大子段和问题的算法伪代码减治法原问题的解只存在于其中一个较小规模的子问题中，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。折半查找，o（iog2n）二叉树查找，o（iog2n）堆排序，o（iog2n）选择问题，o（iog2n）淘汰赛冠车问题，o（iog2n）假币问题，o（iog2n）1.掌握折半查找的算法伪代码描述及具体例子的查找过程，会根据折半查找的过程创建判定树2会根据已知数据序列创建一个二叉查找树3. 掌握堆排序算法中的两种调整堆和新建堆的方法：筛选法和插入法4. 掌握选择问题的算法的伪代码动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段
4、，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过杳表获得该子问题的解而不用再次求解。TSP,多段图的最短路径问题，0/1背包，最长公共子序列问题，最优二叉查找树，近似串匹配问题；其中多段图的最短路径问题：O（n+m）0/1背包问题：O（nxC）1. 掌握多段图的最短路径问题的动态规划算法及具体实现2. 掌握0/1背包问题的动态规划算法及具体实现贪心法贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出局部最优选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。贪心法的关键在于决定贪心策略TSP问题中的两种解决方法：最近领点策略，最短链接策略最小生成树问
5、题的两种算法：最近顶点策略（Prim算法），最短边策略（Kruskal算法）背包问题，活动安排问题，多机调度问题，哈夫曼编码。1. 掌握最小生成树的两种贪心算法：prim算法和kruskal算法，给出具体的例子，能够用两种方法画出树的生成过程2. 掌握背包问题的贪心算法，给出一个具体的例子，能够写出解决问题的过程3. 给出字符集和对应的频率，能够画出对应的哈夫曼树，并对给定的字符串进行哈夫曼编码回溯法从解空间树根结点出发，按照深度优先策略遍历解空间树，在搜索至树中任一结点时，先判断该结点对应的部分解是否满足属于组合问题和排列问题中求最优解的问题都可以用回溯法解决，例如：图着色问题，哈密顿回路问
6、题，八皇后问题（4皇后问题），批处理作业调度问题1. 掌握m颜色图着色判定问题的回溯法算法，并能画出解空间树的搜索过程2. 掌握n皇后问题的回溯法算法，并能画约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。直到搜索到叶子结点，则得到问题的一个可能解。出解空间树的搜索过程3.掌握0/1背包问题的回溯算法，并能画出解空间树的搜索过程分支限界法1）首先确定一个合理的限界函数，并根据限界函数确定目标函数的界down,up，并确定限界函数；
7、2）然后按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的限界函数的可能取值；3）如果某孩子结点的限界函数可能取得的值超出目标函数的界，则将其丢弃；否贝y,将其加入待处理结点表（以下简称表PT）中；4）依次从表PT中选取使限界函数的值是极值的结点成为当前扩展结点；5）重复上述过程，直TSP问题，多段图的最短路径问题，任务分配问题，批处理作业调度问题，0/1背包问题。1掌握任务分配问题的分支限界法.2掌握0/1背包问题的分支限界法3掌握批处理作业问题的分支限界法到找到搜索到叶子结点，如果叶子结点的限界函数的值是极值，则就是问题的最优解，否则，找到其他极值结点重复扩展搜索。
