




已阅读5页,还剩28页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
算法设计与分析 谭守标安徽大学电子学院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 作
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 中国锂电池负极材料项目创业投资方案
- 电解工理论考试题及答案
- 2025年年产3亿个塑料制品项目可行性研究报告申请报告
- 2025年中国氢能源项目创业投资方案
- 中国二月桂酸二正丁基锡项目创业投资方案
- 单招民政考试题及答案
- 齐齐哈尔梅里斯达斡尔族区公益性岗位招聘考试真题2024
- 大连美术考试题目及答案
- 文言文知识点梳理(7篇)人教统编版九年级语文下册
- 事故组协议书
- 装修抵房租租房合同范本
- 医药代表商务礼仪培训课程
- 学校食堂双总监协调机制制度
- 医疗机构医疗质量安全专项整治行动方案2025
- 点、直线和平面的投影
- 交通卡口监控系统维护方案
- 2025年人教版小学一年级下学期奥林匹克数学竞赛试题(附答案解析)
- TSG D2002-2006燃气用聚乙烯管道焊接技术规则
- NB/T 11525-2024气动、电动调度单轨吊车技术条件
- DB34T 4829-2024公路工程泡沫轻质土设计与施工技术规程
- 部编版新教材语文二年级上册《6.去外婆家》教案设计
评论
0/150
提交评论