【算法】Master Theorem 计算递归算法的时间复杂度
目录
- 前言
- Master Theorem
- 递归求区间的最大值
前言
递归算法非常常见，那怎么计算递归的时间复杂度呢？
Master Theorem
master公式 : T(n)=a*T(n/b)+O(n^c) , a、b、c 都是常数
注意：只有所有子问题规模相同的递归才能用master公式计算时间复杂强度
如果log(b,a)<c,复杂度为：O(n^c)
如果log(b,a)>c,复杂度为：O(n^log(b,a))
总结为：log(a,b)和c哪个更大，哪个作为n的指数
如果log(b,a)=c,复杂度为：O(n^c * logn) （这个特殊一点）
补充:
T(n)=2 * T(n/2)+O(n*logn),时间复杂度是O(n * ((logn)的平方))，证明过程略，知道即可
举个例子来计算一下递归的时间复杂度
递归求区间的最大值
简单实现一下：
# 递归求[l,r]区间最大值
def getMax(l, r):
if l == r:
return a[l]
mid = (l + r) // 2
return max(getMax(l, mid), getMax(mid + 1, r))
n = int(input())
a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(getMax(0, n - 1))
可以发现：
这个递归实现可以表示为：
T(n)=2T(n/2)+O(1)
根据：T(n)=aT(n/b)+O(n^c) 易得a=2，b=2，c=0
log(a,b)=1>c , 所以时间复杂度为O(n)
END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