时间复杂度的计算

1、如何计算算法时间复杂度1 计算算法时间复杂度过程：（1）确定基本操作（2）构造基于基本操作的函数解析式（3）求解函数解析式2 如果构建的是递推关系式，那么常用的求解方法有：（1）前向替换法 可以从初始条件给出的序列初始项开始，使用递推方程生成序列的前面若干项，寄希望于从中找出一个能够用闭合公式表示的模式。如果找到了这样的公式，我们可以用两种方法对它进行验证：第一，将它直接代入递归方程和初始条件中。第二，用数学归纳法来证明。3例如，考虑如下递推式： X(n) = 2X(n-1) +1 n1 X(1) = 1x(1)=1x(2)=2x(1)+1 = 2*1+1=3x(3)=2x(2)+1=2*3+

2、1=7x(4)=2x(3)+1=2*7+1=15X(n)=2n-1 n04（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)/25（3）换名 上面形式的在递推关系式，一个规模为n的问题，每一次递归调用后，都简化为n/k规模的问题，为了方便求解，我们通常设定：n=km，则，上面的求解过程可简化为： f(n)= f(km-1)+b = f(km-2)+2b = = f(k0)+m

3、b = f(1) + blog n 6第一种递归关系式：因为规模每一次递归调用后，缩减为原来的1/2，所以采用换名方法求解，设 n = 2k：C(n) = C(2k)= C(2k-1)+1 = C(2k-2) + 2 = =C(2k-k)+k =C(1) + k = logn+17第二种递归调用，每次规模是原来的1/2：因为每一次规模都减到原来的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

4、-1) =T(1)+(2k+1-2)-k =2n-logn-18算法时间复杂度：O(n)分析：算法的复杂度有两部分决定：递归和合并，递归的复杂度是：logn，合并的复杂度是 n。9第三种递推关系式：10T(n)=2T(n/2) +n 设n= 2k =2T(2k-1)+2k =22T(2k-2)+2k-1+2k =22T(2k-2)+2*2k = =2k-1T(2k-(k-1) + (k-1)*2k =n/2 + (logn-1) *n11不失一般性，设规模为n的问题，每一次有分解为m个子问题，设n =mk，则：12T(n)=mT(n/m) +n =mT(mk-1)+mk =mmT(mk-2)+

5、mk-1+mk =m2T(mk-2)+2*mk = =mkT(2k-k) + k*mk =n + logn *n13算法时间复杂度：O(nlogn)分析：算法的复杂度有两部分决定：递归和合并，递归的复杂度是：n，合并的复杂度是 nlogn。14减治法的基本思想 将规模为n的问题递减为规模为n-1或n/2的子问题,反复递减后对子问题分别求解,再建立子问题的解与原问题的解的关系。减治法有两个变形: 减因子(如1/2):每次迭代规模减半n n/2 减可变规模:每次迭代减小的规模不同15递归复杂性的一般形式一般的，递归复杂性可描述为递归方程： 1 n = 1 af(n b) + D(n) n1f(n) =其中，a是子问题个数， 表示递减方式， b是递减步长， D(n)是合成子问题的开销。通常，递归元的递减方式有两种：1、减法，即n b，的形式。2、除法，即n / b，的形式；分治法递推法2022/8/1316分治