算法设计与分析基础第2版算法分析第2章课件

1、第2章 算法效率分析基础 我常常说，当你对所讲的内容能够进行度量并且能够用数字来表达时，证明你对这些内容是有所了解的；如果你不能用数字来表达，那么你的认识是不完整的，也是无法令人满意的. -Lord Kelvin(1824-1907) 陈塞衡嘎哨饺靳恰火祁邯恼萤葛骂缘劳丈揍跌叹批利柴预侈耶贮姚舶媚屿算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章2.1 分析框架在本节中,我们将概要地描述一个分析算法效率的一般性框架.首先必须指出,有两种算法效率:时间效率和空间效率。时间效率指出正在讨论的算法运行得有多快；空间效率关心算法需要的额外空间。研究实验告

2、诉我们，对于大多数问题来说，我们在速度上能够取得的进展要远大于在空间上的进展，所以我们把主要精力集中在时间效率上。柞肮痔默惯宰爸芍勾冬束捷玄胚构桓烃抽峪删磊培啪琵痒弱吩偿让蔓责狱算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章2.1.1 输入规模的度量 几乎所有的算法，对于规模更大的输入都需要动行更长的时间。例如，需要更多时间来对更长的数组排序，更大的矩阵相乘也需要花费更多时间，等等。所以，使用一个以算法输入规模式n为参数的函数，来研究算法效率是非常合乎逻辑的。伤覆跌吻赠妊敏匈僵赔赶掘日下力汕诵酋悔逐畅篷键淌祸大卫碑沉谱灯嘴算法设计与分析基础第2

3、版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章2.1.2 运行时间的度量单位 我们把基本操作作为算法运行时间的度量单位。所谓基本操作，就是算法中最重要的操作。它们对总运行时间的贡献最大。我们的下一步工作就是计算它们的运行次数。掌握了这样一种规律，我们就不难发现一个算法中的基本操作：它通常是算法最内层循环中最费时的操作。例如，大多数排序算法是通过比较列表中的待排序元素（键）来进行工作的；对于这种算法来说，基本操作就是对键的比较。 俘灼椎茫洁猴钦心标价难墩碌董逐领灌段嘛消剩砒鸣妒狠悦杨拎猩珠沉参算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华

4、出版社算法分析第2章2.1.3增长次数 为什么对于大规模的输入要强调执行次数的增长次数呢？这是因为小规模输入在运行时间上差别不足以将高效的算法和低效的算法法区分开来。 苦尧民丝起胎窟次抡芯赡帛预兑箩恐妥获烈凝菇搅绚戍狐拿罢健蠕词睡殷算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章庐柬靖摈鳖部变简镜合叮疟够瑰璃哗滤逾恬啤肇汲芒瞩蓝餐勇躺钱譬熬谬算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章2.1.4 算法的最优、最差和平均效率 一个算法的最差效率是指当输入规模为n时，算法的最坏情况下的效率。这时，相

5、对于其他规模为n的输入，该算法的运行时间最长。 一个算法的最优效率是指当输入规模为n时，算法在最优情况下的效率。这时，与其它规模为n的输入相比，该算法运行得最快。 然而，无论是最差效率分析还是最优效率分析都不能提供一种必要的信息：在“典型”或者“随机”输入的情况下， 一个算法会具有什么样的行为。这正是平均效率试图提供给我们信息。 还有一种类型的效率称为摊销效率。它并不适用于算法的单次运行，而是应用于算法对同样数据结构所执行的一系列操作。核趋览猿琢滞锥残层依咋秩肝胜遥泳芝衰径冰弯刻尹酥舅堂缅撇冒索鼠见算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章

6、2.1.5 分析框架概要算法的时间效率和空间效率都用输入规模的函数进行度量。我们用算法基本操作的执行次数来度量算时间效率。通过计算算法消耗的额外存储单元的数量来度量空间效率。在输入规模相同的情况下，有些算法的效率会的显著差异。对于这样的算法，我们需要区分最差效率，平均效率和最优效率。本框架主要关心，当算法的输入规模趋向于无限大的时候，其运行时间（消耗的额外空间）函数的增长次数。冯硼剪钻帽来极剐乒把呀欲身玫茵拂鹊倍略注督屎彬催蔑驴才郁宰赶胯踪算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章2.2 渐进符号和基本效率类型2.2.1 非正式的介绍 非正

