递推关系T(n) = sqrt(n * T(sqrt( n) ) +n)

Question

我认为这种递归的复杂性是O(n^2/3)‘通过变化变量和归纳法。但我不确定。这个解决方案正确吗？

Answer 1

我们知道：

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

因此：

T(n) < sqrt(n) * sqrt(T(sqrt(n)) + T(sqrt(n)))

1被T(sqrt(n))取代。所以,

T(n) < sqrt(2) * sqrt(n) * sqrt(T(sqrt(n))

现在，为了找到一个上界，我们需要解决以下的循环关系：

G(n) = sqrt(2n) * sqrt(G(sqrt(n))

为了解决这个问题，我们需要扩展它(假设n = 2^{2^k}和T(1) = 1)：

G(n) = (2n)^{1/2} * (2n)^{1/8} * (2n)^{1/32} * ... * (2n)^(1/2^k) => 
G(n) = (2n)^{1/2 + 1/8 + 1/32 + ... + 1/2^k} = 

如果我们从1/2中取一个因子，我们就会得到1/2 * (1 + 1/4 + 1/8 + ... + 1/2^{k-1})。正如我们所知，1 + 1/4 + 1/8 + ... + 1/2^{k-1}是一个具有1/4比率的几何级数，它在无穷远处等于4/3。因此，G(n) = Theta(n^{2/3})和T(n) = O(n^{2/3})。

注意，作为sqrt(n) * sqrt(T(sqrt(n)) < T(n)，我们可以显示类似于前一种情况的T(n) = Omega(n^{2/3})。意思是T(n) = Theta(n^{2/3})。