第4讲算法效率

第4讲算法效率1内容提要什么是算法算法的设计目标算法分析——时间复杂度算法的空间复杂度21.算法•算法的定义和算法的表示方法算法是描述求解问题方法的操作步骤集合。算法要用某种语言来描述。常用的算法描述方法：•自然语言•程序设计语言•类程序设计语言•流程图•算法的性质输入性：具有零个或若干个输入量；输出性：至少产生一个输出或执行一个有意义操作；有限性：执行语句的序列是有限的；确定性：每一条语句的含义明确，无二义性；可执行性：每一条语句都应在有限的时间内完成。2.算法设计目标算法设计应满足以下五条目标：正确性可读性健壮性高时间效率高空间效率3.算法分析对于一个问题，一旦某种算法给定并且是正确的，那么最重要的就是确定该算法将需要多少诸如时间或空间等资源的问题。估计算法资源消耗所需的分析是一个理论问题，需要一套系统架构。数学基础定义1如果存在正常数c和n0使得当N≥n0时T(N)≤cf(N)，则记为T(N)=O(f(N))定义2如果存在正常数c和n0使得当N≥n0时T(N)≥cg(N)，则记为T(N)=Ω(g(N))定义3T(N)=Θ(h(N))当且仅当T(N)=O(h(N))和T(N)=Ω(h(N))定义4如果对每一正常数c都存在常数n0使得当Nn0时T(N)cp(N)，则T(N)=o(p(N))数学基础这些定义的目的是要在函数间建立一种相对的基本，比较的是它们的相对增长率例如：1000N=O(N2)——大O标记法当T(N)=O(f(N))时，函数T(N)是在以不快于f(N)的速度增长，因此f(N)是T(N)的一个上界f(N)=Ω(T(N))，T(N)是f(N)的一个下界数学基础法则1：如果T1(N)=O(f(N))且T2(N)=O(g(N))，那么(a)T1(N)+T2(N)=O(f(N)+g(N))（可写成max(O(f(N)),O(g(N)))）(b)T1(N)*T2(N)=O(f(N)*g(N))法则2：如果T(N)是一个k次多项式，则T(N)=Θ(Nk)法则3：对任意常数k，logkN=O(N)函数名称c常数logN对数log2N对数平方的N线性的NlogNN2二次的N3三次的2N指数的数学基础将常数或低阶项放进大O是坏习惯通过极限来确定两个函数f(N)和g(N)的增长率，必要的时候可以使用洛比达法则。该极限可以有四种可能的值：•极限是0：f(N)=o(g(N))•极限是c≠0：f(N)=Θ(g(N))•极限是∞：g(N)=o(f(N))•极限摆动：二者无关)(/)(limNgNfN要分析的问题要分析的最重要的资源就是运行时间和算法执行时间相关的因素：1．算法选用的策略2．问题的规模3．编写程序的语言4．编译程序产生的机器代码的质量5．计算机执行指令的速度一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。定义两个函数Tavg(N)和Tworst(N)，分别为算法对于输入量N所花费的平均运行时间和最坏情况的运行时间一般情况下，计算的是最坏情况的运行时间T(n)为算法的(渐近)时间复杂度如何估算算法的时间复杂度？从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数（频度）作为算法运行时间的衡量准则.因为:算法=控制结构+原操作（固有数据类型的操作）算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间算法的执行时间与原操作执行次数之和成正比一个简单的例子publicstaticintsum(intn){intpartialSum;partialSum=0;for(inti=1;i=n;i++)partialSum+=i*i*i;returnpartialSum;}不计时间114N1、N+1、N估算算法的时间复杂度的方法:1.多数情况下,求最深层循环内的简单语句(原操作)的重复执行的次数.2.当难以精确计算原操作的执行次数时,只需求出它关于n的增长率或阶即可.3.当循环次数未知(与输入数据有关),求最坏情况下的简单语句(原操作)的重复执行的次数.例1:for(i=1;i=n;++i)for(j=1;j=n;++j){c[i][j]=0;for(k=1;k=n;++k)c[i][j]+=a[i][k]*b[k][j];}基本操作:乘法操作时间复杂度:O(n3)计算算法的时间复杂度的例题:例2:voidselect_sort(inta[]){intn=a.length,temp;for(i=0;in-1;++i){j=i;for(k=i+1;kn;++k)if(a[k]a[j])j=k;if(j!=i){temp=a[i];a[i]=a[j];a[j]=temp;}}//select_sort基本操作:比较(数据元素)操作时间复杂度:O(n2)计算算法的时间复杂度的例题:例3:voidbubble_sort(inta[]){intn=a.length,temp;booleanchange;for(i=n-1,change=true;i1&&change;--i){change=false;for(j=0;ji;++j)if(a[j]a[j+1]){temp=a[j];a[j]=a[j+1];a[j+1]=temp;change=TRUE；}}}//bubble_sort基本操作:赋值操作时间复杂度:O(n2)计算算法的时间复杂度的例题:例4：{++x;s=0;}基本操作：时间复杂度为：++x或s=0Ｏ(1)即常量阶计算算法的时间复杂度的例题:计算算法的时间复杂度的例题:if(list.contains(e)){System.out.println(e);}elsefor(Objectt:list){System.out.println(t);}22T(n)=testtime+worst-case(if,else)=O(n)+O(n)=O(n)TimeComplexityLetnbelist.size().Executedntimes.O(n)例5：其关系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间的关系为：O(2n)O(n!)O(nn)常用计算算法时间的多项式分析二分查找算法算法中的每次迭代都包含一个常数操作，记做c.假设n是2的幂，k=logn.经过一次比较，二分查找排除了一半的输入24ncncTcknTccnTcnTnTklog1log)1()2(...)2()2()(2)(lognOkn2分析汉诺塔问题c表示移动一个盘子的常量时间，也就是说T(1)=c.则25)2()12(2...222...2)1(2)))2((2(2)1(2)1()1()(2121nnnnnnOccccccccTccnTcnTnTcnTnT实例分析:Fibonacci数/**ThemethodforfindingtheFibonaccinumber*/publicstaticlongfib(longindex){if(index==0)//Basecasereturn0;elseif(index==1)//Basecasereturn1;else//Reductionandrecursivecallsreturnfib(index-1)+fib(index-2);}26Finonacciseries:01123581321345589…indices:01234567891011fib(0)=0;fib(1)=1;fib(index)=fib(index-1)+fib(index-2);index=2递归的斐波那契数的时间复杂度Since27and)2(nO)2()12...2(2)12()1(2)12...2()1(22...2)1(2...2)2(2))2(2(2)1(2)2()1()(211121212nnnnnnnnnOcccTcTcccTccnTccnTcnTcnTnTnT)2(222...22222...2)1(2222)222(222)22(22)2)4(2(22)2(2)2()3()2()2()1()(232/2/232/2/23322nnnnnOcccccccccTcccnTccnTccnTcnTcnTcnTnTcnTnTnT实例:非递归斐波那契数列publicstaticlongfib(longn){longf0=0;//Forfib(0)longf1=1;//Forfib(1)longf2=1;//Forfib(2)if(n==0)returnf0;elseif(n==1)returnf1;elseif(n==2)returnf2;for(inti=3;i=n;i++){f0=f1;f1=f2;f2=f0+f1;}returnf2;}28这个算法的时间复杂度为)n(O29f0f1f2Fibonacciseries:01123581321345589…indices:01234567891011f0f1f2Fibonacciseries:01123581321345589…indices:01234567891011f0f1f2Fibonacciseries:01123581321345589…indices:01234567891011f0f1f2Fibonacciseries:01123581321345589…indices:01234567891011实例：找素数比较以下四种算法:30穷举法检测到Math.sqrt(n)检测到Math.sqrt(n)的素数筛选法PrimeNumberRunEfficientPrimeNumbersSieveOfEratosthemesPrimeNumbers实例:最近的点对31midd2d1ddstripLstripRS1S2ddstripLstripRpdstripLstripRpq[r])log()()2/(2)(nnOnOnTnT实际考虑虽然时间复杂度的分析是一种很好的理论估计算法效率的方式，但是两个算法具有意义的时间复杂度不代表效率相同。324.算法的空间复杂度分析算法的空间复杂度分析主要是分析算法在运行时所需要的内存空间的数量级。算法的空间复杂度通常也采用O()函数。算法的空间复杂度分析方法和算法的时间复杂度分析方法类同。