算法分析与设计PPT

1、1,算法分析与设计,cs dept. 李文正楼北203 tel: 83790366 ,2,参考书目,aho, hopcroft, ullman. the design and analysis of computer algorithms. （1974版影印版，铁道出版社） aho, hopcroft, ullman. 数据结构与算法（1983年影印本，清华出版社） thomas h. cormen 等4人. 算法导论（mit第2版）, 高教出版社影印本 潘金贵. 现代计算机常用数据结构和算法（南大出版社），即cormen等3人书第一版的翻译,3,参考书目,m. h. alsuwaiyel.

2、algorithms: design techniques and analysis（电子工业出版社影印本，方世昌等译） 王晓东. 算法设计与分析.（电子工业出版社） sara baase等. 计算机算法：设计与分析导论（第3版），高教出版社影印本。,4,第一章 预备知识,学习要点: 理解算法的概念。 理解什么是程序，程序与算法的区别和内在联系。 掌握算法的计算复杂性概念。 掌握算法渐近复杂性的数学表述。 掌握用c+语言描述算法的方法。,5,什么是算法？,算法(algorithm) 一个（由人或机器进行）关于某种运算规则的集合 特点： 执行时，不能包含任何主观的决定； 不能有类似直觉/创造力等

3、因素。,输出,输入,确定性 有限性,清晰、无歧义 指令执行次数、时间,6,例子：,人们日常生活中做菜的过程，可否用算法描述？,如：“咸了”、“放点盐”、“再煮一会”。 可否用计算机完成？,算法必须规定明确的量与时间； 不能含糊字眼。,7,当然不是所有算法都要明确的选择，有些概率算法进行选择。 “随机”“随意” 有些问题没有实用算法（求解精确解，需要几百年）。,去寻找规则集,在可接受的时间内可以算出足够好的近似解,近似算法,启发式算法,可以预测误差， 且误差足够小,误差无法控制， 但可预计误差大小,8,如何描述算法,通常，描述算法用类pascal的结构化编程语言。,9,算法的证明技巧,反证法(p

4、roof by contradication)/间接证明(indirect proof)：为了证明命题的正确性，转而证明该命题的反命题能导致矛盾。 例子： 欧几里德 定理：存在无穷多个素数。 证明：假设p为有限素数集，那么显然 。 且有限， 将p中所有元素相乘，x表示积 y=x+1。 对y分析：d为y的一个最小的且大于1的约数。,10,欧几里德证明,y1，且不要求d一定不等于y， d一定存在。 d定为素数，否则存在一个约数z，使得z可整除y。 又 zd ，且x是p中所有元素的积 d是x的约数 即d可以同时整除x和y=x+1。 对于 ，可以同时整除连续整数是不可能。,d为y的一个最小的约数,=,

5、矛盾,=,否则,11,欧几里德证明,矛盾 因此，p为无限集合。 证毕 下面衍生出找素数的一个算法：,12,派生出算法,function newprime(p:整数集) 变量p为一非空有限的素数集 xp中所有元素的乘积; yx+1; d1; repeat dd+1 until d整除y; return d,通过上述证明d定为素数且,？,13,派生出算法,function newprime(p:整数集) xp中所有元素的乘积; yx+1; d1; repeat dd+1 until d整除y; return d,通过上述证明d定为素数且,function dumpeuclid(p:整数集) p为非

6、空有限素数集 xp中最大的元素; repeat xx+1 until x是素数; return d,简化,14,算法的证明技巧,归纳法(induction)： 特殊=一般法则。 例子：铺砖定理 铺砖问题总是有解的。,mm个方格(m为2的幂),方格位置随意,瓷砖材料形状为,15,归纳法证明举例-铺砖定理,证明：不妨假设 。 1)当n=0时，显然成立；n=1时，也显然成立； 2) ， ，对 大小的地板显然成立，现四分地板得到4个相同大小的地板。,特殊方格地板,也变成存在特殊 方格地板地板,证毕,16,归纳法证明举例-马的颜色,例子：伪定理 所有马都只有一种颜色。 证明：任何一个马的集合都只有一种颜

