算法分析与设计第2章

1、 每节一经典计算机科学是问题驱动的科学纯数学是理论驱动的科学算法分析的目的（1）深入准确理解问题本质及可能的求解技术（2）探讨某种具体算法适用于解决哪类问题，或某类问题宜采用哪种算法算法评价指标体系 运行时间 存贮空间 易理解 易编码 易调试 易维护第2章 算法分析基础时间复杂度估算 算法执行时间=（原操作的执行次数原操作的执行时间） 语句频度：指语句重复执行的次数 一个算法中所有语句的频度之和构成了该算法的运行时间。例1. for(j=1;j=n;j=j+1) for(k=1;k=n;k=k+1) x=x+1语句 x=x+1,k=n,k=k+1的频度分别均是n2; 总频度是：3n2语句 j=

2、1的频度是1语句 k=1,j=n,j=j+1的频度均为n；总频度：3n因此，算法运行时间(语句总频度)为：3n2 +3n+1第2章 算法分析基础时间复杂度估算 如果算法比较复杂，通常选择一种对于所研究的问题来说最基本的原操作，以它在算法中重复执行的次数作为算法运行时间的衡量标准。 这个原操作多数情况下是最深层循环体内语句中的操作。例2.2. 矩阵乘法算法：for(i=1;i=n;i=i+1) for(j=1;j=n;j=j+1) ci,j=0； for(k=1;k=n;k=k+1) ci,j=ci,j+ai,k*bk,j; 第2讲 算法分析基础该算法最重要的基本操作是语句 ci,j=ci,j+

