时间复杂度的计算

如何计算算法时间复杂度计算算法时间复杂度过程：（1）确定基本操作（2）构造基于基本操作的函数解析式（3）求解函数解析式如果构建的是递推关系式，那么常用的求解方法有：（1）前向替换法可以从初始条件给出的序列初始项开始，使用递推方程生成序列的前面若干项，寄希望于从中找出一个能够用闭合公式表示的模式。如果找到了这样的公式，我们可以用两种方法对它进行验证：第一，将它直接代入递归方程和初始条件中。第二，用数学归纳法来证明。例如，考虑如下递推式：X(n)=2X(n-1)+1n1X(1)=1x(1)=1x(2)=2x(1)+1=2*1+1=3x(3)=2x(2)+1=2*3+1=7x(4)=2x(3)+1=2*7+1=15X(n)=2^n-1n0（2）反向替换法例如：X(n)=x(n-1)+n使用所讨论的递推关系，将x(n-1)表示为x(n-2)得函数，然后把这个结果代入原始方程，来把x(n)表示为x(n-2)的函数。重复这一过程。X(n)=x(0)+1+2+3+4+5…+n=0+1+2+3=4=n(n+1)/2（3）换名bknfnf)/()(上面形式的在递推关系式，一个规模为n的问题，每一次递归调用后，都简化为n/k规模的问题，为了方便求解，我们通常设定：n=km，则，上面的求解过程可简化为：f(n)=f(km-1)+b=f(km-2)+2b=…=f(k0)+mb=f(1)+blogn第一种递归关系式：11nn1)2/(1)(nCnC因为规模每一次递归调用后，缩减为原来的1/2，所以采用换名方法求解，设n=2k：C(n)=C(2k)=C(2k-1)+1=C(2k-2)+2=…=C(2k-k)+k=C(1)+k=logn+1第二种递归调用，每次规模是原来的1/2：1)1()2/(11)(nnnTnnT因为每一次规模都减到原来的1/2，所以用换名的方法设n=2k：T(n)=T(n/2)+(n-1)=T(2k-1)+(2k-1)=[T(2k-2)+(2k-1-1)]+(2k-1)=…=[T(2k-k)+(21-1)]+…+(2k-1-1)+(2k-1)=T(1)+[(2k+1-2)-k]=2n-logn-1算法时间复杂度：O(n)分析：1)1()2/(11)(nnnTnnT算法的复杂度有两部分决定：递归和合并，递归的复杂度是：logn，合并的复杂度是n。第三种递推关系式：)()2/(2)(1)2(nOnTnTTT(n)=2T(n/2)+n设n=2k=2T(2k-1)+2k=2[2T(2k-2)+2k-1]+2k=22T(2k-2)+2*2k=…=2k-1T(2k-(k-1))+(k-1)*2k=n/2+(logn-1)*n不失一般性，设规模为n的问题，每一次有分解为m个子问题，设n=mk，则：)()/()(1)1(nOmnmTnTTT(n)=mT(n/m)+n=mT(mk-1)+mk=m[mT(mk-2)+mk-1]+mk=m2T(mk-2)+2*mk=…=mkT(2k-k)+k*mk=n+logn*n算法时间复杂度：O(nlogn)分析：算法的复杂度有两部分决定：递归和合并，递归的复杂度是：n，合并的复杂度是nlogn。)()/()(1)1(nOmnmTnTT减治法的基本思想•将规模为n的问题递减为规模为n-1或n/2的子问题,反复递减后对子问题分别求解,再建立子问题的解与原问题的解的关系。•减治法有两个变形:减因子(如1/2):每次迭代规模减半n→n/2减可变规模:每次迭代减小的规模不同2020/4/2计算机算法设计与分析16递归复杂性的一般形式•一般的，递归复杂性可描述为递归方程：1n=1af(n~b)+D(n)n＞1f(n)=•其中，a是子问题个数，~表示递减方式，b是递减步长，D(n)是合成子问题的开销。•通常，递归元的递减方式~有两种：1、减法，即n–b，的形式。2、除法，即n/b，的形式；分治法递推法17分治策略的算法分析工具：递推方程两类递推方程)()()()()()(1ndbnafnfnginfanfkii如：汉诺塔如：快速排序递推方程的解方程d(n)为常数d(n)=cn1)(log1)()(loganOanOnTabbanObannObanOnTab)()log()()(log)()/()(ndbnaTnT影响复杂性的主要因素：子问题个数，合并开销函数。