算法分析与设计复习大纲(全)22页.docx

算法分析与设计复习大纲第1章 绪论考点：1、 算法的5个重要特性。答：输入、输出、有穷性、确定性、可行性2、 掌握扩展递归技术和通用分治递推式的使用。扩展递归技术：通用分支递归式：5、使用扩展递归技术求解下列递推关系式（1）（2）第3章 蛮力法1、 掌握蛮力法的设计思想：蛮力法依赖的基本技术扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解;关键依次处理所有元素。2、 蛮力法的代表算法及其时间复杂度：顺序查找，O(n)串匹配（BFO(n*m)，KMPO(n+m) 选择排序，O(n2)冒泡排序，O(n2)生成排列对象（排列问题），O(n!)生成子集（组合问题），O(2n)0/1背包 属于组合问题。任务分配，哈密顿回路，TSP问题 属于排列问题。 3、 掌握BF和KMP算法的原理，能够画出比较过程。要求给出一串字符串，能够求出对应的next数组，并能使用KMP算法进行比较