第2 章 算法效率分析

西南科技大学算分析与设计第二章算法效率分析算法效率（Efficiency）算法效率有什么作用算法效率是怎样度量的，评价算法优劣的依据是什么怎样完成算法算法效率分析西南科技大学算分析与设计算法的复杂性算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。西南科技大学算分析与设计算法效率有什么作用不言而喻，对于任意给定的问题，设计出复杂性尽可能低的算法是我们在设计算法的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。西南科技大学算分析与设计问题怎样完成算法算法效率分析？用怎样的一个量来表达一个算法的复杂性；对于给定的一个算法，怎样具体计算它的复杂性。西南科技大学算分析与设计复杂性的计量（一）算法的复杂性是算法运行所需要的计算机资源的量，需要的时间资源的量称作时间复杂性，需要的空间（即存储器）资源的量称作空间复杂性。这个量应该集中反映算法中所采用的方法的效率，而从运行该算法的实际计算机中抽象出来。换句话说，这个量应该是只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A来表示算法要解问题的规模、算法的输入和算法本身，用C表示算法的复杂性，那么应该有：C=F(N,I,A)西南科技大学算分析与设计复杂性的计量（二）其中F(N,I,A)是N,I,A的一个确定的三元函数。如果把时间复杂性和空间复杂性分开，并分别用T和S来表示，那么应该有：T=T(N,I,A)(2.1.1)和S=S(N,I,A)(2.1.2)通常，我们让A隐含在复杂性函数名当中，因而将（2.1.1）和（2.1.2）分别简写为：T=T(N,I)和S=S(N,I)。由于时间复杂性和空间复杂性概念类同，计算方法相似，且空间复杂性分析相对地简单些，所以将主要地讨论时间复杂性。西南科技大学算分析与设计复杂性的计量（三）根据T(N,I)的概念，它应是算法在一台抽象计算机上运行所需的时间。设此抽象计算机所提供的元运算有k种，记为O1，O2，...，Ok；再设这些元运算每执行一次所需要的时间分别为t1，t2，...，tk。对于给定的算法A，设经过统计，用到元运算Oi的次数分别为ei，i=1，2，...，k，很明显，对每一个i，1=i=k，ei是N和I的函数，即ei=ei(N,I)。那么有：T(N,I)=∑tiei(N,I)(2.1.3)其中{ti|i=1,2,..,k},是与N,I无关的常数。西南科技大学算分析与设计复杂性的计量（四）下面只考虑三种情况的复杂性，即最坏情况、最好情况和平均情况下的时间复杂性，并分别记为Tmax(N)、Tmin(N)和Tavg(N)。在数学上有：其中，DN是规模为N的合法输入的集合；I*是DN中一个使T(N,I*)达到Tmax(N)的合法输入，I~是DN中一个使T(N,I~)到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。西南科技大学算分析与设计复杂性的计量（五）以上三种情况下的时间复杂性各从某一个角度来反映算法的效率，各有各的用处，也各有各的局限性。但实践表明可操作性最好的且最有实际价值的是最坏情况下的时间复杂性。一般来说，最好情况和最坏情况的时间复杂性是很难计量的，原因是对于问题的任意确定的规模N达到了Tmax(N)的合法输入难以确定，而规模N的每一个输入的概率也难以预测或确定。我们有时也按平均情况计量时间复杂性，但那时在对P(I)做了一些人为的假设（比如等概率）之后才进行的。所做的假设是否符合实际总是缺乏根据。因此，在最好情况和平均情况下的时间复杂性分析还仅仅是停留在理论上。西南科技大学算分析与设计复杂性的渐近性（一）随着经济的发展、社会的进步、科学研究的深入，要求用计算机解决的问题越来越复杂，规模越来越大。但是，如果对这类问题的算法进行分析时，把所有的元运算都考虑进去，精打细算，那么，由于问题的规模很大且结构复杂，算法分析的工作量之大、步骤之繁将令人难以承受。因此，人们提出了对于规模充分大、结构又十分复杂的问题的求解算法，其复杂性分析应如何简化的问题。西南科技大学算分析与设计复杂性的渐近性（二）设T(N)是在第二段中所定义的关于算法A的复杂性函数。一般说来，当N单调增加且趋于∞时,T(N)也将单调增加趋于∞。对于T(N)，如果存在T’(N)，使得当N→∞时有：(T(N)-T’(N))/T(N)→0我们就说T’(N)是T(N)当N→∞时的渐近性态，或叫T’(N)为算法A当N→∞的渐近复杂性而与T(N)相区别，因为在数学上，T’(N)是T(N)当N→∞时的渐近表达式。T’(N)是T(N)中略去低阶项所留下的主项。所以它无疑比T(N)来得简单。比如当T(N)=3N2+4Nlog2N+7时，T’(N)的一个答案是3N2，显然3N2比3N2+4Nlog2N+7简单得多。西南科技大学算分析与设计复杂性的渐近性（三）考虑到分析算法的复杂性的目的在于比较求解同一间题的两个不同算法的效率，而当要比较的两个算法的渐近复杂性的阶不相同时，只要能确定出各自的阶，就可以判定哪一个算法的效率高。换句话说，这时的渐近复杂性分析只要关心T’(N)的阶就够了，不必关心包含在T’(N)中的常数因子。所以，我们常常又对T’(N)的分析进--步简化，即假设算法中用到的所有不同的元运算各执行一次，所需要的时间都是一个单位时间。由此，只要考察当问题的规模充分大时，算法复杂性在渐近意义下的阶。与此简化的复杂性分析方法相配套，需要引入五个渐近意义下的记号：Ο（奥密克戎）、Ω（欧米伽）、θ（西塔）、ο和ω。西南科技大学算分析与设计复杂性的渐近性（四）设f(N)和g(N)是定义在正数集上的正函数。如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≤Cg(N)。则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=Ο(g(N))。这时我们还说f(N)的阶不高于g(N)的阶。根据记号Ο的定义，用它评估算法的复杂性，得到的只是当规模充分大时的一个上界。这个上界的阶越低则评估就越精确，结果就越有价值。西南科技大学算分析与设计复杂性的渐近性（五）按照大Ο的定义，容易证明它有如下运算规则：Ο(f)+Ο(g)=Ο(max(f,g))；Ο(f)+Ο(g)=Ο(f+g)；Ο(f)·Ο(g)=Ο(f·g)；如果g(N)=Ο(f(N))，则Ο(f)+Ο(g)=Ο(f)；Ο(Cf(N))=Ο(f(N))，其中C是一个正的常数；f=Ο(f)；西南科技大学算分析与设计复杂性的渐近性（六）估计下面二重循环算法段在最坏情况下的时间复杂性T(N)的阶。for(i=l;iN;i++)for(j=l;jN;j++){S1;S2;S3;S4;}其中Sk(k=1,2,3,4)是单一的赋值语句。对于内循环体，显然只需Ο(l)时间。因而内循环只需时间。累加起来便是外循环的时间复杂性：西南科技大学算分析与设计复杂性的渐近性（七）记号Ω，定义如下：如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≥Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为f(N)=Ω(g(N))。这时我们还说f(N)的阶不低于g(N)的阶。西南科技大学算分析与设计复杂性的渐近性（八）Ω的这个定义的优点是与Ο的定义对称，缺点是当f(N)对自然数的不同无穷子集有不同的表达式，且有不同的阶时，未能很好地刻画出f(N)的下界。比如当：时，如果按上述定义，只能得到f(N)=Ω(1)，这是一个平凡的下界，对算法分析没有什么价值。西南科技大学算分析与设计复杂性的渐近性（九）用Ω评估算法的复杂性，得到的只是该复杂性的一个下界。这个下界的阶越高，则评估就越精确，结果就越有价值。对于一个问题和任意给定的充分大的规模N，下界在该问题的所有算法或某类算法的复杂性中取，那么它将更有意义。这时得到的相应下界，我们称之为问题的下界或某类算法的下界。它常与Ο配合证明问题的某个特定算法是该问题的最优算法或是在某算法类中的最优算法。西南科技大学算分析与设计复杂性的渐近性（十）定义f(N)=θ(g(N))，有f(N)=Ο(g(N))且f(N)=Ω(g(N))。这时，我们说f(N)与g(N)同阶。对于任意给定的ε≥0，都存在非负整数N0，使得当N≥N0时有f(N)≤εg(N)，则称函数f(N)当N充分大时比g(N)低阶，记为f(N)=o(g(N))，例如：4NlogN+7=o(3N2+4NlogN+7)；f(N)=ω(g(N))定义为g(N)=o(f(N))。即当N充分大时f(N)的阶比g(N)高。我们看到Ο对于O有如ω对于Ω。西南科技大学算分析与设计复杂性的渐近性（十一）以下表述虽不很精确，但可帮助记忆：f=Ο(g)↔f≤gf=Ω(g)↔f≥gf=θ(g)↔f=gf=o(g)↔fgf=ω(g)↔fg西南科技大学算分析与设计复杂性渐近阶的重要性（一）随着计算机的设计和制造技术的突飞猛进，计算机的计算速度和存储容量在直线增长。有人从而认为不必要再去苦苦地追求高效算法，不必去无谓地进行复杂性的分析。以为低效的算法可以由高速的计算机来弥补。但实际上，计算机解决的问题复杂程度和规模的线性增长，对低效算法来说，导致的时耗和空间需求是以几何的方式增长的，计算机速度和容量的需求将入不付出。西南科技大学算分析与设计算法与渐近阶的关系（一）设A1,A2,…和A6，它们的渐近时间复杂性分别为N，NlogN，N2，N3，2N，N!，是求解同一间题的6种不同的算法，这六种算法分别在C1和C2两台计算机上运行，设计算机C2的计算速度是计算机C1的10倍。在可接受的一段时间内，设在C1上算法Ai可能求解的问题的规模为N1i，而在C2上可能求解的问题的规模为N2i，那么，我们就应该有Ti(N2i)=10Ti(N1i)，其中Ti(N)是算法Ai渐近的时间复杂性，i=1,2,…,6。分别解出N2i和N1i的关系，可列成下表。西南科技大学算分析与设计表2-1算法渐进时间复杂性T(N)在C1上可解的规模N1在C2上可解的规模N2N1和N2的关系A1NN11N21N21=10N11A2NlogNN12N22N22≈10N12A3N2N13N23N23=101/2N13A4N3N14N24N23=101/3N14A52NN15N25N25=N15+log10A6N!N16N26N26=N16+小的常数西南科技大学算分析与设计算法与渐近阶的关系（二）从表2-1可以清楚地看到，对于低效的算法，计算速度增长基本上不带来求解规模的增益。对表的最后一列观察发现，限制求解问题规模的关键因素是算法渐近复杂性的阶。可见，算法的渐近复杂性的阶对于算法的效率有着决定性的意义。所以在讨论算法的复杂性时基本上都只关心它的渐近阶。多项式算法是有效的算法。绝大多数的问题都有多项式算法。但也有一些问题还未找到多项式算法，只找到指数型算法。西南科技大学算分析与设计算法与渐近阶的关系（三）“复杂性的渐近阶比较低的算法比复杂性的渐近阶比较高的算法有效”这个结论，只是在问题的求解规模充分大时才成立。比如算法A4比A5有效只是在N32N，即N≥c时才成立。其中c是方程N3=2N的解。当Nc时，A5反而比A4有效。所以对于规模小的问题，不要盲目地选用复杂性阶比较低的算法。其原因一方面是如上所说，复杂性阶比较低的算法在规模小时不一定比复杂性阶比较高的算法更有效；另方面，在规模小时，决定工作效率的可能不是算法的效率而是算法的简单性，哪一种算法简单，实现起来快，就选用那一种算法。西南科技大学算分析与设计算法与渐近阶的关系（四）当要比较的两个算法的渐