算法设计与分析-1绪论.ppt

算法设计与分析 谭守标安徽大学电子学院2007 9 基本情况 性质 必修学时 54考核方法 平时成绩50 考勤10 专题或课堂报告40 期末考试50 教材和参考书 教材 美 科曼 Cormen T H 等著 潘金贵等译 算法导论 原书第2版 北京 机械工业出版社 2006 9参考资料AnanyLevitin 潘彦译 算法设计与分析基础 北京 清华大学出版社 2004 6SaraBaase等 计算机算法 设计与分析导论 英文影印版 北京 高等教育出版社 2001 7王晓东 计算机算法设计与分析 北京 电子工业出版社 2001 1 主要内容 算法分析基本知识高级数据结构堆 红黑树 顺序统计树 区间树 二项堆 斐波那契堆 分离集合等算法设计及分析方法各种排序 动态规划 贪心算法等 第一章绪论 1 1算法1 2算法分析1 3算法设计 1 1算法 什么是算法 算法的形式定义可以看作是任何一个良定义 有穷 确定 可行 的计算过程 以一个或一些值作为输入 产生出一个或一组值作为输出 问题陈述 1 1算法 算法的重要性 微积分造就了现代科学 算法造就了现代世界 算法是计算机科学的基石 算法 计算的灵魂 程序 算法 数据结构 学习算法可以开发人们的分析能力 1 1算法 必要性 知道计算机领域中解决不同问题的一系列标准算法 具备设计新算法和分析其效率的能力 1 1算法 问题求解过程 理解问题 精确解或近似解选择数据结构算法设计策略 设计算法 1 1算法 两种组织方法 按照问题类型分类查找 排序 串处理 图 组合问题 几何问题 数值问题等按照算法技术分类直接法 分治技术 贪婪技术 动态规划 近似算法 分支定界法 回溯法 线性规划 网络流 概率算法 并行算法等 1 1算法 算法举例 排序问题输入 一列数输出 输入序列的一个变换 其中a1 an 算法选择 冒泡 插入 快速 堆 算法的选取取决于多种因素 1 1算法 问题的实例及算法正确性 问题实例由满足问题陈述中所给出限制 并能得到问题的一个结果的所有输入构成 对于排序问题 对输入序列 排序算法的返回结果序列为 该输入序列即为排序问题的一个实例 算法正确性对每一个输入实例 一个算法都能停止并给出正确的答案 则该算法是正确的 我们说一个正确的算法解决了给定的计算问题 一个不正确的算法在其错误率可被控制的情况下可能是很有用的 1 1算法 算法的描述 伪码 插入排序 1 1算法 算法的描述 伪码 插入排序 1 1算法 算法的描述 伪码 插入排序INSERTION SORT A 1forj 2tolength A 2dokey A j 3 将A j 插入排好序的A 1 j 1 中 4i j 15whilei 0andA i key6doA i 1 A i 7i i 18A i 1 key 1 1算法 算法的描述 伪码 伪码的使用约定缩进用于表示程序体结构 while for repeat if等语句与Pascal中相同 符号 表示后面部分是注释 符号 表示赋值操作 局部变量可不用声明 全局变量必须声明 数组中 表示数组下标取值范围 如A 1 j 复合数据用对象来表示 对象的域的取值由域名后接方括号括住的对象名来表示 数组或对象变量被看作是指向数组或对象的指针 参数用按值传递方式传给过程 1 2算法分析 基本概念 算法分析是指对算法所需的资源进行预测 算法 好 与 不好 正确性时间效率空间效率是否存在更好的算法 下界最优途径理论 数学上的分析经验 计算机上的执行情况 1 2算法分析 基本概念 一个算法的运行时间是指在特定输入时所执行的基本操作数 一般地 算法的运行时间与输入规模同步增长 即使规模相同的两个不同输入 其运行时间也可能差别很大 如插入排序算法中 输入已排序的程度对算法的时间影响非常大 1 2算法分析 插入排序算法 假定每次执行第i行所花的时间都是常量ci 1 2算法分析 插入排序算法 总运行时间最佳运行时间 已排好序输入 T n c1n c2 n 1 c4 n 1 c5 n 1 c8 n 1 c1 c2 c4 c8 n c2 c4 c5 c8 an b 线性函数 1 2算法分析 插入排序算法 最坏情况运行时间 逆序输入 an2 bn c 二次函数 输入情况选择最坏情况分析 一般情况下 最坏情况运行时间是任何输入下运行时间的上界 对某些算法 最坏情况是经常发生的 平均情况 的时间性常常与最坏情况下大致一样 平均情况分析 特殊情况下 通常假定一个特定规模下的所有输入的 平均性 都是一样的 也可以采用随机算法强制达到平均 1 2算法分析 算法分析一般框架 时间的量度 增长量级忽略每条语句的真实代价 ci 忽略低阶项忽略最高次项的常数系数表示方法 f n 如插入排序的最坏情况时间代价的阶为 n2 如果一个算法的最坏情况运行时间的阶比另一个算法低 一般认为它更为有效 对足够大规模的输入 一个具有阶 n2 的算法在最坏情况下比阶为 n3 的算法运行的更快 1 2算法分析 算法分析一般框架 1 3算法设计 设计方法 直接法分治法减治法变治法贪婪技术动态规划回溯 分支限界法 1 3算法设计 分治法 最著名的通用算法设计技术策略 将原问题分成n个规模较小而结构与原问题相似的子问题 递归地解这些子问题 然后合并其结果就得到原问题的解 步骤 分解 Divide 将原问题分解成一系列子问题 解决 Conquer 递归地解各子问题 若子问题足够小 则直接求解 合并 Combine 将子问题的结果合并成原问题的解 关键在于合并处理 1 3算法设计 分治法 合并排序 步骤 分解 将n个元素分成各含n 2个元素的子系列 解决 用合并排序法对两个子序列递归地排序 如子序列长度为1时递归结束 已排好序 合并 合并两个已排序的子序列以得到排序结果 1 3算法设计 分治法 合并排序 MERGE SORT A p r 1ifp r2thenq p r 23MERGE SORT A p q 4MERGE SORT A q 1 r 5MERGE A p q r 1 3算法设计 分治法 合并排序 1 3算法设计 分治法 合并排序 合并处理 如两堆排好序的牌 合并成排好序的一堆 每次取出两输入堆中最上面的一张比较大小 将小的一张拿出到输出堆中 重复上面的步骤直至某一输入堆无牌 将另一输入堆余下的牌依序放入输出堆中 合并处理的时间代价为 n n r p 1 为待排序元素个数 1 3算法设计 分治算法分析 算法中含有对自身的递归调用时 其运行时间可用递归方程来表述 分治算法的递归式基于基本模式的三个基本步骤 设T n 为在规模n下算法运行时间 设把原问题分解成a个子问题 每个的大小为原问题的1 b 设分解该问题和合并解的时间分别为D n 和C n 如n足够小时 n c 则得到它的直接解的时间为常量 写作 1 则 1 3算法设计 分治法 合并排序分析 简化起见 假定原问题的规模是2的幂次 后面可看到 该假定不影响递归式解的阶 时间分析 给出递归形式的T n 分解 D n 1 解决 递归解两个规模为n 2的子问题 时间为2T n 2 合并 C n n 则 在第四章可知T n 的阶为 nlgn lgn代表log2n 当输入规模足够大时 优于插入排序的 n2 作