算法分析与设计2-算法分析技术.ppt

算法分析技术,第三部分,1、算法复杂性： 它是度量算法计算难度的一种尺度，反映了算法消耗的 资源情况。 算法需要资源越多，其复杂性就越高；反之， 算法需要资源越少，其复杂性就越小。,时间复杂性（Time Complexity）： 如果问题的规模为n，解决这一问题的某算法在算法的 输入为I时所需的时间为T(n,I)，T(n，I)称为算法的时间复杂性。,3.1 算法复杂性分析,空间复杂性（Space Complexity）： 如果问题的规模为n，解决这一问题的某算法在算法的 输入为I时所需的空间为S(n,I)，S(n,I)称为算法的空间复杂性。,算法分析（Algorithm Analysis）:分析算法复杂性的过程；,算法的最好时间复杂性： Tmin(n)=Min T(n,I)=T(n,I*) IDn Dn是规模为n的合法输入的集合，I*是使算法的时间达到 最小的一个输入；,算法的复杂性除了与问题的规模有关外，在规模一定 的情况下，输入的分布也会影响算法的复杂性。从而就有 了最好、最坏、平均复杂性。,3.1 算法复杂性分析,算法的最坏时间复杂性： Tmax(n)=Max T(n,I)=T(n,I#) IDn Dn是规模为n的合法输入的集合，I#是使算法的时间达到 最大的一个输入；,算法的平均时间复杂性： Tavg(n)= P(I) T(n,I) IDn Dn是规模为n的合法输入的集合,p(I)是输入I出现的概率。,3.1 算法复杂性分析,对算法空间复杂性可以同样定义。,实践证明，可操作性最好且最有实际价值的是最坏复杂性！,注： 输入规模的概念和具体问题有关，对有些问题来说，最自然的度量标准是输入中的元素个数（例如，排序）；对另一些问题其规模的最佳度量是输入数在二进制表示下的位数（例如整数相乘）；还有的问题需要用两个数表示输入规模（例如图的顶点数和边数）。,3.1 算法复杂性分析,对于一个算法而言，在不同的执行时间内，它占用的内存空间量不一定相等，也就是说，占用空间量y是时间x的函数，即y=f(x)。,定义：时空积分= 其中t是算法的运行时间。,时空积可以综合评价算法的时间、空间性能。,例如：一个算法的执行时间为 30秒，前10秒算法占用60个字 节，第2个10秒占用70个字节， 最后10秒占用80个字节，则： 时空积如图。 60*10+70*10+80*10=2100(字节秒),2、问题的时间（空间）复杂性： 假设问题有多个算法，所有算法的集合表示为，其中A是 其中的一个算法，即A ，它的时间（空间）复杂性表示为 TA(n),问题的时间（空间）复杂性定义为：Min( TA(n) )。 A 即最优算法的时间（空间）复杂性为该问题的时间复杂性。,3.1 算法复杂性分析,3.1 算法复杂性分析,最初，我们希望精确计算出算法的复杂性（用多少时间、占多少空间）。但是，很难（可比性差），也没有必要！,精确测算出算法的性能指标是很难的，因为： （1）把两个或多个算法都写出程序代码须花费很大的时间和精力； （2）可能会因为程序写的“好”而没有体现出算法的真正质量，特别是程序员对算法有偏见时； （3）测试环境和测试数据的选择很难对各个算法公正； （4）你觉得好的算法也不一定达到要求，要重复设计算法、写代码、测试。,3.1 算法复杂性分析,但是，值得注意的是无论是操作计数还是执行步数都不能够非常准确地描述时间复杂性，特别是在需要比较时。例如: t1(n)=10n2+20n-100 t2(n)=1000n+500 哪个更好？,然后，我们又提出用评估的方法，抓主要矛盾和核心的东西，用统计基本操作或步数来估计复杂性。,于是，既然我们的目的是为了比较，就应该将注意力集中在被比较的对象之间最主要的差别。如果两个程序执行步数分别是3n+2和3n+20，则这两个程序的时间复杂性不会有太大的差别，即使这两个程序的每个执行步操作数可能有所不同，这两个程序的时间复杂性至多相差一个常数倍。,最后，就有了一个关注点， 算法性能的增长率！,3.1 算法复杂性分析,算法的增长率(growth rate)：是指当输入增长时，算法代价的增长速率。具体就体现在两个函数的变化趋势上。 T(n)=f(n) S(n)=g(n),线性增长率(linear growth rate) 二次增长率(quadratic growth rate) 指数增长率(exponential growth rate),3.1 算法复杂性分析,换更快的计算机，还是换更快的算法？,从增长率可以看出：算法不同，当计算机速度提高时，你得到 的解决问题规模的增益是不同的！,例如，当计算机的运行速度是提高为原来的10倍时，不同的算法在解决问题的规模上得到的收益是有很大不同的。,注： n是原来解决问题规模； n是现在解决问题规模,3.1 算法复杂性分析,提高计算速度对不同时间复杂性函数的影响对比,3.1 算法复杂性分析,3、复杂性的渐近估计 对算法，精确计算其增长率有时很难，如果能粗略比较出 哪个更快或更慢就可以了。于是在增长率的基础上提出渐近估 计的概念。,算法的渐近复杂性（Asymptotic Algorithm Analysis） 确切说：渐近分析是指当输入规模很大，或者说大到一 定程度时对算法的研究和分析。（从微积分意义上说是达到 极限时）。,3.1 算法复杂性分析,例如： t1(n)=10n t2(n)=2n2 n0=5时 总有： t1(n)t2(n) t1(n)=20n t2(n)=2n2 n0=10时 总有： t1(n)t2(n) 可以看出：增长率的系数对增长率的影响并不是很大。 （仅仅是改变了n0的值）,3.1 算法复杂性分析,当拥有一台更快的计算机时，它一定时间内可以完成问题的 规模增长倍数是一个定值，类似地，两个增长率不同的算法对 应的曲线总会相交，增长率的系数只是影响到相交的位置。,于是，当估算算法的性能（时间或其他代价）时，经常 忽略其增长率的系数，这样可简化算法分析，并使注意力集 中在最重要的一点，即增长率。,这样，我们在考虑增长率时就不用过多地专注于它的精确，而是专注于它的“数量级”或者“阶！,“规模”和“基本操作”都是模糊的概念！ “规模”一般是指输入量的数目。 “基本操作”完成该操作所需时间与操作数的具体 取值无关 。,最终，我们就可以在估算增长率时主要专注于问题的 “规模”和“基本的操作”。,3.1 算法复杂性分析,要注意：并不是任何情况都可以忽略常数！当解决问题的 规模n很小时，系数就会起到举足轻重的作用。,例如：t1(n)=10n t2(n)=n2 n=1: n=3: n=6:,再如：对10个数排序时使用适合于上万个数排序的算法 就不一定能够效率高。,因此，渐近分析是对算法资源开销的一种不精确的估算， 是一种“信封背面”估算，提供了对算法资源开销进行评估的 简单化模型。它有局限性。,3.2 算法复杂性分析中的渐近符号,用来表示算法的渐近时间的记号是用定义在自然数N= 0,1,2上的函数来定义的。因为T(n)一般仅定义在整数的输入规模上。,1. 记号渐近确界(上下限:lower bound and upper bound),(g(n) = f(n): 存在正常数c1,c2和n0，使对所有的nn0，有0c1.g(n) f(n) c2.g(n) 即，对于任意一个函数f(n)，若存在正常数c1,c2,使当n充分大时，f(n)能被夹在c1.g(n)和c2.g(n)中间，则f(n)属于集合(g(n) 。,因为(g(n)是一个集合，所以可以写成“ f(n) (g(n) ”。但是人们习惯写成“f(n)= (g(n)”来表示相同的意思！,3.2 算法复杂性分析中的渐近符号,由于时间和空间需求都是非负值，因此当n足够大时f(n)是非负值（渐近正函数），g(n)也必须是渐近非负的。,直观图如右：,3.2 算法复杂性分析中的渐近符号,例1：证明 n2-3n=(n2),要证明存在常数c1,c2和n0，使得对所有的nn0，有 c1n2 n2-3nc2n2 成立 用n2除以不等式得： c1 - c2 于是， c2 - 得知：c2 时对所有n 1成立 同样可知， c1 - 在 c1 时对所有n 7成立 因此，取c1= c2= n07 有 c1n2 n2-3nc2n2 成立！,3.2 算法复杂性分析中的渐近符号,反证法：假设成立，则存在常数c2和n0使得对所有的n n0有 6n3 c2n2 于是，n c2/6 由于c2是常数，所以对于任意大的n是矛盾的！ 结论得证。,例2：证明 6n3(n2),注意： （1）(g(n)中不同得函数，需要不同得常数！ （2）一个渐近正函数中得低阶项在决定渐近确界时可以被忽略，因为当n很大时它们就相对不重要了，最高阶项很小的一部分就足以超越所有的低阶项。 （3）一般可将c1取略小于最高阶项系数值，可将c2取稍大于最高阶项系数的值。,3.2 算法复杂性分析中的渐近符号,例3：证明 若 f(n)=an2+bn+c 其中a,b和c都是常数，且a0 则 f(n)=(n2),取c1=a/4, c2=7a/4 n0=2.max(|b|/a, ) 有，对于所有的nn0 ,c1.n2an2+bn+cc2.n2 成立,证明：略！,定理：如果f(n)=amnm+ + a1n + a0 且am0,则f(n)= (nm),大 比率定理：对于函数f(n)和g(n)，如果极限 和 都存在，则f(n)= (g(n)当且仅当存在正的常数c1,c2，使得 . ,3.2 算法复杂性分析中的渐近符号,例4 (1) f(n)=3n+2, g(n)=n,3n+2= (n),(2) f(n)=10n2+4n+2, g(n)=n2,f(n)=10n2+4n+2 = (n2),3.2 算法复杂性分析中的渐近符号,(3) f(n)=6*2n+n2, g(n)=2n,f(n)=6*2n+n2=(2n),3.2 算法复杂性分析中的渐近符号,2. O记号 (渐近上界:upper bound) O记号定义增长率的上界一般是指最小上界。 O(g(n) = f(n): 存在正常数c和n0，使对所有的nn0，有 0f(n) c.g(n) 即，对于任意一个函数f(n)，若存在正常数c，使当n充分大时，f(n)的值总在c.g(n)之下，则f(n)属于集合O (g(n) 。,为了表示一个函数f(n)是集合O(g(n)的一个元素，记： f(n)=O(g(n),直观图如右：,3.2 算法复杂性分析中的渐近符号,注意：,（1）根据集合知识，有(g(n)O(g(n),（2）an+b=O(n2) 是上界，但不是最小上界。,（3）有些文献用O来非正式地描述渐近确界。现在文献中都将渐近确界和渐近上界区分开来。,（4）不要产生错误界限。 例如：n2+100n+6，当nc-100就有n2+100n+6cn。,3.2 算法复杂性分析中的渐近符号,（5）用来作比较的函数g(n)应该尽量接近所考虑的函数f(n). 例如：3n+2=O(n2) 是松散的界限；3n+2=O(n) 是较好的界限。同理，3n2+42n=O(n2)是错误的界限。,（6） f(n)=O(g(n)不能写成g(n)=O(f(n)，因为两者并不等价。 前面提到，这里的等号并不是通常相等的含义。按照定义，用集合符号更准确些。,3.2 算法复杂性分析中的渐近符号,大O比率定理：对于函数f(n)和g(n)，如果极限 存在，则f(n)=O(g(n)当且仅当存在正的常数c，使得 .,证明：略！,例如：因为 ， 所以 ； 因为 ，所以 ； 因为 ，所以 ；,3.2 算法复杂性分析中的渐近符号,因为 ，所以 ； 但是这不是一个好的上界估计，问题出在极限值不 是正的常数。,因为 ，所以 3n2+5O(n),O记号用来表示上界，它表示对任意的输入，算法的最坏情况情况运行时间的上界。即最坏时间复杂性。,3.2 算法复杂性分析中的渐近符号,定理：如果f(n)=amnm+ + a1n + a0 且am0,则f(n)=O(nm),证明：略！,下述不等式对于复杂性阶的评估非常有帮助： 定理： 对于任意一个正实数x0和任一个实数0,下面的结论 都正确。 (1) 存在某个n0使得对于任何nn0 ，有 。 (2) 存在某个n0使得对于任何nn0 ，有 。 (3) 存在某个n0使得对于任何nn0 ，有 。 (4) 存在某个n0使得对于任何nn0 ，有 nxnx+ 。 (5) 对任意实数 y,存在某个n0使得对于任何nn0 ，有 nx(logn)ynx+ ,3.2 算法复杂性分析中的渐近符号,例如 根据上面定理，我们很容易得出：,(logn)xn,(logn)xn,(logn)xn,3. 记号（渐近下界：lower bound) 记号定义增长率的下界一般是指最大下界 (g(n) = f(n): 存在正常数c和n0，使对所有的nn0，有 0 c.g(n) f(n) 即，对于任意一个函数f(n)，若存在正常数c，使当n充分大时，f(n)的值等于或大于c.g(n)，则f(n)属于集合(g(n) 。,3.2 算法复杂性分析中的渐近符号,直观表示如右图：,例如,大 比率定理：对于函数f(n)和g(n)，如果极限 存在，则f(n)= (g(n) 当且仅当存在正的常数c，使得,证明：略！,3.2 算法复杂性分析中的渐近符号,n/(3n+2)=1/3 所以 3n+2=(n),n2/(10n2+4n+2)=0.1 所以 10n2+4n+2 =(n2),2n/(6*2n+n2)=1/6 所以 6*2n+n2 =(2n),n/(6n2+2)=0 所以 6*n2+2 =(n),n3/(3n2+5)= 所以 3n2+5 (n),定理：如果f(n)=amnm+ + a1n + a0 且am0,则f(n)= (nm),证明：略！,3.2 算法复杂性分析中的渐近符号,记号用来表示渐近下界，它表示对任意的输入，算法的最好情况情况运行时间的下界。即最好时间复杂性。,注意：由这三个符号的定义可以看出，尽管由渐近确界可以导出渐近上界和渐近下界，但是在实际应用中是用渐近上界和渐近下界证明（导出）出渐近确界。,另外：一般情况下，我们不可能对每个复杂性函数去估计它们的渐近上界、渐近下界和渐近确界。,4. 记号 O记号所提供的渐近上界可能是也可能不是渐近紧确的。 例如，2n2=O(n2)是渐进紧确的， 2n=O(n2)就不是渐近紧确的。 使用符号来表示非渐近紧确的上界。即： f(n)= (g(n)=对任意正常数c，存在常数n00，使得所有的nn0，有0f(n)c.g(n) ,3.2 算法复杂性分析中的渐近符号,O和定义类似。主要区别是： f(n)=O(g(n)，界0f(n)c.g(n) 对某个常数c0成立； f(n)= (g(n)，界0f(n)c.g(n) 对所有常数c0成立；,也就是说：在表示中，当n时，函数f(n)相对于g(n)来说就不重要了。即,5. 记号 记号与记号的关系就象记号和O记号的关系一样。 f(n)= (g(n)=f(n):对任意正常数c0，存在常数n00，使得所有的nn0，有0 c.g(n) f(n) ,3.2 算法复杂性分析中的渐近符号,和定义类似。主要区别是： f(n)=(g(n)，界0 c.g(n) 0成立； f(n)=(g(n)，界0 c.g(n) 0成立；,也就是说：在表示中，当n时，函数g(n)相对于f(n)来说就不重要了。即,一些常见的求和函数式的渐近表示：,3.2 算法复杂性分析中的渐近符号,其中， 符号代表 中的任意一个 。,3.2 算法复杂性分析中的渐近符号,实数的许多关系属性也一样适合渐近比较：,3.2 算法复杂性分析中的渐近符号,（1）传递性：,f(n)=(g(n)和g(n)= (h(n) 则f(n)= (h(n) f(n)=(g(n)和g(n)= (h(n) 则f(n)= (h(n) f(n)=(g(n)和g(n)= (h(n) 则f(n)= (h(n) f(n)=(g(n)和g(n)= (h(n) 则f(n)= (h(n) f(n)=(g(n)和g(n)= (h(n) 则f(n)= (h(n),（2）自反性：,f(n)=(f(n) f(n)=(f(n) f(n)=(f(n),实数的许多关系属性也一样适合渐近比较：,3.2 算法复杂性分析中的渐近符号,（3）对称性：,f(n)=(g(n) 当且仅当 g(n)= (f(n),（4）转置对称性：,f(n)= (g(n) 当且仅当 g(n)=(f(n) f(n)=(f(n) 当且仅当 g(n)=(f(n),为了好理解，可以将两个函数f和g的渐近比较与两个实数的比较类比来看：,3.2 算法复杂性分析中的渐近符号,f(n)= (g(n) 类似于 a b f(n)= (g(n) 类似于 a b f(n)= (g(n) 类似于 a = b f(n)= (g(n) 类似于 a b,注意：实数集上的“三分性”不适合渐近记号,对于两个实数a和b，下列三种情况恰有一种成立： ab (这个性质称为“三分性”) 但是，并不是所有函数都是渐近可比较的。即，对两个函数f(n)和g(n)，可能f(n)= (g(n)和f(n)= (g(n)都不成立，当然f(n)= (g(n)也不成立。例如： f(n)=n , g(n)=n1+sinn,3.2 算法复杂性分析中的渐近符号,有时算法需要由多个函数经过加、乘运算组合起来的复杂函数来表示其复杂性。对复杂函数的渐近表示有下列规则：,I1 I2 I3 I4 I5 I6,3.2 算法复杂性分析中的渐近符号,加法规则 针对并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m),乘法规则 针对嵌套程序段 T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m),3.2 算法复杂性分析中的渐近符号,void exam ( float x , int m, int n ) float sum ; for ( int i = 0; i m; i+ ) sumi = 0.0; for ( int j = 0; j n; j+ ) sumi += xij; for ( i = 0; i m; i+ ) cout i “ : ” sum i endl; ,两个并列循环的例子,渐进时间复杂度为 O(max (m*n, m),3.2 算法复杂性分析中的渐近符号,template void dataList : Sort ( ) int i = 1; int exchange = 1; while ( i ArraySize ,两个嵌套循环的例子,3.2 算法复杂性分析中的渐近符号,template void dataList: BExchange(int i, int ,3.2 算法复杂性分析中的渐近符号,渐进时间复杂度 O(f (n)*g (n) = O(n2),Sort n-1趟,BExchange ( ) n-i次比较,关于渐近表示一些有用的补充说明：,1 方程式中的渐近符号 当渐近符号只出现在等式的右边，例如 n=O(n2)，等号即表示集合的成员关系，即 n O(n2)。,但是，当渐近符号出现在一个公式中时，我们将其解释为某些匿名函数。例如 ，2n2+3n+1=2n2+(n)意即2n2+3n+1=2n2+f(n)，其中f(n) 是属于某个集合(n)的函数。此处f(n)=3n+1确实在(n)中。,渐近表示的这种用法可以略去方程式中无关紧要的细节，例如，T(n)=2T(n/2)+ (n)。 如果我们对T(n)的渐近行为感兴趣，就没有必要写出低阶的项，它们都包含在由(n)表示的函数中。,3.2 算法复杂性分析中的渐近符号,有时渐近符号出现在等式的左边，例如 2n2 (n) (n2) 这时根据以下规则来解释方程：无论等号左边的匿名函数如阿选择，总有办法选取等号右面的匿名函数使等式成立。 针对例子，我们知道，对任意函数f(n) (n) ,存在函数g(n) (n2) ,使对所有的n，2n2+f(n)= g(n) ,换言之，方程右边提供了较左边更少的细节。,一组这样的关系可以链起来，例如: 2n2+3n+1=2n2+ (n) = (n2) 于是，我们可以这么来解释：第一个方程式说明存在函数f(n) (n) 使对所有n有2n2+3n+1=2n2+ f(n) 。第二个方程说明对任意函数g(n) (n) ,存在函数h(n) (n2) ,对所有n有2n2+g(n)=h(n) ,这也就意味着2n2+3n+1= (n2) 。,3.2 算法复杂性分析中的渐近符号,2一些标准记号和通用函数,（1）上取整(Floors)下取整(Ceilings) 对于任意实数x，小于或等于x的最大整数表示为x ，大于或等于x的最小整数表示为 x 。对于所有实数x， x-10， n/a/b = n/ab n/a/b = n/ab a/b (a+(b-1)/b a/b (a-(b-1)/b 下取整函数f(x)= x是单调递增的， 上取整函数f(x)= x 也是单调递增的。,3.2 算法复杂性分析中的渐近符号,（2）取模运算 (Modular arithmetic) 对于任意整数a和任意正整数n，a mod n的值即是a/n的余数： a mod n = a- a/n n,同余：如果(a mod n) = (b mod n)，称在模n时，a等于b，即a和b被n除时余数相同。记作 ab(mod n) ab(mod n)当且仅当n是b-a的一个约数。,3.2 算法复杂性分析中的渐近符号,（3）多项式 给定一个正整数，的次多项式是具有如下形式的函数p(n)： d p(n)=aini i=0 其中常数a0,a1,ad是多项式的系数，且ad0。,一个多项式是渐近正的，当且仅当ad0。 对于一个d次的渐近正多项式p(n)，有p(n)= (nd)。 对于任意实常数a0，函数na单调递增； 对于任意实常数a0， 函数na单调递减； 对某个常数k有f(n)=O(nk)，则称函数f(n)有多项式界；,3.2 算法复杂性分析中的渐近符号,（4）指数式 对于任意实数a0，m和n，有下列恒等式： a0=1 ，a1=a ， a-1=1/a (am)n=amn， (am)n=(an)m， aman=am+n,3.2 算法复杂性分析中的渐近符号,对任意n和a1，函数an关于n单调递增； 对任意实数a和b，且a1，有： =0 因此，根据前面的定义可知 nbo(an) 即 任何底大于1的指数函数比任何多项式函数增长的更快！,用e表示2.71828，即自然对数函数的底，对任意实数x x2 x3 xi ex =1+x+ + + = 2! 3! i=0 i!,对任意实数x，有不等式： ex 1+x 只有x=0时等号才成立； 当 |x|1时，有近似式： 1+xex1+x+x2 当x0时，用1+x来近似ex的效果相当好： ex=1+x+ (x2) 对任意的x，有： x lim ( 1+ )n =ex n n,3.2 算法复杂性分析中的渐近符号,（5）对数 一般约定： lgn=log2n lnn=logen lgkn=(lgn)k lglgn=lg(lgn) lgn+k=(lgn)+k,3.2 算法复杂性分析中的渐近符号,函数来logbn在常数b大于1时，关于n0严格递增。,改变一个对数的底只是把对数的值改变了一个常数倍，所以当不在意这些常数因子时常采用“lgn”记号，就象O记号一样。一般认为对数的底取2最为自然，因为很多算法和数据结构都涉及到对问题的二分。,当|x|-1时，还有以下不等式成立： x ln(1+x) x 只有x=0时等号才成立 1+x,3.2 算法复杂性分析中的渐近符号,如果对常数k，函数f(n)=O(lgkn) ，则称f(n)是多项对数有界的。 由前面我们已知： nb lim 0 n an 于是用lg n 代替n ，用2a代替a，于是可以将多项式增长率和多项对数增长率联系起来： lgbn lgbn lim lim =0 n (2a)lgn n na 因此对于任意常数a0，有： lgbno(na) 即任意正的多项式函数都比多项对数函数增长得快！,3.2 算法复杂性分析中的渐近符号,（6）阶乘 阶乘函数的一个弱上界是 n! nn 。,斯特林近似公式： n 1 n!= ()n (1+ () e n 给出了一个更紧确的上界和下界。其中e是自然对数的底。 有用结论： n!=o(nn) n!=(2n) lg(n!)= (nlgn),3.2 算法复杂性分析中的渐近符号,3.2 算法复杂性分析中的渐近符号,1、算法分析的一般步骤： （1）计算基本操作、基本存储占用的数量； （2）求出累计和函数T(n),S(n)； （3）给出渐近表示。,3.3 算法复杂性分析的内涵,2、算法复杂性的实质： 问题规模变化与资源消耗的关系！,渐进复杂性分析的重要性 很多人认为：随着计算机技术的发展，低效算法无所谓了！ 其实不然，“坏”算法终究是“坏”算法，不因为计算机速度的 提高它就成了“好”算法！,对低效算法（一般是超线性的）来说，计算机本身性能的提高不能带来求解问题规模的增益。即：计算机速度提高了，我们希望在原来的时间内解决问题的规模变大，或希望解决原来相同规模的问题时时间相应的变短，但结果可能不是你想象的那样好，这与你使用的算法有关！,3.3 算法复杂性分析的内涵,注意： （1）“复杂性渐进阶比较低的算法比复杂性的渐进阶比较高的算法有效”，只是在问题规模充分大时才成立。 （2） 当两个算法的复杂性渐进阶相同时，必须进一步考察T（n）的常数因子,3.4 一般算法的时间复杂性分析,1、赋值、读、写等一般看作基本操作； 2、划分三种控制结构； 3、对各种控制结构，有 （1）顺序操作序列，可以累加或取最大值； （2）分支的条件判断一般看作基本操作，分支结构的时间 定义为条件成立和不成立时的和； （3）循环结构的时间为循环体的时间乘循环次数； 4、函数调用时要考虑函数的执行时间。 给出基本操作的计数(或步数统计) 渐近表示：最好给出,各个符号的表示!,3.5 递归算法的复杂性分析,递归算法是比较特殊的一类算法，其分析过程一般有下面几步： 1、分析递归算法，写出递归方程 2、求解递归方程； 3、给出递归方程解的渐近表示； 其中，求解递归方程式是关键，也是比较难的一步！,3.5 递归算法的复杂性分析,递归方程的求解,当一个算法包含对自身的递归调用时，其运行时间通常用 递归式来表示。递归式是一组等式或不等式，它所描述的函数 是用在更小的输入下该函数的值来定义的。,例如，数据结构中介绍的“归并”分类算法的最坏运行时间 可以用下面的递归式来描述： (1) n=1 T(n)= 2T(n/2)+ (n) n1 其解为T(n)= (nlgn) 求解递归方程，是数学里的一类问题，有些是比较难的， 我们介绍三种在算法分析中常用的方法。,3.5 递归算法的复杂性分析,一代换法,“代换法”这一名称源于当归纳假设用较小值时，用所猜测 的值代替函数的解。它可用来确定一个递归式的上界或下界。 这种方法很有效，但是只能用于解的形式很容易猜的情形。,1用代换法解递归式需要两个步骤： 1）猜测解的形式 2）用数学归纳法找出使解真正有效的常数,例如，有下面的递归式： T(n)=2T( n/2 )+n，我们可以用代换法来确定它的一个上界。,首先，从前面的一些结论我们可以猜测，T(n) cnlgn，其中c0是某个常数。,3.5 递归算法的复杂性分析,一代换法,然后，用归纳法来确定常数c。先假设这个界对 n/2 成立，即 T(n/2 ) c n/2 lg( n/2 )，代入原式，于是有： T(n)=2T( n/2 )+n 2 (c n/2 lg( n/2 )+n cnlg(n/2)+n =cnlgn cnlg2+n =cnlgn-cn+n cnlgn (只要c1) 可以归纳证明，c 2时，对于n 2 都成立（根据渐近表示要求，n0可以把不符合的边界区分开来） 于是有T(n) cnlgn，结论获证！,3.5 递归算法的复杂性分析,一代换法,2需要注意的问题,1）做一个好的猜测 不存在通用的方法来猜测递归式正确的解，需要经验和创新。但是有些探试法可以帮助做出好的猜测。 如果某个递归式与以前见过的类似，则可以猜测该递归式有类似的解。例如，对 T(n)=2T( n/2 +17)+n 我们可以猜测其解为 T(n)=O(nlgn)。 另一方法是，先证明递归式的轻松的上下界，然后再缩小不确定性区间。,3.5 递归算法的复杂性分析,一代换法,2需要注意的问题,2）一些细微问题 有时，我们或许能够猜出递归式的渐近界，但却会在归纳证明时出现问题。通常，问题出在归纳假设不够强，无法证明其准确的界。遇到这种情况时，可以去掉一个低阶项来修正所猜的界，以使证明顺利进行。,例如有下面的递归式： T(n)=T( n/2 )+T( n/2 )+1 根据经验我们猜测：T(n)=O(n)，即要证明对适当选择的c，有 T(n) cn。,3.5 递归算法的复杂性分析,一代换法,用所猜测的界对递归式做替换，于是得到： T(n)= T( n/2 )+T( n/2 )+1 c n/2 + c n/2 +1 = c (n/2 + c n/2 )+1 = cn+1 由此看出，无论c为何值，都得不出 T(n) cn的结论。,于是，人们或许就猜测一个更大的界，例如T(n)=O(n2)，这的确是它的一个上界，但它不是最小的上界。而事实上，我们猜的很正确。为了归纳证明，我们需要做一个更强的归纳假设。从直观上看，我们猜的与上面归纳推的结论只差一个常数“1”，即一个看似无关的低阶项，但是就是这个低阶项却使得数学归纳法无法证明出期望的结果。,3.5 递归算法的复杂性分析,一代换法,现在，我们用降阶来修正猜测的界，即从所作的猜测中减去一个低阶的项，即有 T(n) cn-b，b0是常数。然后我们再去归纳证明。,将假设代入，有： T(n)= T( n/2 )+T( n/2 )+1 (c n/2 -b + c n/2 -b)+1 = cn-2b+1 cn-b (只要b1) 同时c要取得足够大，以便能够处理边界条件。,好象我们感觉从猜测中减去一项与直觉不符合，为什么不增加一项来解决问题呢？这关键是由数学归纳法本身决定的：通过更小的值做更强的假设，就可以证明对某个给定值的更强的结论。,3.5 递归算法的复杂性分析,一代换法,2需要注意的问题,3）避免陷阱 在运用渐近符号时很容易出错，记住：我们要归纳证明的是准确的形式。例如：由假设T(n) cn , 然后： T(n)=2T( n/2 )+n 2(c n/2 )+n cn+n =O(n) 这个结论是错误的，因为我们希望推出的是准确的形式：T(n) cn,3.5 递归算法的复杂性分析,一代换法,2需要注意的问题,4）改变变量 有时，对于一个陌生，看似复杂的递归式做一些简单的变换，就会变成我们较为熟悉的形式，从而可以根据经验做出好的猜测。,例如，有递归式 T(n)=2T( )+lgn，我们可以按下面的方法进行变换： 1）不考虑整数截取 2）设m=lgn, 于是 n=2m ， =2m/2 于是有： T(2m)=2T(2m/2)+m 再假设 S(m)=T(2m)，于是就有：S(m)=2S(m/2)+m 根据前面的猜测我们知道，S(m)=O(mlgm)。再将S(m)代回去得：T(n)=T(2m)=S(m)=O(mlgm)=O(lgn lglgn),3.5 递归算法的复杂性分析,二递归树法,虽然代换法给递归式的解的正确性提供了一种简单的证明方法，但是有时候很难得到一个好的猜测。而画出递归树是一种得到好的猜测的直接方法。,递归树的构造方法是：首先将递归式转化为一棵等价树，该树的树根结点是顶层递归的代价，根的子树是根据递归式推出的更小的递归式。即首先T(n)扩展为一棵等价的树，然后再依次下去，继续扩展递归式的各个结点，即将其分解成由递归式所决定的各个组成部分，直到问题规模降到了最小。,在递归树中，每个结点都代表递归函数调用集合中一个子问题的代价。将树中每一层的代价相加得到一个每层代价的集合，再将每层的代价相加得到递归式所有层次的总代价。,3.5 递归算法的复杂性分析,二递归树法,例如，对于递归式 T(n)2T(n/2)+cn，递归树构造为：,T(n),cn,T(n/2),T(n/2),cn,cn/2,cn/2,T(n/4),T(n/4),T(n/4),T(n/4),3.5 递归算法的复杂性分析,cn,cn/2,cn/2,cn/4,cn/4,cn/4,cn/4,c c c c c c c c c c c c c c c,n,lgn,cn,cn,cn,cn,3.5 递归算法的复杂性分析,二递归树法,递归树最适合来产生好的猜测，然后用代换法加以验证。但是，在用递归树产生好的猜测时，由于后面还要对猜测进行归纳证明，所以产生递归树时可以是一个大致的粗略的，即不一定是非常严格的全部生成出来。,如果生成递归树时非常仔细完整，并且将代价都加了起来，那么就可以直接用递归树来作为递归式解的证明，这也就是我们经常用的展开法求解递归式的解。,请你自己试着画出递归式 T(n)=3T(n/4)+cn2 的递归树，并猜测其解。,3.5 递归算法的复杂性分析,三主方法,主方法(master method)给出求解如下形式的递归式的“食谱”方法。 T(n)=aT(n/b)+f(n) 其中 a1和b1是常数，f(n)是一个渐近正的函数。,主方法要求只要记忆三种情况，就可以很容易地确定一些递归式的解，而且不用纸和笔！,上面的递归式描述了将规模为n的问题划分为a个子问题的算法的运行时间，每个子问题的规模为n/b，a和b是正常数，a个问题被递归地解决，其花时间为T(n/b)。划分原问题与合并答案的代价用函数f(n)来描述。,3.5 递归算法的复杂性分析,三主方法,3.5 递归算法的复杂性分析,三主方法,主定理的应用：,再例如： ，这里 ， ， 由于 ， =(1) 所以由公式()有 。,3.6 复杂性分析举例,Insertion_sort(A) for j2 to length(A) do key Aj /将Aj插入到有序序列A1j-1 i j-1 while(i0)and(Aikey) do Ai+1 Ai i i-1 Ai+1 key ,例1：分析下面插入分类的时间复杂性,假设tj为对每个j值时while循环的运行次数，于是有各个代码行的 执行次数如上。又假设n=length(A),Cost times c1 n c2 n-1 c3=0 n-1 c4 n-1 c5 tj c6 (tj-1) c7 (tj-1) c8 n-1,于是， T(n)=c1n+c2(n-1)+c4(n-1)+c5tj+c6 (tj-1)+c7(tj-1)+c8(n-1),3.6 复杂性分析举例,另外，在输入规模一定时，不同的输入样本实例会影响算法的运行时间。 例如，当输入序列已经排好序时，对于每一个j，都有tj=1， ，出现最好情况，于是有: T(n)=c1n+c2(n-1)+c4(n-1)+c5(n-1)+c8(n-1