算法设计与分析总结.docx

第一章 绪论1、重要特性1.输入2.输出3.有穷性4.确定性5.可行性2、描述算法的方法1.自然语言：优点是直观易懂，缺点是容易出现二义性2.流程图：优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言3.程序设计语言：优点是计算机直接运行，缺点是抽象性差4.伪代码：3、递归算法分析1.猜测技术2.扩展递归技术3.通用分治递归推式第二章 NP完全理论第三章 蛮力法3.1 蛮力法的设计思想蛮力法依赖的基本技术扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解;关键依次处理所有元素。3.2 查找问题中的蛮力法3.2.1 顺序查找O(n)3.2.2串匹配问题BF O(n*m)BMP O(n+m)BM O(n*m)3.3 排序问题中的蛮力法3.3.1 选择排序O(n2)3.3.2 起泡排序O(n2)3.4 组合问题中的蛮力法3.4.1 生成排列对象O(n!)3.4.2 生成子集O(2n)3