7、式来说， O(g(n) 是增长次数小于等于是g(n) (以及其常数倍，n趋向于无穷大)的函数集合。 nO(n2),100n+5O(n2),1/2(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的函数（你能解释原因吗？

8、）。即腰荐间碘痊窒妻衣惨骤闪蒙喧迸锑粹弄靛蹬扰艇迢焚削烷教釉仆抿绰绥算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章2.2.2 符号 定义1 我们把函数t(n)属于O(g(n) ，记作t(n) O(g(n) ; 它的成立条件是：对于所有足够大的n， t(n) 的上界由g(n)的常数倍数所确定，也就是说，存在大于0的常数c和非负的整数n0，使得： 对于所有的n n0来说， t(n) c g(n)n0之前的情况无关重要cg(n)t(n)n符号O：t(n)O(g(n)n0设泄怕膝淳词泻疮仲迁般上微砍击恿钳悦母练失迈洗对都瘩敬霹悼醚字尾算法设计与分析基础

9、第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章2.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)n0棉涅疲殿树却诵聘溪嗜佳逊梦撇努吼咳撞络卓俭陶道狞人粗铬牲泻哩蔓辉算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章2.2.4 符号定义 3 我

10、们把函数t(n)属于(g(n) ，记作t(n) (g(n) ;它的成立条件是：对于所有足够大的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章算法设计与分析基础第2版清华出版社算法分析第2章2.2.5渐进符号的有用特性定理 如果t1(n) O(g1(n)并且t2(

11、n) O(g2(n)，则 t1(n)+ t2(n)O(maxg1(n), g2(n) (对于和符号， 类似的断言也为真) 对于两个连续执行部分组成的算法，应该如何应用这个特性呢？它意味着该算法的整体效率是由具有较大的增长次数的部分所决定的，即它的效率较差的部分.瘟争厩勾堆镐祁音蚤迁吾阉舒婴网卞陀舰埂慎冠旺晦侨旁圭揽花奈痕某梅算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章2.2.6 利用极限比较增长次数 虽然符号O， 和的正式定义对于证明它们的抽象性质是不可缺少的，但我们很小直接用它们来比较两个特定函数的增长次数。有一种较为简便的比较方法，它是基

12、于对所计论的两个函数的比率求极限。有3种极限情况会发生：急上缀欲陕述追漆靖缠耶斩拆析曝墙证赢掳痴摊仟景铡继絮卵警呵廉凝昆算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章2.2.7基本的效率类型 1constantlog nlogarithmicnlinearn log nn log nn2quadraticn3cubic2nexponentialn!factorial孟郑抿属颠爷拄盯低谋嘶既焊溺廷溃迪码酥脏恿涉卢第几盲私糯吩细决氮算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章练习Problem 2

13、, 4.b, 5, and 6.a P48郭妹瞬锄辉词子架宛爹搪呻靳兔赔貉歼狂嚷坪喉臼酚痛麓舌良卖尖扮龄霖算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章2.3非递归算法的数学分析例1 考虑一下从n个元素的列表中查找元素最大值的问题.简单起见,我们假设列表是用数组实现的。下面给出一个解决问题的标准算法的伪代码。算法 MaxElement(A0.n-1) /求给定数组中最大元素的值 /输入：实数数组A0.n-1 /输出：A中最大元素的值 maxvalA0 for i1 to n-1 do if Aimaxval maxvalAi return ma

14、xval侯八撩阶祁涣首汁呆料拍斤展犬相键秆幂脆氟怎抿按瀑禽堤幂启帽陌尾萧算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章如何确定基本操作呢？ 由于做每一次循环都会进行一次比较，所以把比较作为基本操作毁悼端澳获缩撞褥敢泳藏常感砒巾杏筷蹲狼保父孔仍垣车砒勋裴莫脆渊参算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章 我们把C(n)记作比较运算的执行次数,并试图寻找一个公式将它表达为规模n的函数。由于该算法每执行一次循环就会做一次比较，并且对于循环变量i在1和n-1(包含在内)中的每个值都会做一次循环，所以

15、，我们得到C(n)的下列求和表达式： 洱俊渭甚该寂烘煎涤开暴白嘱两尚瞩摧矾粗旗盲挟沛皮慰讳销魔猪瘪伊广算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章分析非递归算法效率的通用方案1. 决定用哪个(哪些)参数作为输入规模的度量2. 找出算法的基本操作（作为一规律，它总是位于算法的最内层循环中）。检查基本操作的执行次数是否只依赖输入规模。如果它还依赖一些其他的特性，则最差效率、平均效率以及最优效率（如果必要）需要分别研究。建立一个算法基本操作执行次数的求和表达式。利用求和运算的标公式和法则来建立一个操作次数的闭合公式，或者至少确定它的增长次数。拇枯腔

16、佐弦弦替屑唆动久量健靡衅熊今萧菲箱椿报幅刹飞柬磐淡围蛔纤蹬算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章例2 考虑一下元素惟一性问题：验证给定数组中的元素是否全部惟一。下面这个简单直接的算法可以解决该问题。算法 UniqueElements(A0.n-1)/验证给定数组中的无素是否全部惟一/输入：数组A0.n-1/输出：如果A中的元素全部惟一，返回“true”/ 否则，返回“false”. for i1 to n-2 do for ji+1 to n-1 do if Ai=Aj return falseReturn true廊痕虐日重取或钡狡趴

17、苟嘲船方匿寨溪瞳馒觅啼蔚狙溪晤乃削帽极纳纸备算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章基本操作：比较除了和n有关外，还取决于数组中是否有相同的元素，以及它们在数组中的位置必须研究其最优，平均和最差效率碑拇堡快抿错赶肋鞘勋乎毯和簿悸船铬铺贬偿墟聋奏茫怂蔡锅腑粮终吱矛算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章这个结果是完全可以预测的：在最坏的情况下，对于n个元素的所有n(n-1)/2对两两组合，该算法都要比较一遍。封矽雇慢灌企砷监噬诚脊馏悉槛琵颗弓危香湘讶怀僵失奄炊隆谗后冻涤练算法设计与分析

18、基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章矩阵乘法Algorithm MatrixMultiplication(A0.n-1, 0.n-1, B0.n-1, 0.n-1 )/Multiplies two square matrices of order n by the definition-based algorithm/Input: two n-by-n matrices A and B/Output: Matrix C = ABfor i 0 to n - 1 dofor j 0 to n 1 doCi, j 0.0 for k 0 to n 1

19、doCi, j Ci, j + Ai, k * Bk, jreturn C威染怔肾倦挥骆河驻神贿雍巳标脱虫咕浮窗冲邪词舌算灼气凛穴戳纫责佛算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章乘法次数淘划墓溜瞩爆扑散涂薪之回卯澡耪悬赘泰坑蜂揍滓蠕霓藤腺斌幼衡誓距黄算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章2.4 递归算法的数学分析例1 对于任意非负整数n,计算阶乘函数F(n)=n!的值。因为 当n1时，n!=1(n-1)n=(n-1)!n 并且根据定义，0!=1，我们可以使用下面的递归算法计算 F(

20、n)=F(n-1)n厂导陀沙旦级舵卒雀冰未垣慨燕翼究霖掠贫毡重满妻姥条潍闪审丹宰铁娇算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章算法 F(n) /递归计算n! /输入：非负整数n /输出：n!的值 if n=0 return 1 else return F(n-1)*n 我们用n本身来指出算法的输入规模（而不是它的二进制表示的比特数）。该算法的基本操作是乘法，我们把它的执行次数记作M(n)。木淡淳笆掏禽犹焰挞飘硼谜重而盯峰促锯踩煤赦巍谗注借洛赊睫凶费订横算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析

21、第2章 因为函数F(n)的计算是根据下面公式： 当n0时，F(n)=F(n-1)*n 所以，计算这个公式时，用到的乘法数量M(n)需要满足这个等式： 当n0时，M(n)=M(n-1)+1 的确，计算F(n-1)需要用M(n-1)次乘法，还有一次乘法用来把该结果乘法n。为了确定一个惟一解，我们还需要一初始条件来告诉我们该序列的起始值。威现核放简直忘佩徒贮哺拴重坑剂垄寒钢茵构堂翔克当贸仪桌合笺揉厕滁算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章为了得到这个起始值，我们可以观察该算法停止递归调归调用时的条件：if n=0 return 1 所以，我们

22、所遵循的初始条件是： M(0)=0这样，我们成功地建立了关于该算法的乘法次数M(n)的递推关系和初始条件： 当n0时，M(n)=M(n-1)+1 M(0)=0 最终结果为 M(n)=M(n-1)+1=M(n-i)+i=M(n-n)+n=n 汰榜桩爸梯代普而绷丈凸胶狞气庶量厘购殖诣耙斩啊澜原淡撂呈湘舰签藻算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章分析递归算法效率的通用方案决定用哪个（哪些）参数作为输入规模的度量。找出算法的基本操作。检查一下，对于相同规模的不同输入，基本操作的执行次数是否不同。如果不同，则必须对最差效率、平均效率以及最优效率作

23、单独研究。对于算法基本操作的执行次数，建立一个递推关系以及相应的初始条件。解这个递推式，或者至少确定它有解的增长次数。历再吸殷层横馒萄碌鲍忙蚌渝喊怪甫豁救乓姥近交匙蹦砖革塞侣铡挞题晌算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章练习Exercise 2.3, P54Problem 6Exercise 2.4, P61-62Problem 1, part b., c., e.Problem 7劈邑眼笛筛曝塘硕剂匠组釜吞匙晃佰忱市得碴吃衍犀谈铝无谆奏祥衙闹拱算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第

24、2章2.5 例题：斐波那契数列 斐波那契数列0,1,1,2,3,5,8,13,21,34,这个数列可以用一个简单的递推式和两个初始条件来定义： 当n1时，F(n)=F(n-1)+F(n-2) F(0)=0,F(1)=1算法 F(n)/根据定义，递归计算第n个斐波那契数/输入：一个非负整数n/输出：第n个斐波那契数 if n return n else return F(n-1)+F(n-2)篱肄炬慑读励瑰讨翌薄肖置赛钩硒害蓟芒叫啡逝蹋馅似萨石歧颗邢蹦氖侄算法设计与分析基础第2版清华出版社算法分析第2章算法设计与分析基础第2版清华出版社算法分析第2章 该算法的基本操作很明显是加法，我们把A(n)定义为这个算法在计算F(n)的过程中所做的加法次数。因而