算法分析与设计第1章详解.ppt

1 60 算法设计与分析 福州大学数计 软件 学院陈家瑞jrchen 2 60 课程安排 总学时 32考查方式 闭卷考试 80 出勤作业 20 3 60 教材 计算机算法设计与分析 第4版 王晓东编著电子工业出版社 4 60 参考书1 算法设计与分析 C 语言描述 第2版 陈慧南编著电子工业出版社 5 60 参考书2 算法导论 原书第3版 ThomasH Cormen等著 殷建平等译机械工业出版社 6 60 课程主要内容 第1章算法概述第2章递归与分治策略第3章动态规划第4章贪心算法第5章回溯法第6章分支限界法 7 60 第1章算法概述 学习要点 1 1理解算法的基本概念 1 2掌握算法的复杂性分析 1 3理解NP完全性理论相关知识 8 60 1 1算法的基本概念 1 1 1为什么要学习算法1 1 2算法及其重要性质1 1 3算法的描述方法1 1 4问题求解的一般过程1 1 5重要的问题类型 9 60 1 1 1为什么要学习算法 理由1 算法 程序的灵魂问题的求解过程 分析问题 设计算法 编写程序 整理结果程序设计研究的四个层次 算法 方法学 语言 工具理由2 提高分析问题的能力算法的形式化 思维的逻辑性 条理性 10 60 算法应用 人类基因数据库分析因特网信息管理 电子商务 加密 解密 保护隐私 火车 航班调度 大科学计算 应用软件 实际应用 11 60 算法可以看做一项技术 算法可以看作是一项技术例对于排序问题 问题规模 n 106 插入排序算法 复杂度c1n2合并排序算法 复杂度c2nlog2n计算机A每秒能执行10亿条指令计算机B每秒能执行1000万条指令计算机A 插入排序算法 c1 2 则计算机A花的时间为 计算机B 合并排序算法 c2 50 则计算机B花的时间为 12 60 1 1 2算法及其重要性质 算法是指解决问题的一种方法或一个过程 算法是若干指令的有穷序列 满足性质 1 输入 有外部提供的量作为算法的输入 2 输出 算法产生至少一个量作为输出 3 确定性 组成算法的每条指令是清晰 无歧义的 4 有限性 算法中每条指令的执行次数是有限的 执行每条指令的时间也是有限的 13 60 欧几里德算法 mn r 例 欧几里德算法 辗转相除法求两个自然数m和n的最大公约数 14 60 算法与程序的区别 程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的性质 4 例如操作系统 是一个在无限循环中执行的程序 因而不是一个算法 操作系统的各种任务可看成是单独的问题 每一个问题由操作系统中的一个子程序通过特定的算法来实现 该子程序得到输出结果后便终止 15 60 1 1 3算法的描述方法 自然语言优点 容易理解缺点 冗长 二义性使用方法 粗线条描述算法思想注意事项 避免写成自然段 16 60 欧几里德算法 输入m和n 求m除以n的余数r 若r等于0 则n为最大公约数 算法结束 否则执行第 步 将n的值放在m中 将r的值放在n中 重新执行第 步 17 60 流程图优点 流程直观缺点 缺少严密性 灵活性使用方法 描述简单算法注意事项 注意抽象层次 18 60 开始 输入m和nr m n r 0Nm n n r输出n 结束 Y 欧几里德算法 19 60 程序设计语言优点 能由计算机执行缺点 抽象性差 对语言要求高使用方法 算法需要验证注意事项 将算法写成子函数 20 60 include intCommonFactor intm intn intr m n while r 0 m n n r r m n returnn voidmain cout CommonFactor 63 54 endl 欧几里德算法 21 60 伪代码 算法语言伪代码 Pseudocode 介于自然语言和程序设计语言之间的方法 它采用某一程序设计语言的基本语法 操作指令可以结合自然语言来设计 优点 表达能力强 抽象性强 容易理解 22 60 欧几里德算法1 r m n 2 循环直到r等于02 1m n 2 2n r 2 3r m n 3 输出n 23 60 1 1 4问题求解的一般过程 理解问题 精确解或近似解选择数据结构算法设计策略 设计算法 24 60 1 查找问题2 排序问题3 图问题4 组合问题5 几何问题 1 1 5重要的问题类型 25 60 1 2算法分析 1 2 1最好 最坏和平均情况1 2 2渐近符号1 2 3非递归算法的分析1 2 4递归算法的分析1 2 5算法的实验分析 26 60 算法复杂性分析 算法复杂性 算法所需要的计算机资源算法的时间复杂性T n 算法的空间复杂性S n 其中n是问题的规模 输入大小 27 60 算法的时间复杂性 1 最坏情况下的时间复杂性Tmax n max T I size I n 2 最好情况下的时间复杂性Tmin n min T I size I n 3 平均情况下的时间复杂性Tavg n 其中I是问题的规模为n的实例 p I 是实例I出现的概率 28 60 算法渐近复杂性 T n asn T n t n T n 0 asn t n 是T n 的渐近性态 为算法的渐近复杂性 在数学上 t n 是T n 的渐近表达式 是T n 略去低阶项留下的主项 它比T n 简单 29 60 渐近分析的记号 在下面的讨论中 对所有n f n 0 g n 0 1 渐近上界记号OO g n f n 存在正常数c和n0使得对所有n n0有 0 f n cg n 2 渐近下界记号 g n f n 存在正常数c和n0使得对所有n n0有 0 cg n f n 30 60 3 非紧上界记号oo g n f n 对于任何正常数c 0 存在正数和n0 0使得对所有n n0有 0 f n cg n 等价于f n g n 0 asn 31 60 4 紧渐近界记号 g n f n 存在正常数c1 c2和n0使得对所有n n0有 c1g n f n c2g n 定理1 g n O g n g n 32 60 渐近分析记号在等式和不等式中的意义 f n g n 的确切意义是 f n g n 一般情况下 等式和不等式中的渐近记号 g n 表示 g n 中的某个函数 例如 2n2 3n 1 2n2 n 表示2n2 3n 1 2n2 f n 其中f n 是 n 中某个函数 等式和不等式中渐近记号O o 的意义是类似的 33 60 渐近分析中函数比较 f n O g n a b f n g n a b f n g n a b f n o g n a b 34 60 渐近分析记号的若干性质 1 传递性 f n g n g n h n f n h n f n O g n g n O h n f n O h n f n g n g n h n f n h n f n o g n g n o h n f n o h n 35 60 2 反身性 f n f n f n O f n f n f n 3 对称性 f n g n g n f n 4 互对称性 f n O g n g n f n 36 60 5 算术运算 O f n O g n O max f n g n O f n O g n O f n g n O f n O g n O f n g n O cf n O f n g n O f n O f n O g n O f n 37 60 算法分析中常见的复杂性函数 凡渐近时间复杂度有多项式时间限界的算法称做多项式时间算法 polynomialtimealgorithm 而渐近时间复杂度为指数函数限界的算法称做指数时间算法 exponentialtimealgorithm 38 60 算法分析中常见的复杂性函数 39 60 最常见的多项式时间算法的渐近时间复杂度O 1 O logn O n O nlogn O n2 O n3 最常见的指数时间算法的渐近时间复杂度O 2n O n O nn 算法分析中常见的复杂性函数 40 60 小规模数据 41 60 中等规模数据 42 60 1 2 3非递归算法的分析 算法 非递归算法 递归算法例 顺序搜索算法 templateintseqSearch Type a intn Typek for inti 0 i n i if a i k returni return 1 43 60 非递归算法分析的一般步骤 1 决定用哪个 或哪些 参数作为算法问题规模的度量2 找出算法中的基本语句3 检查基本语句的执行次数是否只依赖于问题规模4 建立基本语句执行次数的求和表达式5 用渐进符号表示这个求和表达式关键 建立一个代表算法运行时间的求和表达式 然后用渐进符号表示这个求和表达式 44 60 1 Tmax n max T I size I n O n 2 Tmin n min T I size I n O 1 3 在平均情况下 假设 a 搜索成功的概率为p 0 p 1 b 在数组的每个位置i 0 i n 搜索成功的概率相同 均为p n 45 60 templatevoidinsertion sort Type a intn Typekey costtimesfor inti 1 i 0 c7n 1 46 60 在最好情况下 ti 1 for1 i n 在最坏情况下 ti i 1 for1 i n 47 60 对于输入数据a i n i i 0 1 n 1 算法insertion sort达到其最坏情形 因此 由此可见 Tmax n n2 48 60 1 2 4递归算法的分析 关键 根据递归过程建立递推关系式 然后求解这个递推关系式 1 猜测技术 对递推关系式估计一个上限 然后 用数学归纳法 证明它正确 49 60 2 扩展递归技术 50 60 3 通用分治递推式大小为n的原问题分成若干个大小为n b的子问题 其中a个子问题需要求解 而cnk是合并各个子问题的解需要的工作量 51 60 递归算法复杂性分析 intfactorial intn if n 0 return1 returnn factorial n 1 52 60 最优算法 问题的计算时间下界为 f n 则计算时间复杂性为O f n 的算法是最优算法 例如 排序问题的计算时间下界为 nlogn 计算时间复杂性为O nlogn 的排序算法是最优算法 堆排序算法是最优算法 53 60 算法的后验分析 Posteriori 也称算法的实验分析 它是一种事后计算的方法 通常需要将算法转换为对应的程序并上机运行 1 2 5算法的后验分析 54 60 一般步骤 1 明确实验目的2 决定度量算法效率的方法 为实验准备算法的程序实现3 决定输入样本 生成实验数据4 对输入样本运行算法对应的程序 记录得到的实验数据5 分析得到的实验数据 55 60 将能在多项式时间求解的问题看作易处理问题 tractableproblem 而将至今尚未找到多项式时间算法求解的问题视为难处理问题 intractableproblem 1 3NP完全性理论 56 60 P类和NP类问题 P类和NP类 P是所有可在多项式时间内用确定算法求解的判定问题的集合 NP是所有可在多项式时间内用不确定算法求解的判定问题的集合 多项式约化 令Q1和Q2是两个问题 如果存在一个确定算法A求解Q1 而算法A以多项式时间调用另一个求解Q2的确定算法B 若不计B的工作量 算法A是多项式时间的 则称Q1约化 reducedto 为Q2 记做Q1 Q2 57 60 NP难度和NP完全问题 NP难度 对于问题Q以及任意问题Q1 NP 都有Q1 Q 则称Q是NP难度 NPhard 的 NP完全 对于问题Q NP Q是NP难度的 则称Q是NPC NPcomplete 的 58 60 如何确定某个问题Q是否是NP难度的 一般的证明策略由以下两步组成 1 选择一个已经证明是NP难度问题Q1 2 求证Q1 Q 由于Q1是NP难度的 因此所有NP类问题都可约化到Q1 根据约化的传递性 任何NP类问题都可约化到Q 所以Q是NP难度的 如果进一步表明Q本身是NP类的 则问题Q是NPC的 59 60 P NP 目前人们猜测P NP 则P类问题 NP类问题 NP完全问题之间