如何解决这种递归关系：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）。

Answer 2

我在解决这个问题时遇到了麻烦：T（n）= 4 * T（sqrt（n））+ n

编辑：这里n是2的幂

此编辑很重要。所以我们说复发在2点停止。

所以现在的问题是递归树有多深。那么，这是在n变得足够小（比如小于2）之前你可以取n的平方根的次数。如果我们写

n = 2lg n

然后在每次递归调用时，n将采用其平方根。这相当于将上述指数减半，因此在k次迭代之后我们就有了这个

n1 /（2k）= 2lg n /（2k）

我们想在小于2时停止给予

2lg n /（2k）= 2

lg n /（2k）= 1

lg n = 2k

lg lg n = k

因此，在lg lg n次迭代的平方根后，递归停止。 （source）

对于每个递归，我们将有4个新分支，分支的总数是4 ^（树的深度）因此4^(lg lg n)。

编辑：

Source

Answer 3

   T(n) = 4 T(sqrt(n)) + n
   4 [ 4 T(sqrt(sqrt(n) + n ] + n
   4^k * T(n^(1/2^k)) +kn because n is power of 2.
   4^k * T(2^(L/2^k)) +kn   [  Let n = 2^L , L= logn]
   4^k * T(2) +kn   [  Let L = 2^k,  k = logL = log log n]
   2^2k * c +kn
   L^2 * c + nloglogn 
   logn^2 * c + nloglogn
   = O(nloglogn)

Answer 4

T(n) = 4T(√n) + n 
suppose that (n = 2^m) . so we have :
T(2^m) = 4T(2^(m/2)) + (2^m)
now let name T(2^m) as S(m):
S(m) = 4S(m/2) + m . now with master Method we can solve this relation, and the answer is :
S(m) = Θ(m^2) 
now we step back to T(2^m):
T(2^m) = Θ((2^m)^2)
now we need m to solve our problem and we can get it from the second line and we have :
n = 2^m   =>   m=lgn 
and the problem solved .
T(n) = Θ((2^lgn)^2)
T(n) = Θ(n^2)