算法分析与设计PPT

1、1 算法分析与设计算法分析与设计 陶陶 军军 CS dept. 李文正楼北李文正楼北203 Tel: 83790366 2 参考书目 nAho, Hopcroft, Ullman. The Design and Analysis of Computer Algorithms. （1974版影印版，铁 道出版社） nAho, Hopcroft, Ullman. 数据结构与算法（1983 年影印本，清华出版社） nThomas H. Cormen 等4人. 算法导论（MIT第2 版）, 高教出版社影印本 n潘金贵. 现代计算机常用数据结构和算法（南大 出版社），即Cormen等3人书第一版的翻译

2、3 参考书目 nM. H. Alsuwaiyel. Algorithms: Design Techniques and Analysis（电子工业出版社影印 本，方世昌等译） n王晓东. 算法设计与分析.（电子工业出版社） nSara Baase等. 计算机算法：设计与分析导论 （第3版），高教出版社影印本。 4 第一章 预备知识 n学习要点: n理解算法的概念。 n理解什么是程序，程序与算法的区别和内在联 系。 n掌握算法的计算复杂性概念。 n掌握算法渐近复杂性的数学表述。 n掌握用C+语言描述算法的方法。 5 什么是算法？ n算法(algorithm) n一个（由人或机器进行）关于某种运算

3、规则的集合 n特点： n执行时，不能包含任何主观的决定； n不能有类似直觉/创造力等因素。 规则 输出输入 确定性 有限性 清晰、无歧义 指令执行次数、时间 6 例子： n人们日常生活中做菜的过程，可否用算法 描述？ 如：“咸了”、“放点盐”、“再煮一会”。 可否用计算机完成？ n算法必须规定明确的量与时间； n不能含糊字眼。 7 n当然不是所有算法都要明确的选择，有些 概率算法进行选择。 n“随机”“随意” n有些问题没有实用算法（求解精确解，需 要几百年）。 去寻找规则集规则集 在可接受的时间内可以算出足够好的近似解 近似算法近似算法 启发式算法启发式算法 可以预测误差，可以预测误差， 且

4、误差足够小且误差足够小 误差无法控制，误差无法控制， 但可预计误差大小但可预计误差大小 8 如何描述算法 n通常，描述算法用类Pascal的结构化编程语言。 9 算法的证明技巧 n反证法(proof by contradication)/间接证明(indirect proof)： 为了证明命题的正确性，转而证明该命题的反 命题能导致矛盾。 n例子： 欧几里德欧几里德 定理：存在无穷多个素数。 证明：假设P为有限素数集，那么显然 。 且有限， 将P中所有元素相乘，X表示积 Y=X+1。 对Y分析：d为Y的一个最小的且大于1的约数。 P P 10 欧几里德证明 Y1，且不要求d一定不等于Y， d一

5、定存在。 d定为素数，否则存在一个约数z，使得z可整除Y。 又 z 矛盾矛盾 Pd = 0d 否则否则1moddY 11 欧几里德证明 矛盾矛盾 因此，P为无限集合。 证毕证毕 下面衍生出找素数的一个算法：下面衍生出找素数的一个算法： 12 派生出算法 function Newprime(P:整数集) 变量P为一非空有限的素数集 XP中所有元素的乘积; YX+1; d1; repeat dd+1 until d整除Y; return d 通过上述证明通过上述证明d定为定为 素数且素数且 Pd ？ 13 派生出算法 function Newprime(P:整数集) XP中所有元素的乘积; YX+

6、1; d1; repeat dd+1 until d整除Y; return d 通过上述证明通过上述证明d定为定为 素数且素数且 Pd function DumpEuclid(P:整数集) P为非空有限素数集 XP中最大的元素中最大的元素; repeat XX+1 until X是素数是素数; return d 简化简化 14 算法的证明技巧 n归纳法(induction)： 特殊特殊=一般法则一般法则。 n例子：铺砖定理铺砖定理 铺砖问题总是有解的。 mm个方格(m为2的幂) 方格位置随意 瓷砖材料形状为 15 归纳法证明举例-铺砖定理铺砖定理 证明：不妨假设 。 1)当n=0时，显然成立；

