算法分析与设计PPT

1,算法分析与设计,陶军CSdept.李文正楼北203Tel:83790366juntao,2,参考书目,Aho,Hopcroft,Ullman.TheDesignandAnalysisofComputerAlgorithms.（1974版影印版，铁道出版社）Aho,Hopcroft,Ullman.数据结构与算法（1983年影印本，清华出版社）ThomasH.Cormen等4人.算法导论（MIT第2版）,高教出版社影印本潘金贵.现代计算机常用数据结构和算法（南大出版社），即Cormen等3人书第一版的翻译,3,参考书目,M.H.Alsuwaiyel.Algorithms:DesignTechniquesandAnalysis（电子工业出版社影印本，方世昌等译）王晓东.算法设计与分析.（电子工业出版社）SaraBaase等.计算机算法：设计与分析导论（第3版），高教出版社影印本。,4,第一章预备知识,学习要点:理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握用C+语言描述算法的方法。,5,什么是算法？,算法(algorithm)一个（由人或机器进行）关于某种运算规则的集合特点：执行时，不能包含任何主观的决定；不能有类似直觉/创造力等因素。,输出,输入,确定性有限性,清晰、无歧义指令执行次数、时间,6,例子：,人们日常生活中做菜的过程，可否用算法描述？,如：“咸了”、“放点盐”、“再煮一会”。可否用计算机完成？,算法必须规定明确的量与时间；不能含糊字眼。,7,当然不是所有算法都要明确的选择，有些概率算法进行选择。“随机”“随意”有些问题没有实用算法（求解精确解，需要几百年）。,去寻找规则集,在可接受的时间内可以算出足够好的近似解,近似算法,启发式算法,可以预测误差，且误差足够小,误差无法控制，但可预计误差大小,8,如何描述算法,通常，描述算法用类Pascal的结构化编程语言。,9,算法的证明技巧,反证法(proofbycontradication)/间接证明(indirectproof)：为了证明命题的正确性，转而证明该命题的反命题能导致矛盾。例子：欧几里德定理：存在无穷多个素数。证明：假设P为有限素数集，那么显然。且有限，将P中所有元素相乘，X表示积Y=X+1。对Y分析：d为Y的一个最小的且大于1的约数。,10,欧几里德证明,Y1，且不要求d一定不等于Y，d一定存在。d定为素数，否则存在一个约数z，使得z可整除Y。又z,矛盾,=,否则,11,欧几里德证明,矛盾因此，P为无限集合。证毕下面衍生出找素数的一个算法：,12,派生出算法,functionNewprime(P:整数集)变量P为一非空有限的素数集XP中所有元素的乘积;YX+1;d1;repeatdd+1untild整除Y;returnd,通过上述证明d定为素数且,？,13,派生出算法,functionNewprime(P:整数集)XP中所有元素的乘积;YX+1;d1;repeatdd+1untild整除Y;returnd,通过上述证明d定为素数且,functionDumpEuclid(P:整数集)P为非空有限素数集XP中最大的元素;repeatXX+1untilX是素数;returnd,简化,14,算法的证明技巧,归纳法(induction)：特殊=一般法则。例子：铺砖定理铺砖问题总是有解的。,mm个方格(m为2的幂),方格位置随意,瓷砖材料形状为,15,归纳法证明举例-铺砖定理,证明：不妨假设。1)当n=0时，显然成立；n=1时，也显然成立；2)，对大小的地板显然成立，现四分地板得到4个相同大小的地板。,特殊方格地板,也变成存在特殊方格地板地板,证毕,16,归纳法证明举例-马的颜色,例子：伪定理所有马都只有一种颜色。证明：任何一个马的集合都只有一种颜色=所有马只有一种颜色。设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序列给出：递归形式序列以0,1,1,2,3,5,8,13,21,34,Fibonacci序列的算法：FunctionFibonacci(n)ifn0andxi+1tondoifTj0使得对所有nn0有：0f(n)0，存在正数n00使得对所有nn0有：0cg(n)0;p(n)=(nd);f(n)=O(nk)f(n)多项式有界；f(n)=O(1)f(n)c;kdp(n)=O(nk);kdp(n)=(nk);kdp(n)=o(nk);k0:a0=1;a1=a;a-1=1/a;(am)n=amn;(am)n=(an)m;aman=am+n;a1an为单调递增函数;a1nb=o(an),54,ex1+x;|x|11+xex1+x+x2;ex=1+x+(x2),asx0;,55,对数函数logn=log2n;lgn=log10n;lnn=logen;logkn=(logn)kl;loglogn=log(logn);fora0,b0,c0,56,57,|x|1forx-1,foranya0,logbn=o(na),58,阶层函数Stirlingsapproximation,59,60,算法分析中常见的复杂性函数,61,小规模数据,62,中等规模数据,63,用c+描述算法,64,选择语句：if语句：？语句：,if(expression)statement;elsestatement;,exp1?exp2:exp3y=x9?100:200;等价于：if(x9)y=100;elsey=200;,65,switch语句：,switch(expression)case1:statementsequence;break;case2:statementsequence;break;default:statementsequence;,66,迭代语句：for循环：for(init;condition;inc)statement;while循环：while(condition)statement;do-while循环：dostatement;while(condition);,67,跳转语句return语句：returnexpression;goto语句：gotolabel;label:,68,函数：例：,return-typefunctionname(para-list)bodyofthefunction,intmax(intx,inty)returnxy?x:y;,69,templateTypemax(Typex,Typey)returnxy?x:y;inti=max(1,2)；doublex=max(1.0,2.0)；,模板template,70,动态存储分配运算符new运算符new用于动态存储分配。new返回一个指向所分配空间的指针。例：inty；y=newint；y=10；也可将上述各语句作适当合并如下：inty=newint；y=10；或inty=newint(10)；或inty；y=newint(10)；,71,一维数组为了在运行时创建一个大小可动态变化的一维浮点数组x，可先将x声明为一个float类型的指针。然后用new为数组动态地分配存储空间。例：floatx=newfloatn；创建一个大小为n的一维浮点数组。运算符new分配n个浮点数所需的空间，并返回指向第一个浮点数的指针。然后可用x0，x1，xn-1来访问每个数组元素。,72,运算符delete当动态分配的存储空间已不再需要时应及时释放所占用的空间。用运算符delete来释放由new分配的空间。例：deletey；deletex；分别释放分配给y的空间和分配给一维数组x的空间。,73,动态二维数组创建类型为Type的动态工作数组，这个数组有rows行和cols列。,templatevoidMake2DArray(Type*,74,当不再需要一个动态分配的二维数组时，可按以下步骤释放它所占用的空间。首先释放在for循环中为每一行所分配的空间。然后释放为行指针分配的空间。释放空间后将x置为0，以防继续访问已被释放的空间。,templatevoidDelete2DArray(Type*,75,算法分析方法,例：顺序搜索算法,templateintseqSearch(Type*a,intn,Typek)for(inti=0;in;i+)if(ai=k)returni;return-1;,76,Tmax(n)=maxT(I)|size(I)=n=O(n)Tmin(n)=minT(I)|size(I)=n=O(1)在平均情况下，假设：搜索成功的概率为p(0p1)；在数组的每个位置i(0in)搜索成功的概率相同，均为p/n。,77,算法分析的基本法则,非递归算法：for/while循环循环体内计算时间*循环次数；嵌套循环循环体内计算时间*所有循环次数；顺序语句各语句计算时间相加；if-else语句if语句计算时间和else语句计算时间的较大者。,78,templatevoidinsertion_sort(Type*a,intn)Typekey;/costtimesfor(inti=1;i=0/c7n-1,79,在最好情况下，ti=1,for1in;在最坏情况下，tii+1,for1in;,80,对于输入数据ai=n-i,i=0,1,n-1，算法insert