算法设计与分析基础第2版算法分析第2章精品课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《算法设计与分析基础第2版算法分析第2章精品课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 基础 精品 课件
- 资源描述:
-
1、第第2章章 算法效率分析基础算法效率分析基础 我常常说,当你对所讲的内容能够进行度我常常说,当你对所讲的内容能够进行度量并且能够用数字来表达时,证明你对这些内量并且能够用数字来表达时,证明你对这些内容是有所了解的;如果你不能用数字来表达,容是有所了解的;如果你不能用数字来表达,那么你的认识是不完整的,也是无法令人满意那么你的认识是不完整的,也是无法令人满意的的.-Lord Kelvin(1824-1907)-Lord Kelvin(1824-1907)2.1 分析框架分析框架 在本节中,我们将概要地描述一个分析算法效率的一般性框架.首先必须指出,有两种算法效率:时间效率和空间效率时间效率和空间
2、效率。时时间效率间效率指出正在讨论的算法运行得有多快;空间效率空间效率关心算法需要的额外空间。研究实验告诉我们,对于大多数问题来说,我们在速度上能够取得的进展要远大于在空间上的进展,所以我们把主要精力集中在时间效率上。2.1.1 输入规模的度量输入规模的度量 几乎所有的算法,对于规模更大的输入都需要动行更长的时间。例如,需要更多时间来对更长的数组排序,更大的矩阵相乘也需要花费更多时间,等等。所以,使用一个以算法输入规模式n为参数的函数,来研究算法效率是非常合乎逻辑的。2.1.2 运行时间的度量单位运行时间的度量单位 我们把基本操作基本操作作为算法运行时间的度量单位。所谓基本操作,就是算法中最重
3、要的操作。它们对总运行时间的贡献最大。我们的下一步工作就是计算它们的运行次数。掌握了这样一种规律,我们就不难发现一个算法中的基本操作基本操作:它通常是算法最内层循环中最费时的操作。例如,大多数排序算法是通过比较列表中的待排序元素(键)来进行工作的;对于这种算法来说,基本操作就是对键的比较。)()(nCcnTop2.1.3增长次数增长次数 为什么对于大规模的输入要强调执行次数的增长次数呢?这是因为小规模输入在运行时间上差别不足以将高效的算法和低效的算法法区分开来。010020030040050060070012345678n*n*nn*nn log(n)nlog(n)2.1.4 算法的最优、最差
4、和平均效率算法的最优、最差和平均效率 一个算法的最差效率最差效率是指当输入规模为n时,算法的最坏情况下的效率。这时,相对于其他规模为n的输入,该算法的运行时间最长。一个算法的最优效率最优效率是指当输入规模为n时,算法在最优情况下的效率。这时,与其它规模为n的输入相比,该算法运行得最快。然而,无论是最差效率分析还是最优效率分析都不能提供一种必要的信息:在“典型”或者“随机”输入的情况下,一个算法会具有什么样的行为。这正是平均效率平均效率试图提供给我们信息。还有一种类型的效率称为摊销效率摊销效率。它并不适用于算法的单次运行,而是应用于算法对同样数据结构所执行的一系列操作。2.1.5 分析框架概要分
5、析框架概要 算法的时间效率和空间效率都用输入规模的函数进行度量。我们用算法基本操作的执行次数来度量算时间效率。通过计算算法消耗的额外存储单元的数量来度量空间效率。在输入规模相同的情况下,有些算法的效率会的显著差异。对于这样的算法,我们需要区分最差效率,平均效率和最优效率。本框架主要关心,当算法的输入规模趋向于无限大的时候,其运行时间(消耗的额外空间)函数的增长次数。2.2 渐进符号和基本效率类型渐进符号和基本效率类型2.2.1 非正式的介绍非正式的介绍 非正式来说,O(g(n)是增长次数小于等于是g(n)(以及其常数倍,n趋向于无穷大)的函数集合。nO(n2),100n+5O(n2),1/2(
6、n(n-1)O(n2),n3/O(n2),第二个符号(g(n),代表增长次数大于等于g(n)(以及其常数倍,n趋向于无穷大)的函数集合。n3(n2),1/2(n(n-1)(n2),但是100n+5/(n2)最后,(g(n)是增长次数等于g(n)(以及其常数倍,n趋向于无穷大)的函数集合。因些,每一个二次方程an2+bn+c在a0的情况下都包含在(n2)中,除了无数类似于n2+sin n和n2+log n的函数(你能解释原因吗?)。2.2.2 符号符号 定义1 我们把函数t(n)属于O(g(n),记作t(n)O(g(n);它的成立条件是:对于所有足够大的n,t(n)的上界由g(n)的常数倍数所确
7、定,也就是说,存在大于0的常数c和非负的整数n0,使得:对于所有的n n0来说,t(n)c g(n)n0之前的情况无关重要cg(n)t(n)n符号O:t(n)O(g(n)n02.2.3 符号符号定义2 我们把函数t(n)属于(g(n),记作t(n)(g(n),它的成立条件是:对于所有足够大的n,t(n)的下界由g(n)的常数倍所确定,也就是说,存在大于0的常数c和非负的整数n0,使得:对于所有的n n0来说,t(n)c g(n)n0之前的情况无关重要cg(n)t(n)n符号:t(n)(g(n)n02.2.4 符号符号定义 3 我们把函数t(n)属于(g(n),记作t(n)(g(n);它的成立条
8、件是:对于所有足够大的n,t(n)的上界和下界都由g(n)的常数倍数所确定,也就是说,存在大于0的常数c1,c2和和非负的整数n0,使得:对于所有的n n0来说,c2g(n)t(n)c1g(n)n0之前的情况无关重要c1 g(n)t(n)n符号:t(n)(g(n)n0c2 g(n)2.2.5渐进符号的有用特性渐进符号的有用特性定理定理 如果t1(n)O(g1(n)并且t2(n)O(g2(n),则 t1(n)+t2(n)O(maxg1(n),g2(n)(对于和符号,类似的断言也为真)对于两个连续执行部分组成的算法,应该如何应用这个特性呢?它意味着该算法的整体效率是由具有较大的增长次数的部分所决定
9、的,即它的效率较差的部分.2.2.6 利用极限比较增长次数利用极限比较增长次数 虽然符号O,和的正式定义对于证明它们的抽象性质是不可缺少的,但我们很小直接用它们来比较两个特定函数的增长次数。有一种较为简便的比较方法,它是基于对所计论的两个函数的比率求极限。有3种极限情况会发生:大的增长次数比表明相同的增长次数和表明小的增长次数比表明)()()()()()(0)()(limngntngntcngntngntn2.2.7基本的效率类型基本的效率类型 1constantlog nlogarithmicnlinearn log nn log nn2quadraticn3cubic2nexponenti
展开阅读全文