algorithm - 如何计算这个函数的增长率 : T(n) = 2T(n^(1/2)) + 2(n^(1/2))

Question

我的作业需要计算这个函数的增长率:

T(n) = 2T( n^(1/2) ) + 2( n^(1/2) )

换句话说:

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

改变变量可能会有帮助(比如 n = 2^m)

我找到的答案是 log(n)*log(log(n))，但我知道这是不正确的。

Answer 1

n = 2^m 确实是要使用的正确变量替换。定义一个函数S(m):

S(m) = T(n) = T(2^m)

T(sqrt(n)) = T(2^[m/2]) = S(m/2)

S(m) = 2S(m/2) + 2^[m/2+1]

扩展:

S(m) =  4*S(m/4)  + 2*2^[m/4+1]  + 2^[m/2+1]
     =  8*S(m/8)  + 4*2^[m/8+1]  + 2^[m/4+2] + 2^[m/2+1]
     = 16*S(m/16) + 8*2^[m/16+1] + 2^[m/8+3] + 2^[m/4+2] + 2^[m/2+1]
     = ...

2^[m/2] 将支配所有其他项，因此:

S(m) = O(2^[m/2])

*********************
*                   *
* T(n) = O(sqrt(n)) *
*                   *
*********************

以上也可以使用Master Theorem推导出来(案例 3)。