算法分析与设计PPT.ppt

《算法分析与设计PPT.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计PPT.ppt（82页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、法(proof by contradication)/间接证明(indirect proof)：为了证明命题的正确性，转而证明该命题的反命题能导致矛盾。n例子：欧几里德欧几里德 定理：存在无穷多个素数。证明：假设P为有限素数集，那么显然 。且有限，将P中所有元素相乘，X表示积Y=X+1。对Y分析：d为Y的一个最小的且大于1的约数。10欧几里德证明Y1，且不要求d一定不等于Y，d一定存在。d定为素数，否则存在一个约数z，使得z可整除Y。又 z矛盾矛盾=否则否则11欧几里德证明 矛盾矛盾因此，P为无限集合。证毕证毕下面衍生出找素数的一个算法：下面衍生出找素数的一个算法：12派生出算法functio

5、n 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为非空有限素数集XP中最大的元素;repeat XX+1 until X是素数;return d简化简化14算法的证明技巧n归

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

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

8、0 and xi+1 to n doif 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平均和最坏情况分析平均和最

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

10、题的规模n问题的规模：一个或多个整数，作为输入问题的规模：一个或多个整数，作为输入数据量的测度。数据量的测度。n数表的长度数表的长度(数据项的个数数据项的个数)，(问题：在一个数问题：在一个数据表中寻找据表中寻找X)；n矩阵的最大维数矩阵的最大维数(阶数阶数)(问题：求两个实矩阵问题：求两个实矩阵相乘的结果相乘的结果)n输入规模通常用输入规模通常用n来表示，也可有两个以上来表示，也可有两个以上的参数的参数n图中的顶点数和边数图中的顶点数和边数(图论中的问题图论中的问题)30基本运算基本运算(elementary operation)n概念：概念：n指执行时间可以被一个常数限定，只与指执行时间可

11、以被一个常数限定，只与环境环境有关。有关。n因此，分析时只需要关心执行的基本运算次数，因此，分析时只需要关心执行的基本运算次数，而不是它们执行确切时间。而不是它们执行确切时间。n例子：例子：机器、语言编译机器、语言编译只和只和基本运算基本运算相关相关31基本运算基本运算(elementary operation)n一般可以认为加法和乘法都是一个单位开一般可以认为加法和乘法都是一个单位开销的运算。销的运算。n理论上，这些运算都不是基本运算，因为操作理论上，这些运算都不是基本运算，因为操作数的数的长度长度影响了执行时间。影响了执行时间。n实际，只要实例中操作数长度相同，即实际，只要实例中操作数长度

12、相同，即可认为是基本运算。可认为是基本运算。32基本运算基本运算(elementary operation)n例如例如n在一个表中寻找数据元素在一个表中寻找数据元素x：x与表中的一个项与表中的一个项进行比较；进行比较；n两个实矩阵的乘法：实数的乘法（及加法）两个实矩阵的乘法：实数的乘法（及加法）C=AB；n将一个数表进行排序，表中的两个数据项进行将一个数表进行排序，表中的两个数据项进行比较。比较。n通常情况下，讨论一个算法优劣时，我们通常情况下，讨论一个算法优劣时，我们只讨论基本算法的执行次数。只讨论基本算法的执行次数。因为它是占支配地位的，其他运算可以忽略。因为它是占支配地位的，其他运算可以

13、忽略。33基本运算基本运算function Sum(n)计算1n整数的累加和sum0for i1 to n dosumsum+ireturn 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紧渐近界记号紧渐近界记号 n(g(n)=f(n)|存在正常数c1,c2和n0使得对所有n n0有：c1g(n)f(n)c2g(n)46例：渐近意义下的On如果存在常数C和自然数N0，使得当N N0时，有f(n)Cg(n)，则称函数f(n)当N

14、充分大时上有界，且g(n)是它的一个上界，记为f(n)=O(g(n)。n也即f(n)的阶不高于g(n)的阶。n ，；n ，；n ，；n ，；n ，无 使得 ；反例反例47O的运算性质n n n n如果 ；n ，C是一个正常数；n 下面考察性质的证明：下面考察性质的证明：48性质：性质：设设 。根据符号。根据符号O的定义，存在正的定义，存在正常数常数C1和自然数和自然数N1，使对所有，使对所有 ，都，都有有 。，设，设 ，则存在正的常数，则存在正的常数C2和自和自然数然数N2，有有 。证明：证明：类似地类似地49令令 同理同理所以所以证毕。证毕。性质：性质：50算法渐近复杂性分析常用函数算法渐近

15、复杂性分析常用函数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的最大整数；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 为单调递增函数。52n多项式函数多项式函数n p(n)=a0+a1n+a2n2+adnd；ad0;n

16、 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)=(nk);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)54nex 1+x;n|x|1 1+x ex 1+x+x2;n ex=1+x+(x2),as x0;55n对数函数对数函数n log n=log2n;n lg n=log10n;n ln n=logen;n logk

