算法分析与设计PPT

1算法分析与设计陶军CSdept.李文正楼北203Tel:[e-mail]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的约数。PP10[欧几里德]证明Y1，且不要求d一定不等于Y，d一定存在。d定为素数，否则存在一个约数z，使得z可整除Y。又zd，且X是P中所有元素的积d是X的约数即d可以同时整除X和Y=X+1。对于，可以同时整除连续整数是不可能。d为Y的一个最小的约数=矛盾Pd=0d否则1moddY11[欧几里德]证明矛盾因此，P为无限集合。[证毕]下面衍生出找素数的一个算法：12派生出算法functionNewprime(P:整数集){变量P为一非空有限的素数集}XP中所有元素的乘积;YX+1;d1;repeatdd+1untild整除Y;returnd通过上述证明d定为素数且Pd？13派生出算法functionNewprime(P:整数集)XP中所有元素的乘积;YX+1;d1;repeatdd+1untild整除Y;returnd通过上述证明d定为素数且PdfunctionDumpEuclid(P:整数集){P为非空有限素数集}XP中最大的元素;repeatXX+1untilX是素数;returnd简化14算法的证明技巧归纳法(induction)：特殊=一般法则。例子：[铺砖定理]铺砖问题总是有解的。m×m个方格(m为2的幂)方格位置随意瓷砖材料形状为15归纳法证明举例-铺砖定理证明：不妨假设。1)当n=0时，显然成立；n=1时，也显然成立；2)，，对大小的地板显然成立，现四分地板得到4个相同大小的地板。1nnm21122nnnm2特殊方格地板也变成存在特殊方格地板地板[证毕]16归纳法证明举例-马的颜色例子：[伪定理]所有马都只有一种颜色。证明：任何一个马的集合都只有一种颜色=所有马只有一种颜色。设H为任何一个马的集合，对H中马数量n归纳：1)n=0，成立；n=1，显然成立。2)设H中的马为h1,h2,…hn，由于任意n-1匹马的集合有唯一的颜色，那么对两个集合应用归纳假设：H具有同种颜色。？HH1h2h3h4…hnH2h1h3h4…hnH1一种颜色H2一种颜色H1和H2同种颜色=17归纳法证明举例-马的颜色，正确必须，从2=3，3=4，…不能1=2。1n0n3n18归纳法证明举例-斐波纳契序列例子：[Fibonacci序列]每个月一对繁殖期的兔子会产生一对后代，而这对后代2个月后又会繁殖。即第1个月买了1对兔子；第2个月仍只有1对；第3个月有2对…依此类推，如兔子不死亡，那么各月的兔子数由Fibonacci序列给出：递归形式序列以0,1,1,2,3,5,8,13,21,34,…2,1;02110nfffffnnnFibonacci序列的算法：FunctionFibonacci(n)ifn2thenreturnn;elsereturnFibonacci(n-1)+Fibonacci(n-2);19如何选择算法？当解决一个问题时，存在几种算法可供选择，如何决定哪个最好？两种研究方法：经验(Empirical)：对各种算法编程，用不同实例实验；理论(Theoretical)：以数学化的方式确定算法所需要资源数与实例大小之间函数关系。算法效率算法的快慢时间/空间★20如何选择算法？当解决一个问题时，存在几种算法可供选择，如何决定哪个最好？两种研究方法：经验(Empirical)：对各种算法编程，用不同实例实验；理论(Theoretical)：以数学化的方式确定算法所需要资源数与实例大小之间函数关系。常用某些方法度量实例中某些构件数的数量。例如排序：以参与排序的项数表示实例大小；讨论图时，常用图的节点/边来表示；critical循环的层数。计算机上用紧凑代码表示实例时，需占比特。21如何选择算法？两种研究方法特点：理论法优点：既不依赖于计算机，也不依赖于语言/编程技能。节省了无谓编程时间；可研究任何在实例上算法效率。而经验法却不能，特别：只有用于处理大的实例时才显示出来。22什么单位表示算法效率？对于一个给定的函数t，如果存在一个正的常数C，而该算法的一个实现对每个大小为n的实例都能用不超过Ct(n)秒的时间来解决。那么该算法的开销在t(n)级内。23平均和最坏情况分析一个算法的时间耗费/空间耗费，对于不同的实例都会有所不同。Procedureinsert(T[1..n])fori2tondoxT[i];ji-1;whilej0andxT[j]doT[j+1]T[j];jj-1;T[j+1]x;插入排序//从第2列到第n个元素，把该元素插入到之前的数组相应位置上12324平均和最坏情况分析ProcedureSelect(T[1..n])fori1ton-1dominji;minxT[i];forji+1tondoifT[j]minxthenminjj;minxT[j];T[minj]T[i];T[i]minx;选择排序//从array中选最小的，放到数组开头；再选第2小，放到第2位置上…25平均和最坏情况分析设u和v是两个长度为n的数组，u中元素已按升序排序；v按降序排序。对任意次序的数组，选择排序时间影响不大，“ifT[j]minx”都会执行相同次数，区别在于：then的执行次数。插入排序有所不同：对数组u，因为while循环总是假，insert(u)只用了线性时间。26平均和最坏情况分析另一方面insert(v)花费二次时间。两个实例的时间差随着元素个数增加而增加。算法解决一个实例的时间取决于最坏情况(worstcase)。最精确的是分析算法的平均响应时间：例如：对于插入排序的时间开销在n到n2变动。因为存在n!种初始排列，所以最好求出n!种初始排序时间=排序一个随机次序array的时间耗费。已排序最坏情况太难！！27平均和最坏情况分析分析算法平均情况难于最坏情况。特别实例不随机那么平均情况可能误入歧途。最好有一个实例分布的先验知识。28算法好坏的衡量尺度用所需的计算时间来衡量一个算法的好坏，不同的机器相互之间无法比较。能否有一个独立于具体计算机的客观衡量标准。面介绍几个常见的衡量标准。问题的规模基本运算算法的计算量函数29问题的规模问题的规模：一个或多个整数，作为输入数据量的测度。数表的长度(数据项的个数)，(问题：在一个数据表中寻找X)；矩阵的最大维数(阶数)(问题：求两个实矩阵相乘的结果)输入规模通常用n来表示，也可有两个以上的参数图中的顶点数和边数(图论中的问题)30基本运算(elementaryoperation)概念：指执行时间可以被一个常数限定，只与环境有关。因此，分析时只需要关心执行的基本运算次数，而不是它们执行确切时间。例子：机器、语言编译a次加法，一个加≤ta；m次乘法，一个乘≤tm；s次赋值，一个赋值≤ts；smatttstmtattsmasma,,max只和基本运算相关31基本运算(elementaryoperation)一般可以认为加法和乘法都是一个单位开销的运算。理论上，这些运算都不是基本运算，因为操作数的长度影响了执行时间。实际，只要实例中操作数长度相同，即可认为是基本运算。32基本运算(elementaryoperation)例如在一个表中寻找数据元素x：x与表中的一个项进行比较；两个实矩阵的乘法：实数的乘法（及加法）C=AB；将一个数表进行排序，表中的两个数据项进行比较。通常情况下，讨论一个算法优劣时，我们只讨论基本算法的执行次数。因为它是占支配地位的，其他运算可以忽略。33基本运算functionSum(n){计算1~n整数的累加和}sum0fori1tondosumsum+ireturnsum只要n231-1，都可成功。乘法更易产生一个大数，所以运算不溢出很重要。操作数长度增加，加法运算时间开销线性增加，而乘法却快得多。functionFibonacci(n){计算Fibonacci序列第n项}i0;j0fork1tondoji+j;ij-ireturnjn=47在32位机上会溢出。34怎样提高效率？硬件速度增加，算法效率还那么重要吗？大小为n的实例的执行，需要s。则：计算机性能提高100倍，那么需要s。还是求不出n=45的实例即新的计算机最多解决n+lg100的实例，n+7。n210410421010n20421020n30421030n扩大210倍扩大210×210倍至多解n=38假设n210635怎样提高效率？改进算法，在原来计算机上，需s。因此，用一天可以解决大小超过200的实例，一年处理n=1500实例。假设3210n10nmin2~120nmin5.430ns1036怎样提高效率？计算时间(s)10210110-110310410551015202530354010-4×2n10-6×2n10-2×n3实例大小37算法的复杂性算法的复杂性是算法运行所需计算机资源的量。需要时间的时间复杂性；需要空间的空间复杂性。反映算法的效率，并与运算计算机独立。依赖于问题的规模，输入和算法本身，用C表示。C=F(N,I,A)是一个三元函数。时间TS空间复杂度两者类似，但S简单让A隐含到函数中所以通常研究T(N,I)在一台抽象计算机上运行所需时间。38算法的计算量函数用输入规模的某个函数来表示算法的基本运算量