7、色 =所有马只有一种颜色。 设h为任何一个马的集合，对h中马数量n归纳： 1)n=0， 成立；n=1，显然成立。 2)设h中的马为h1, h2, hn，由于任意n-1匹马的集合有唯一的颜色，那么 对两个集合应用归纳假设： h具有同种颜色。？,17,归纳法证明举例-马的颜色,， 正确 必须 ，从2=3，3=4， 不能1=2。,18,归纳法证明举例-斐波纳契序列,例子：fibonacci序列 每个月一对繁殖期的兔子会产生一对后代，而这对后代2个月后又会繁殖。 即 第1个月买了1对兔子；第2个月仍只有1对；第3个月有2对 依此类推，如兔子不死亡，那么各月的兔子数由fibonacci序列给出：递归形式

8、 序列以0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ,fibonacci序列的算法： function fibonacci(n) if n2 then return n; else return fibonacci(n-1)+fibonacci(n-2);,19,如何选择算法？,当解决一个问题时，存在几种算法可供选择，如何决定哪个最好？ 两种研究方法： 经验(empirical)：对各种算法编程，用不同实例实验； 理论(theoretical)：以数学化的方式确定算法所需要资源数与实例大小之间函数关系。,算法效率算法的快慢,20,如何选择算法？,当解决一个问题时，存在几种

9、算法可供选择，如何决定哪个最好？ 两种研究方法： 经验(empirical)：对各种算法编程，用不同实例实验； 理论(theoretical)：以数学化的方式确定算法所需要资源数与实例大小之间函数关系。,常用某些方法度量实例中某些构件数的数量。例如排序： 以参与排序的项数表示实例大小； 讨论图时，常用图的节点/边来表示； critical循环的层数。,计算机上用紧凑代码表示实例时，需占比特。,21,如何选择算法？,两种研究方法特点： 理论法优点：既不依赖于计算机，也不依赖于语言/编程技能。节省了无谓编程时间；可研究任何在实例上算法效率。 而经验法却不能，特别：只有用于处理大的实例时才显示出来。

10、,22,什么单位表示算法效率？,对于一个给定的函数t，如果存在一个正的常数c，而该算法的一个实现对每个大小为n的实例都能用不超过ct(n) 秒的时间来解决。 那么该算法的开销在t(n)级内。,23,平均和最坏情况分析,一个算法的时间耗费/空间耗费，对于不同的实例都会有所不同。 procedure insert(t1.n) for i2 to n do xti; ji-1; while j0 and xtj do tj+1tj; jj-1; tj+1x;,插入排序,/从第2列到第n个元素，把该元素插入到之前的数组相应位置上,24,平均和最坏情况分析,procedure select(t1.n)

11、for i1 to n-1 do min ji; min xti; for ji+1 to n do if tjmin x then min jj; min xtj; tmin jti; timin x;,选择排序,/从array中选最小的，放到数组开头；再选第2小，放到第2位置上,25,平均和最坏情况分析,设u和v是两个长度为n的数组，u中元素已按升序排序；v按降序排序。 对任意次序的数组，选择排序时间影响不大，“if tjmin x”都会执行相同次数，区别在于：then的执行次数。 插入排序有所不同：对数组u，因为while循环总是假，insert(u)只用了线性时间。,26,平均和最坏情

12、况分析,另一方面insert(v)花费二次时间。 两个实例的时间差随着元素个数增加而增加。 算法解决一个实例的时间取决于最坏情况(worst case)。 最精确的是分析算法的平均响应时间： 例如：对于插入排序的时间开销在n到n2变动。 因为存在n!种初始排列，所以最好求出n!种初始排序时间=排序一个随机次序array的时间耗费。,已排序,最坏情况,太难！,27,平均和最坏情况分析,分析算法平均情况难于最坏情况。 特别 实例不随机那么平均情况可能误入歧途。,最好有一个实例分布的先验知识。,28,算法好坏的衡量尺度,用所需的计算时间来衡量一个算法的好坏，不同的机器相互之间无法比较。 能否有一个独

13、立于具体计算机的客观衡量标准。 面介绍几个常见的衡量标准。 问题的规模 基本运算 算法的计算量函数,29,问题的规模,问题的规模：一个或多个整数，作为输入数据量的测度。 数表的长度(数据项的个数)，(问题：在一个数据表中寻找x)； 矩阵的最大维数(阶数) (问题：求两个实矩阵相乘的结果) 输入规模通常用n来表示，也可有两个以上的参数 图中的顶点数和边数(图论中的问题),30,基本运算(elementary operation),概念： 指执行时间可以被一个常数限定，只与环境有关。 因此，分析时只需要关心执行的基本运算次数，而不是它们执行确切时间。 例子：,机器、语言编译,只和基本运算相关,31