7、n=1时，也显然成立； 2) ， ，对 大小的地板显然成 立，现四分地板得到4个相同大小的地板。 1n n m2 11 22 nn n m2 特殊方格地板也变成存在特殊 方格地板地板 证毕证毕 16 归纳法证明举例-马的颜色马的颜色 n例子：伪定理伪定理 所有马都只有一种颜色。 证明：任何一个马的集合都只有一种颜色 =所有马只有一种颜色。 设H为任何一个马的集合，对H中马数量n归纳： 1)n=0， 成立；n=1，显然成立。 2)设H中的马为h1, h2, hn，由于任意n-1匹马的集合有唯一 的颜色，那么 对两个集合应用归纳假设： H具有同种颜色。？ H 17 归纳法证明举例-马的颜色马的颜色

8、 ， 正确 必须 ，从2=3，3=4， 不能1=2。 1n0n 3n 18 归纳法证明举例-斐波纳契序列斐波纳契序列 n例子：Fibonacci序列序列 每个月一对繁殖期的兔子会 产生一对后代，而这对后代2个月后又会繁殖。 即 第1个月买了1对兔子；第2个月仍只有1对；第3 个月有2对 依此类推，如兔子不死亡，那么各月的兔子数由Fibonacci 序列给出：递归形式 序列以0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 2 , 1 ; 0 21 10 nfff ff nnn Fibonacci序列的算法： Function Fibonacci(n) if n0 and xi+

9、1 to n do if Tjmin x then min jj; min xTj; Tmin jTi; Timin x; 选择排序 /从array中选最小的，放到数组开头； 再选第2小，放到第2位置上 25 平均和最坏情况分析平均和最坏情况分析 n设设u和和v是两个长度为是两个长度为n的数组，的数组，u中元素已按升中元素已按升 序排序；序排序；v按降序排序。按降序排序。 n对任意次序的数组，对任意次序的数组，选择排序选择排序时间影响不大，时间影响不大，“if Tj排序一个随机次序排序一个随机次序array的时间耗费。的时间耗费。 已排序已排序最坏情况最坏情况 太难！太难！ 27 平均和最坏情

10、况分析平均和最坏情况分析 n分析算法平均情况难于最坏情况。分析算法平均情况难于最坏情况。 n特别特别 n实例不随机实例不随机那么平均情况那么平均情况可能误入歧途可能误入歧途。 最好有一个实例分布的先验知识。最好有一个实例分布的先验知识。 28 算法好坏的衡量尺度 n用所需的计算时间来衡量一个算法的好坏，用所需的计算时间来衡量一个算法的好坏， 不同的机器相互之间无法比较。不同的机器相互之间无法比较。 n能否有一个独立于具体计算机的客观衡量标准能否有一个独立于具体计算机的客观衡量标准。 n面介绍几个常见的衡量标准。面介绍几个常见的衡量标准。 n问题的规模问题的规模 n基本运算基本运算 n算法的计算

11、量函数算法的计算量函数 29 问题的规模问题的规模 n问题的规模：一个或多个整数，作为输入问题的规模：一个或多个整数，作为输入 数据量的测度。数据量的测度。 n数表的长度数表的长度(数据项的个数数据项的个数)，(问题：在一个问题：在一个 数据表中寻找数据表中寻找X)； n矩阵的最大维数矩阵的最大维数(阶数阶数) (问题：求两个实矩阵问题：求两个实矩阵 相乘的结果相乘的结果) n输入规模通常用输入规模通常用n来表示，也可有两个以来表示，也可有两个以 上的参数上的参数 n图中的顶点数和边数图中的顶点数和边数(图论中的问题图论中的问题) 30 基本运算基本运算(elementary operatio

12、n) n概念：概念： n指执行时间可以被一个常数限定，只与指执行时间可以被一个常数限定，只与环境环境有关。有关。 n因此，分析时只需要关心执行的基本运算次数，因此，分析时只需要关心执行的基本运算次数， 而不是它们执行确切时间。而不是它们执行确切时间。 n例子：例子： 机器、语言编译机器、语言编译 smattt stmtatt sma sma ,max 只和只和基本运算基本运算相关相关 31 基本运算基本运算(elementary operation) n一般可以认为加法和乘法都是一个单位开一般可以认为加法和乘法都是一个单位开 销的运算。销的运算。 n理论上，这些运算都不是基本运算，因为操理论上

