算法设计与分析 课件 第一章 绪论1.4.2 渐近时间复杂度分析

计算机算法设计与分析第一章概述渐近时间复杂度分析设T(N)是算法A的时间复杂度函数，N是问题规模，N≥0，且N∈Z。当N

∞时，T(N)

∞。对于T(N)，如果存在T'(N)，使得当N

∞时有那么，我们就说T'(N)是算法A当N

∞的渐近复杂度。渐近时间复杂度分析在渐近复杂度函数T'(N)中，阶与T'(N)中的常数因子没有关系，所以T'(N)可进一步简化，省略常数因子。例1.4中的T'(N)可取值N2即可。需要注意的是，函数简化并不是一种精确计算复杂度的方法，而是一种近似评估的方式。例1.4中的T'(N)=N2/2+5N/2-3渐近时间复杂度分析定义1.1设f(N)和g(N)是正整数集上的函数。如果∃c≥0和自然数N0，使得当N≥N0时有0≤f(N)≤cg(N)，则称函数f(N)充分大时上有界，g(N)是f(N)的一个上界，记为f(N)=O(g(N))，即f(N)的阶不高于g(N)的阶，如图所示。不是直接比较f(N)和g(N)的数值大小，O表示的只是一个充分大的上界，上界的阶越低则算法时间复杂度的评估越精确，结果值越有价值N0cg(N)f(N)渐近时间复杂度分析例1.5求5n+4，n2+nlogn，2n+n2，10000的上界。n≥4时，5n+4≤6n，则5n+4=O(n)n≥1时，n2+nlogn≤2n2，则n2+nlogn=O(n2)n≥1时，2n+n2≤2*2n，则2n+n2=O(2n)对于常整数10000，算法执行时间与问题规模无关，无论问题规模多大，算法都在固定时间内完成。因此无论是10000还是其他任何常数输入，它的时间复杂度是一个常数级别的复杂度，即O(1)。渐近时间复杂度分析例1.6给定多项式函数：

试证明T(n)=O(nm)。证明：设n0=1,对于任意的n，若n≥n0=1，则：存在c≥0和自然数n0=1，使得当n≥n0时有T(n)≤cnm，故T(n)=O(nm)成立。渐近时间复杂度分析根据定义1.1，我们有如下O(n)的性质：（1）O(f)+O(g)=O(max(f,g))；算法最复杂的部分运行时间就是算法的时间复杂度。（2）O(f)+O(g)=O(f+g)；算法中并行语句的时间复杂度等于各个语句运行时间之和。（3）O(f)×O(g)=O(f×g)；循环的时间复杂度等于循环体运行时间与循环次数的乘积。（4）O(cf(n))=O(f(n))，c∈Z+；算法的时间复杂度是运行时间函数的数量级。（5）如果g(n)=O(f(n))，则O(f)+O(g)=O(f)；算法的时间复杂度是运行时间函数的最高阶。（6）f=O(f)。渐近时间复杂度分析定义1.2设f(N)和g(N)是正整数集上的函数。如果∃c≥0和自然数N0，使得当N≥N0时有f(N)≥cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是f(N)的一个下界，记为f(N)=Ω(g(N))，即f(N)的阶不低于g(N)的阶，如图所示。N0cg(N)f(N)渐近时间复杂度分析例1.8求5n+1，n2+nlogn的下界。当n≥1时，5n+1≥5n，则5n+1=Ω(n)当n≥1时，n2+nlogn≥n2，则n2+nlogn

=Ω(n2)；n2+nlogn≥nlogn，则n2+nlogn=Ω(nlogn)，但nlogn≠Ω(n2)。根据定义1.2可知，n2+nlogn=Ω(n2)和n2+nlogn

=Ω(nlogn)都成立，算法时间复杂度一般取最大下界。下界的阶越高，评估越精确，结果越有价值，Ω通常也表示求解问题的最好情况下的时间复杂度。渐近时间复杂度分析定义1.3设f(N)和g(N)是正整数集上的函数。如果∃c1≥0、∃c2≥0和自然数N0，使得当N≥N0时有0≤c1g(N)≤f(N)≤c2g(N)，则称g(N)是f(N)的紧确界。记为f(N)=θ(g(N))，如图1.7所示。若f(N)=θ(g(N))，则当且仅当f(n)=O(g(N))且f(N)=Ω(g(N))，也称g(N)和f(N)同阶。N0c1g(N)f(N)c2g(N)渐近时间