为什么不能应用大师定理

Question

做作业并坚持几个问题。

1. T(n) = T(2n/5)+n
2. T(n) = T(2n/3)+T(n/3)+n
3. T(n) = T(n?2)+n

有人告诉我，大师定理不能应用于所有这些。但为什么？他们的上限是多少（大哦）？

Answer 1

主方法仅适用于以下类型的重复。

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

对于问题，

1. T(n) = T(2n/5)+n

@templatetypedef 已经修改了这个递推方程以适合主定理

T(n) = T(n / (5/2)) + n

我想你可以从这里解决它。

2. T(n) = T(2n/3)+T(n/3)+n

显然，这不能通过主定理直接解决。我们应该尝试构建递归树并查看。递归树描绘了递归调用树和每次调用完成的工作量。以下是从这里拍摄的图像

所以，这简化为 O(n * log n)

3. T(n) = T(n?2)+n

显然，这不能通过主定理直接解决。有一个为减法和征服类型派生的修改公式。

此链接可能有用。

对于形式的重复，

T(n) = aT(n-b) + f(n)

where n > 1, a>0, b>0

如果 f(n) 是 O(n ^k ) 并且 k>=0，那么

1. 如果 a<1 那么 T(n) = O(n ^k )
2. 如果 a=1 则 T(n) = O(n ^k+1 )
3. 如果 a>1 那么 T(n) = O(n ^k * a ^n/b )

我想你可以从这里解决它。

希望能帮助到你！