14、,基本运算(elementary operation),一般可以认为加法和乘法都是一个单位开销的运算。 理论上，这些运算都不是基本运算，因为操作数的长度影响了执行时间。 实际，只要实例中操作数长度相同，即可认为是基本运算。,32,基本运算(elementary operation),例如 在一个表中寻找数据元素x：x与表中的一个项进行比较； 两个实矩阵的乘法：实数的乘法（及加法）c=ab； 将一个数表进行排序，表中的两个数据项进行比较。 通常情况下，讨论一个算法优劣时，我们只讨论基本算法的执行次数。 因为它是占支配地位的，其他运算可以忽略。,33,基本运算,function sum(n) 计算

15、1n整数的累加和 sum0 for i1 to n do sumsum+i return sum 只要n231-1，都可成功。 乘法更易产生一个大数，所以运算不溢出很重要。 操作数长度增加，加法运算时间开销线性增加，而乘法却快得多。,function fibonacci(n) 计算fibonacci序列第n项 i0; j0 for k1 to n do ji+j; ij-i return j n=47在32位机上会溢出。,34,怎样提高效率？,硬件速度增加，算法效率还那么重要吗？ 大小为n的实例的执行，需要 s 。则： 计算机性能提高100倍，那么需要 s。 还是求不出n=45的实例 即 新的

16、计算机最多解决n+lg100的实例，n+7。,扩大210倍,扩大210 210倍,至多解n=38,假设,35,怎样提高效率？,改进算法，在原来计算机上，需 s。 因此，用一天可以解决大小超过200的实例，一年处理n=1500实例。,假设,36,怎样提高效率？,37,算法的复杂性,算法的复杂性是算法运行所需计算机资源的量。 需要时间的时间复杂性； 需要空间的空间复杂性。 反映算法的效率，并与运算计算机独立。 依赖于问题的规模，输入和算法本身，用c表示。 c=f(n, i, a)是一个三元函数。,时间t,s空间复杂度,两者类似，但s简单,让a隐含到函数中,所以通常研究t(n,i)在一台抽象计算机上

17、运行所需时间。,38,算法的计算量函数,用输入规模的某个函数来表示算法的基本运算量，称为算法的时间复杂性(度)。 用t(n)或t(n, m)来表示，例如： t(n)=5n t(n)=3nlog n t(n)=4n3 t(n)=2n t(n, m)=2(n+m),39,t(n, m)的概念,设抽象计算机的元运算有k种，记为o1, , ok，每执行一次所需时间为t1, , tk。 对算法a，用到元运算oi 的次数为ei 与n，i相关。,40,t(n, m)的概念,我们不可能规模n的每种合法输入i都去统计ei(n, i)，对于i我们分别考虑：最坏情况、最好情况、平均情况。,合法输入集,41,复杂性渐

18、进性态,设 是前面定义的算法a复杂性函数。 n递增到无限大，t(n)递增到无限大 如存在 ，使 时，有 称 是 当 的渐进性态。 在数学上， 是 当 的渐进表达式，通常 是 中略去低阶项所留下的主项。 比 简单。,42,复杂性渐进性态,例如： 由 因为 ， 所以有理由用 来替代 来度量a。,43,衡量算法的效率,当比较两个算法的渐近复杂性的阶不同时，只要确定各自的阶，即可判定哪个算法效率高。 等价于 只要关心 的阶即可，不必考虑其中常数因子。 对 的分析进一步简化，假设算法中用到的所有不同元运算各执行一次需要的时间都是一个单位时间。 简化算法复杂性分析的方法和步骤，只要考察问题的规模充分大时，

