如何解决这种递归关系:T(n)= 4*T(sqrt(n))+ n

Question

我知道如何使用Master方法解决递归关系.另外我知道如何解决下面的重现:

T(n)= sqrt(n)*T(sqrt(n))+ n

T(n)= 2*T(sqrt(n))+ lg(n)

在上述两次递归中,递归树的每个级别都有相同的工作量.并且递归树中总共有log log n级别.

我在解决这个问题时遇到了麻烦:T(n)= 4*T(sqrt(n))+ n

编辑: 这里n是2的幂

Answer 1

假设n = 2 ^ k.我们有T(2 ^ k)= 4*T(2 ^(k/2))+ 2 ^ k.设S(k)= T(2 ^ k).我们有S(k)= 4S(k/2)+ 2 ^ k.通过使用Mater定理,我们得到S(k)= O(2 ^ k).由于S(k)= O(2 ^ k)并且S(k)= T(2 ^ k),因此T(2 ^ k)= O(2 ^ k),这意味着T(n)= O(n).