3、ai,k*bk,j由于它在三重循环之内，所以它的频度是n3. 我们称该算法的时间复杂度是O(n3).大O表示法 例2.3 当一个算法的运行时间为表达式3n4+n2+1时，由于当n足够大时，表达式的值约等于n4,我们说该表达式与n4的数量级相等，称n4为这个算法的渐近时间复杂度，简称算法的时间复杂度，记作：T(n)=O(n4). 其中，O是Order的首字母，表示数量级。两个表达式f(n)与g(n)的数量级相等定义如下：定义2.1 设f(n)和g(n)是一个关于正整数n的函数，如果存在一个常数C,使极限则称f(n)和g(n)是相同数量级的函数。第2讲 算法分析基础常用算法时间复杂度表示形式 O(

4、1): 常数级，如 3； O(logn): 对数级，如log3n；O(n): 线性级，如5n; O(nc): 多项式级,如n3; O(cn): 指数级，如2n ; O(n！): 阶乘级,如3n!以上时间复杂度的大小排列如图所示。对复杂算法，可以把它分隔成容易估算的几个部分，然后再利用O的求和原则得到算法总的时间复杂度。T(n)=T1(n)+ T2(n)+ Tm(n) =O(max(f1(n), f2(n), fm(n) 第2讲 算法分析基础算法时间复杂度上、下界复杂度上、下界是用来估计解决某个问题所需资源（时间、空间）的复杂程度的界限函数。注意：算法复杂度与问题复杂度的区别。如果找到解决某问题

5、的算法，算法复杂度为u(n),则u(n)是问题本身复杂度的一个上界。如果对解决某个问题的所有算法而言， 算法复杂度均大于l(n),则l(n)是该问题复杂度的一个下界。算法所需的时间总量的上界用符号O表示，定义为：定义2.2 设f(n)和g(n)是一个关于正整数n的函数，如果存在两个正整数c和n0,对 于所有的nn0,有|f(n)|c|g(n)|,则记作 f(n)=O(g(n)。算法所需的时间总量的下界用符号表示，定义为：定义2.3 设f(n)和g(n)是一个关于正整数n的函数，如果存在两个正整数c和n0,对 于所有的nn0,有|f(n)|c|g(n)|,则记作 f(n)=(g(n)。第2讲 算

6、法分析基础小o和表示法定义2.4 设f(n)和g(n)是一个关于正整数n的函数，当f(n)=O(g(n)，f(n)=(g(n)）时f(n)和g(n)同阶，记作f(n)=(g(n)定义2.5 设f(n)和g(n)是一个关于正整数n的函数，如果对任意0，都存在非负整数n0,使得当nn0时, 有f(n)g(n)）,则称当n充分大时，f(n)比g(n)低阶，记作 f(n)=o(g(n).定义2.6 设f(n)和g(n)是一个关于正整数n的函数，如果对任意0，都存在非负整数n0,使得当nn0时, 有g(n) (f(n)）,则称当n充分大时，f(n)比g(n)高阶，记作 f(n)= (g(n). 可以看出

7、，o对O, 对第2讲 算法分析基础最好情况下的时间复杂性 指时间复杂度下界，记作Tmax最坏情况下的时间复杂性 指时间复杂度上界，记作Tmin平均情况下的时间复杂性 指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。 记作Tavg. 我们关注的重点是： Tmin第2讲 算法分析基础算法空间复杂性 （1）输入数据所占空间：与问题本身有关，与算法无关。 （2）算法（程序）本身所占空间：大小相对固定。 （3）辅助变量所占空间：不同算法空间数量可能不同。算法空间复杂性：指算法在执行过程中所占辅助存贮空间的大小，记为S(n)， S(n)=O(f(n)表示随着问题规模n的增大，算法运行所需要

8、的存贮空间数量的增长率与f(n)的增长率相同。第2讲 算法分析基础问题分类（不是算法分类） P问题：对一个问题p而言，存在多项式时间算法能够解决该问题，那么称问题p为P问题。也称为易求解问题。 P类问题：所有的P问题的集合。 P类问题是易解问题，非P类问题是难解问题。 NP问题：能够在多项式时间内验证一个解是否正确的问题，称为NP问题。也称为易验证问题。 NP类问题：所有的NP问题的集合。 NP完全类问题：NP类问题中复杂性最高的一个子类，称为NP完全类问题。第2讲 算法分析基础P类问题、NP类问题、NP完全类问题之间的关系 重要结论： 定理2.1 任取NP类中的一个问题np,再任取NP完全类

9、中的一个问题npc,则一定存在一个具有多项式时间复杂性的算法，可以把NP问题np转变成NPC问题npc. 求解问题 判定问题定理1表明，只要能够证明NP完全类中有一个问题是属于P类的，也就证明了NP类中的所有问题都是P类的，即P=NP. P=NP ？不幸的是，这是一个世界一级难题！第2讲 算法分析基础P类问题NP类问题NP完全类问题？存在多项式算法：把一个NP问题转化为NP完全问题NP完全类问题是最难解的一类问题 可以使用的方法： 近似算法:多项式近似算法，求近似解来代替最优解。 启发式算法：利用启发式策略，如蚂蚁算法求最优解或近似解。方法有效，但很难说清它的道理。 概率分析方法,动态规划方法

10、，分支限界方法等.第2讲 算法分析基础算法分析实例 （1）非递归算法分析 1）依赖于问题规模的时间复杂度 T(n)=O(1): 如果算法的执行时间不是随问题规模n的增加而增长，即使算法中有成千上万条语句，其执行时间仍然是一个较大的常数，即f(n)=C,则称此类算法的时间复杂度是O(1）。 例2.1 temp=i i=j j=temp 则上述三个算法的时间复杂度均为T(n)=O(1)第2讲 算法分析基础i=1J=2K=3H=4S=i+j+k+hi=1J=2K=3H=4S=i*j+k*h算法分析实例例2.2 循环次数直接依赖问题规模n以上算法中频度最大的语句是: y=y+1,其频度f(n)=n2,

11、所以，该算法的时间复杂度是：T(n)=O(n2)例2.3 循环次数间接依赖问题规模n以上算法中频度最大的语句是: x=x+1,其频度需要从内循环向外循环逐层计算： 第2讲 算法分析基础x=0;y=0;For(k=1;k=n;k=k+1) x=x+1;For(i=1;i=n;i=i+1) For(j=1;j=n;j=j+1) y=y+1;x=1;Input(n);For(i=1;i=n;i=i+1) For(j=1;j=i;j=j+1) For(k=1;k=j;k=k+1) x=x+1; 则f(n)=n3/6, 所以T(n)=O(n3). 2）依赖于输入实例的初始状态 例2.4 在数组a0.n-

12、1中查找给定值k的算法为： 12, 23, 34, 80, 21, 38, 40, 2 a0 a1 a7把循环语句while中的比较操作aik作为主要操作。这是因为比较操作比i=i+1更复杂。算法的频度不仅与问题规模n有关，还与输入实例数组a0.n-1的元素取值及k值有关： 第2讲 算法分析基础i=n-1;While (i=0 and aik) i=i+1;Return i 若数组a中没有等于k值的元素，则语句2的频度f(n)=n,这是最坏情形。 若数组a的最后一个元素等于k，则语句2的频度f(n)=1,这是最好情形。 一般情形下需要求平均复杂度。 假设在n个元素中每个元素被查找的概率P是相同

13、的（1/n），则所有元素被查找的总次数(算法的平均复杂度)为： （2）递归算法分析 1)递归模型 例2.5 求阶乘 n!=? 先看一个简单实例： 5！=5*4！=5*4*3！=5*4*3*2！=5*4*3*2*1！=120, 这里，0！=1！=1, 归纳阶乘公式：n!=n*(n-1)!=n*(n-1)*(n-2)!=第2讲 算法分析基础 因此，求阶乘 n!算法如下： fact(int n) (1) if (n=0 or n=1) (2) return (1); (3) else (4) return(n*fact(n-1); (5) 递归算法需要数据结构“栈(stack)”来存贮中间结果，再回

14、溯求解。第2讲 算法分析基础当n=5时，算法计算5！过程如下：执行语句1：转语句(3)-(4)， 结果得到：5*fact(4);再调用函数fact(4):执行语句1：转语句(3)-(4),结果得到：5*4*fact(3);再调用函数fact(3):执行语句1：转语句(3)-(4),结果得到：5*4*3*fact(2);再调用函数fact(2):执行语句1：转语句(3)-(4),结果得到：5*4*3*2*fact(1);此时，由于fact(1)=1,即1！=0，结果得到： 5*4*3*2*1最后把上述式子累乘，得到5！=120求阶乘 n!算法复杂度分析：例2.6：假设n=4 4!=4*3!.T(

15、4)=T(3)+O(1) 3!=3*2!.T(3)=T(2)+O(1) 2!=2*1!.T(2)=T(1)+O(1) 1!=1 T(1)=O(1)因此，T(4)=O(1)+O(1)+O(1)+O(1)推广：n!=n*(n-1)! T(n)=T(n-1)+O(1) =n*(n-1)*(n-2)! =T(n-2)+O(1)+O(1) =n*(n-1)*(n-2)*1 =O(1)+O(1)+O(1) (共n项）因此，T(n)=n*O(1)=O(n).迭代法第2讲 算法分析基础归纳：递归算法复杂度分析方法之一迭代法基本思想：先将递归算法简化为对应的递归方程，然后通过反复迭代，将递归方程右端变成为一个级数，最后求级数的和，再估计和的渐近复杂度。或者，不求级数的和，直接估计级数的渐近复杂度。递归方程：利用递归算法中的关系写出递归方程，然后迭代地展开右端，变成为一个非递归的求和式子，然后对和式估计，从而对方程解进行估计。T(n)=2T(n/2)+O(n)=2(T(n/4)+O(n/2)+O(n)=2T(n/4)+O(n)+O(n)=k*O(n)=O(k*n)第2讲 算法分析基础如何提高算法质量（1）设计算法时，优先考虑算法的正确性、可靠性、稳健性、可读性；（2）其次考虑算法时空效率。 1）提高全局