13、，这些运算都不是基本运算，因为操 作数的作数的长度长度影响了执行时间。影响了执行时间。 n实际，只要实例中操作数长度相同，即实际，只要实例中操作数长度相同，即 可认为是基本运算。可认为是基本运算。 32 基本运算基本运算(elementary operation) n例如例如 n在一个表中寻找数据元素在一个表中寻找数据元素x：x与表中的一个与表中的一个 项进行比较；项进行比较； n两个实矩阵的乘法：实数的乘法（及加法）两个实矩阵的乘法：实数的乘法（及加法） C=AB； n将一个数表进行排序，表中的两个数据项进将一个数表进行排序，表中的两个数据项进 行比较。行比较。 n通常情况下，讨论一个算法优

14、劣时，我们通常情况下，讨论一个算法优劣时，我们 只讨论基本算法的执行次数。只讨论基本算法的执行次数。 因为它是占支配地位的，其他运算可以忽略。因为它是占支配地位的，其他运算可以忽略。 33 基本运算基本运算 function Sum(n) 计算1n整数的累加和 sum0 for i1 to n do sumsum+i return sum 只要只要n0，存在正数n0 0 使得对所有n n0有：0 f(n)0，存在正数n0 0使得对所有n n0有：0 cg(n) f(n) n等价于 f(n) / g(n) ，as n。 nf(n) (g(n) g(n) o (f(n) n紧渐近界记号紧渐近界记号

15、 n (g(n) = f(n) | 存在正常数c1, c2和n0使得对所有 n n0有：c1g(n) f(n) c2g(n) 46 例：渐近意义下的O n如果存在常数C和自然数N0，使得当N N0时，有 f(n)Cg(n)，则称函数f(n)当N充分大时上有界，且 g(n)是它的一个上界，记为f(n)=O(g(n)。 n也即f(n)的阶不高于g(n)的阶。 n ， ； n ， ； n ， ； n ， ； n ，无 使得 ； 1N NONNN343 1N NONNN102410251024 10N 2222 10112310112NONNNNN 1N 3232 NONNN 23 NON 0 NN

16、反例反例 23 CNN CN 47 O的运算性质 n n n n如果 ； n ，C是一个正常数； n 下面考察性质的证明：下面考察性质的证明： gfOgOfO,max gfOgOfO gfOgOfO fOgOfONfONg NfONcfO fOf 48 性质：性质： 设设 。根据符号。根据符号O的定义，存在正的定义，存在正 常数常数C1和自然数和自然数N1，使对所有，使对所有 ，都，都 有有 。 ，设，设 ，则存在正的常数，则存在正的常数C2和自和自 然数然数N2， 有有 。 gfOgOfO,max 证明：证明： fONF 1 NN NfCNF 1 类似地类似地 gONG 2 NN NgCNG

17、 2 49 令令 213 ,maxCCC 213 ,maxNNN gfNh,max)( 同理同理 3 NN NhCNhCNfCNF 311 NhCNhCNgCNG 322 所以所以 gfOhONhC NhCNhCNGNFgOfO ,max2 3 33 证毕。证毕。 性质：性质： gfOgOfO,max 50 算法渐近复杂性分析常用函数算法渐近复杂性分析常用函数 n单调函数单调函数 n单调递增：m n f(m) f(n) ; n单调递减：m n f(m) f(n); n严格单调递增：m n f(m) f(n); n严格单调递减：m f(n). n取整函数取整函数 n x ：不大于x的最大整数；

18、n x ：不小于x的最小整数。 51 取整函数的若干性质取整函数的若干性质 n x-1 x x x 0，有： n n/a /b = n/ab ; n n/a /b = n/ab ; n a/b (a+(b-1)/b; n a/b (a-(b-1)/b; n f(x)= x , g(x)= x 为单调递增函数。 52 n多项式函数多项式函数 n p(n)= a0+a1n+a2n2+adnd； ad0; n p(n) = (nd); n f(n) = O(nk) f(n)多项式有界； n f(n) = O(1) f(n) c; n k d p(n) = O(nk) ; nk d p(n) = (n

19、k) ; nk d p(n) = o(nk) ; nk 0: n a0=1; n a1=a ; n a-1=1/a ; n (am)n = amn ; n(am)n = (an)m ; n aman = am+n ; n a1 an为单调递增函数; n a1 nb = o(an) 0lim n b n a n 54 nex 1+x; n|x| 1 1+x ex 1+x+x2 ; n ex = 1+x+ (x2), as x0; 0 32 ! 3! 2 1 i i x i xxx xe x n n e n x 1lim 55 n对数函数对数函数 n log n = log2n; n lg n =

20、 log10n; n ln n = logen; n logkn = (log n)kl; n log log n = log(log n); n for a0,b0,c0 a b ba log 56 baab ccc loglog)(log ana b n b loglog b a a c c b log log log aa bb log)/1 (log b a a b log 1 log ac bb ca loglog 57 n|x| 1 nfor x -1, nfor any a 0, , logbn = o(na) . 5432 )1ln( 5432 xxxx xx xx x x )

21、1ln( 1 0 log lim )2( log lim log a b n na b n n nn 58 n阶层函数阶层函数 nStirlings approximation 0 0 )!1( 1 ! n n nn n nn321! ne n nn n 1 12! 59 n e e n nn n 2! nn n 12 1 112 1 )(! n non )2(! n n )log() !log(nnn 60 算法分析中常见的复杂性函数算法分析中常见的复杂性函数 61 小规模数据小规模数据 62 中等规模数据中等规模数据 63 用用c+描述算法描述算法 64 n选择语句：选择语句： nif 语

22、句：语句： n？语句：？语句： if (expression) statement; else statement; exp1?exp2:exp3 y= x9 ? 100:200; 等价于： if (x9) y=100; else y=200; 65 nswitch语句：语句： switch (expression) case 1: statement sequence; break; case 2: statement sequence; break; default: statement sequence; 66 n迭代语句：迭代语句： nfor 循环：循环： for (init;cond

23、ition;inc) statement; nwhile 循环：循环： while (condition) statement; ndo-while 循环：循环： do statement; while (condition); 67 n跳转语句跳转语句 nreturn语句：语句： return expression; ngoto语句：语句： goto label; label: 68 n函数：函数： n例：例： return-type function name(para-list) body of the function int max(int x,int y) return xy?x:

24、y; 69 template Type max(Type x,Type y) return xy?x:y; int i=max(1,2)； double x=max(1.0,2.0)； n 模板模板template 70 n动态存储分配动态存储分配 n运算符运算符new 运算符new用于动态存储分配。 new返回一个指向所分配空间的指针。 n例：int y；y=new int；y=10； 也可将上述各语句作适当合并如下： nint y=newint；y=10； n或 int y=new int(10)； n或 int y；y=new int(10)； 71 n一维数组一维数组 n为了在运行时创

25、建一个大小可动态变化的一维 浮点数组x，可先将x声明为一个float类型的指 针。然后用new为数组动态地分配存储空间。 例：例： float x=new floatn； n创建一个大小为n的一维浮点数组。运算符new 分配n个浮点数所需的空间，并返回指向第一个 浮点数的指针。 n然后可用x0，x1，xn-1来访问每个数组 元素。 72 n运算符运算符delete n当动态分配的存储空间已不再需要时应及时释 放所占用的空间。 n用运算符delete来释放由new分配的空间。 n例：例：delete y；delete x； n分别释放分配给y的空间和分配给一维数组x的 空间。 73 n动态二维数

26、组动态二维数组 n创建类型为Type的动态工作数组，这个数组有 rows行和cols列。 template void Make2DArray(Type* for (int i=0;irows;i+) xi=new Typecols; 74 n当不再需要一个动态分配的二维数组时，可按以下步 骤释放它所占用的空间。首先释放在for循环中为每一 行所分配的空间。然后释放为行指针分配的空间。 n释放空间后将x置为0，以防继续访问已被释放的空间。 template void Delete2DArray(Type* irows;i+) delete xi; delete x; x=0; 75 算法分析方法

27、算法分析方法 n例：顺序搜索算法例：顺序搜索算法 template int seqSearch(Type *a, int n, Type k) for(int i=0;in;i+) if (ai=k) return i; return -1; 76 nTmax(n) = max T(I) | size(I)=n =O(n) nTmin(n) = min T(I) | size(I)=n =O(1) n在平均情况下，假设： n搜索成功的概率为p ( 0 p 1 )； n在数组的每个位置i ( 0 i n )搜索成功的概率相同，均 为 p/n。 nIsize avg ITIpnT )( )()()( pn n p n n p n p n p 1321 )1 ( 2 ) 1( 1 1 pn np pni n p n i 77 算法分析的基本法则算法分析的基本法则 n非递归算法：非递归算法： nfor / while 循环 循环体内计算时间*循环次数； n嵌套循环 循环体内计算时间*所有循环次数； n顺序语句 各语句计算时间相加； nif-else语句 if语句计算时间和else语句计算时