递归时间复杂度分析——master公式

【牛客左神的算法课笔记】

若递归可以写成如下形式： T ( n ) = a T ( n b ) O ( n d ) T(n) = aT(\frac{n}{b}) O(n^d) T(n)=aT(bn​) O(nd)
则时间复杂度计算如下：

  • if log ⁡ b a > d \log_ba > d logb​a>d ，复杂度为 O ( N log ⁡ b a ) O(N^{\log_ba}) O(Nlogb​a)
  • if log ⁡ b a = d \log_ba = d logb​a=d ，复杂度为 O ( N d ∗ l o g N ) O(N^{d*logN}) O(Nd∗logN)
  • if log ⁡ b a < d \log_ba < d logb​a<d ，复杂度为 O ( N d ) O(N^d) O(Nd)

其中，a表示初始迭代的子算法有几个，b表示初始将数组分成了几个部分，d表示递归完成后还要进行的复杂度。

举例，用递归求解一个数组的最大值，采用分治方法将数组均分为两部分左和右，分别计算两部分的最大值，其中最大的那个就是全数组的最大值。
代码如下：

# 递归分治求最大值 找到左边的最大值和右边的最大值，再比较def getMax(alist,L,R):    if L==R:        return alist[L]    mid = int((L R)/2)    maxLeft = getMax(alist,L,mid)    maxRight = getMax(alist,mid 1,R)    ans = max(maxLeft,maxRight)    return ansalist = [3,2,1,6,8,4]a = getMax(alist,0,len(alist)-1)

递归的时间复杂度可以写成 T ( n ) = 2 T ( n 2 ) O ( 1 ) T(n)=2T(\frac{n}{2}) O(1) T(n)=2T(2n​) O(1)
其中算法分成了左和右两个子算法，所以a=2；
数组被均分成了两部分，所以b=2；
递归完成后只做了比较运算，时间复杂度为O(1)，所以d=0
因此 log ⁡ b a > d \log_ba>d logb​a>d，时间复杂度为 O ( n ) O(n) O(n)

来源：https://www.icode9.com/content-4-808401.html

赞 (0)

相关推荐