17、n=(log n)kl;n log log n=log(log n);n for a0,b0,c05657n|x|1 nfor x -1,nfor any a 0,logbn=o(na)58n阶层函数阶层函数nStirlings approximation 5960算法分析中常见的复杂性函数算法分析中常见的复杂性函数61小规模数据小规模数据62中等规模数据中等规模数据63用用c+描述算法描述算法64n选择语句：选择语句：nif 语句：语句：n？语句：？语句：if(expression)statement;else statement;exp1?exp2:exp3 y=x9?100:200;等价

18、于：if(x9)y=100;else y=200;65nswitch语句：语句：switch(expression)case 1:statement sequence;break;case 2:statement sequence;break;default:statement sequence;66n迭代语句：迭代语句：nfor 循环：循环：for(init;condition;inc)statement;nwhile 循环：循环：while(condition)statement;ndo-while 循环：循环：do statement;while(condition);67n跳转语句跳转

19、语句nreturn语句：语句：return expression;ngoto语句：语句：goto label;label:68n函数：函数：n例：例：return-type function name(para-list)body of the function int max(int x,int y)return xy?x:y;69template Type max(Type x,Type y)return xy?x:y;int i=max(1,2)；double x=max(1.0,2.0)；n 模板模板template70n动态存储分配动态存储分配n运算符运算符new运算符new用于动态

20、存储分配。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)；71n一维数组一维数组n为了在运行时创建一个大小可动态变化的一维浮点数组x，可先将x声明为一个float类型的指针。然后用new为数组动态地分配存储空间。例：例：float x=new floatn；n创建一个大小为n的一维浮点数组。运算符new分配n个浮点数所需的空间，并返回指向第一个浮点数的指针。n然后可用x0，x1，xn-1来访问每个数组元

21、素。72n运算符运算符deleten当动态分配的存储空间已不再需要时应及时释放所占用的空间。n用运算符delete来释放由new分配的空间。n例：例：delete y；delete x；n分别释放分配给y的空间和分配给一维数组x的空间。73n动态二维数组动态二维数组n创建类型为Type的动态工作数组，这个数组有rows行和cols列。template void Make2DArray(Type*&x,int rows,int cols)x=new Type*rows;for(int i=0;irows;i+)xi=new Typecols;74n当不再需要一个动态分配的二维数组时，可按以下步骤

22、释放它所占用的空间。首先释放在for循环中为每一行所分配的空间。然后释放为行指针分配的空间。n释放空间后将x置为0，以防继续访问已被释放的空间。template void Delete2DArray(Type*&x,int rows)for(int i=0;irows;i+)delete xi;delete x;x=0;75算法分析方法算法分析方法n例：顺序搜索算法例：顺序搜索算法templateint seqSearch(Type*a,int n,Type k)for(int i=0;in;i+)if(ai=k)return i;return-1;76nTmax(n)=max T(I)|si

23、ze(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。77算法分析的基本法则算法分析的基本法则n非递归算法：非递归算法：nfor/while 循环循环体内计算时间*循环次数；n嵌套循环循环体内计算时间*所有循环次数；n顺序语句各语句计算时间相加；nif-else语句if语句计算时间和else语句计算时间的较大者。78templatevoid insertion_sort(Type*a,int n)Type key;/cost times

24、 for(int i=1;i=0&ajkey)/c4 sum of ti aj+1=aj;/c5 sum of(ti-1)j-;/c6 sum og(ti-1)aj+1=key;/c7 n-1 79n在最好情况下，ti=1,for 1 i n;n在最坏情况下，ti i+1,for 1 i n;80n对于输入数据ai=n-i,i=0,1,n-1，算法insertion_sort 达到其最坏情形。因此，n由此可见，Tmax(n)=(n2)81最优算法最优算法n问题的计算时间下界为(f(n)，则计算时间复杂性为O(f(n)的算法是最优算法。n例如，排序问题的计算时间下界为(nlogn)，计算时间复杂性为O(nlogn)的排序算法是最优算法。n堆排序算法是最优算法。82递归算法复杂性分析递归算法复杂性分析 int factorial(int n)if(n=0)return 1;return n*factorial(n-1);