19、算法复杂性在渐近意义下的阶。,44,渐近分析的记号,下面的讨论中，对所有n，f(n) 0，g(n) 0。 渐近上界记号o o(g(n)= f(n) | 存在正常数c和n0使得对所有n n0有：0 f(n) cg(n) 渐近下界记号 (g(n)= f(n) | 存在正常数c和n0使得对所有n n0有：0 cg(n) f(n) 非紧上界记号o o(g(n)= f(n) | 对于任何正常数c0，存在正数n0 0使得对所有n n0有：0 f(n)cg(n) 等价于 f(n) / g(n) 0 ，as n。,45,渐近分析的记号(cont.),非紧下界记号 (g(n) = f(n) | 对于任何正常数c

20、0，存在正数n0 0使得对所有n n0有：0 cg(n) f(n) 等价于 f(n) / g(n) ，as n。 f(n) (g(n) g(n) o (f(n) 紧渐近界记号 (g(n) = f(n) | 存在正常数c1, c2和n0使得对所有n n0有：c1g(n) f(n) c2g(n) ,46,例：渐近意义下的o,如果存在常数c和自然数n0，使得当n n0时，有f(n)cg(n)，则称函数f(n)当n充分大时上有界，且g(n)是它的一个上界，记为f(n)=o(g(n)。 也即f(n)的阶不高于g(n)的阶。 ， ； ， ； ， ； ， ； ，无 使得 ；,反例,47,o的运算性质,如果

21、； ，c是一个正常数； 下面考察性质的证明：,48,性质：,设 。根据符号o的定义，存在正常数c1和自然数n1，使对所有 ，都有 。 ，设 ，则存在正的常数c2和自然数n2， 有 。,证明：,类似地,49,令,同理,所以,证毕。,性质：,50,算法渐近复杂性分析常用函数,单调函数 单调递增：m n f(m) f(n) ; 单调递减：m n f(m) f(n); 严格单调递增：m f(n). 取整函数 x ：不大于x的最大整数； x ：不小于x的最小整数。,51,取整函数的若干性质,x-1 0，有： n/a /b = n/ab ; n/a /b = n/ab ; a/b (a+(b-1)/b;

22、a/b (a-(b-1)/b; f(x)= x , g(x)= x 为单调递增函数。,52,多项式函数 p(n)= a0+a1n+a2n2+adnd； ad0; p(n) = (nd); f(n) = o(nk) f(n)多项式有界； f(n) = o(1) f(n) c; k d p(n) = o(nk) ; k d p(n) = (nk) ; k d p(n) = o(nk) ; k d p(n) = (nk) .,53,指数函数 对于正整数m,n和实数a0: a0=1; a1=a ; a-1=1/a ; (am)n = amn ; (am)n = (an)m ; aman = am+n

23、; a1 an为单调递增函数; a1 nb = o(an),54,ex 1+x; |x| 1 1+x ex 1+x+x2 ; ex = 1+x+ (x2), as x0;,55,对数函数 log n = log2n; lg n = log10n; ln n = logen; logkn = (log n)kl; log log n = log(log n); for a0,b0,c0,56,57,|x| 1 for x -1, for any a 0, , logbn = o(na),58,阶层函数 stirlings approximation,59,60,算法分析中常见的复杂性函数,61,

24、小规模数据,62,中等规模数据,63,用c+描述算法,64,选择语句： if 语句： ？语句：,if (expression) statement; else statement;,exp1?exp2:exp3 y= x9 ? 100:200; 等价于： if (x9) y=100; else y=200;,65,switch语句：,switch (expression) case 1: statement sequence; break; case 2: statement sequence; break; default: statement sequence; ,66,迭代语句： for

25、 循环： for (init;condition;inc) statement; while 循环： while (condition) statement; do-while 循环： do statement; while (condition);,67,跳转语句 return语句： return expression; goto语句： goto label; label:,68,函数： 例：,return-type function name(para-list) body of the function ,int max(int x,int y) return xy?x:y; ,69,t

26、emplate type max(type x,type y) return xy?x:y; int i=max(1,2)； double x=max(1.0,2.0)；,模板template,70,动态存储分配 运算符new 运算符new用于动态存储分配。 new返回一个指向所分配空间的指针。 例：int y；y=new int；y=10； 也可将上述各语句作适当合并如下： int y=newint；y=10； 或 int y=new int(10)； 或 int y；y=new int(10)；,71,一维数组 为了在运行时创建一个大小可动态变化的一维浮点数组x，可先将x声明为一个floa

27、t类型的指针。然后用new为数组动态地分配存储空间。 例： float x=new floatn； 创建一个大小为n的一维浮点数组。运算符new分配n个浮点数所需的空间，并返回指向第一个浮点数的指针。 然后可用x0，x1，xn-1来访问每个数组元素。,72,运算符delete 当动态分配的存储空间已不再需要时应及时释放所占用的空间。 用运算符delete来释放由new分配的空间。 例：delete y；delete x； 分别释放分配给y的空间和分配给一维数组x的空间。,73,动态二维数组 创建类型为type的动态工作数组，这个数组有rows行和cols列。,template void make2darray(type* ,74,当不再需要一个动态分配的二维数组时，可按以下步骤释放它所占用的空间。首