algorithm - 如何得到这个递归: T(n) = sqrt(n) * T(sqrt(n)) + n的时间复杂度

Question

这次重复:

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

它似乎无法用 Master 定理求解。它似乎也无法用 Akra-Bazzi 解决。即使我设置 n = 2^k 以便 T(2^k) = 2^(k/2) * T(2^(k/2)) + 2^k 然后S(k) = T(2^k) 它变为 S(n) = 2^(n/2) * S(n/2) + 2^n但乘数不是常数，因此更改变量也不起作用。

我不确定如何推导出这种循环的封闭形式或时间复杂度，如果它是在采访中给我的。你会怎么做？

Answer 1

我没有在这里使用任何常用技术。

请注意，没有基本情况。让我们考虑T(a) = b其中 a和 b是常量作为基本情况。

除以'n'，我们得到: T(n) / n = T(sqrt(n)) / sqrt(n) + 1

使用 g(k) = T(k) / k

所以 g(n) = g(sqrt(n)) + 1

这基本上意味着 g(n)是我们可以采取sqrt(n)的次数在此之前我们达到了不变的基本情况 a .

这意味着有一个 k这样 n^(1/2^k) >= a和 n^(1/2^(k+1)) < a .

让n^(1/2^k) = a => n = a^(2^k) => lg(n) = 2^k => lg(lg(n)) = k .那么g(n) = k + b = O(log(log(n))) .

这意味着 T(n) = n * O(log(log(n))) = O(n * log(log(n))) .将其代入原方程似乎有道理。

验证:如果在 O() 中设置常量符号为 1让T(n) = n * lg(lg(n))其中 lg(n)是log到基地2 , 我们得到

RHS = sqrt(n) * (sqrt(n) * lg(lg(sqrt(n)))) + n
     = n * lg(1/2 * (lg(n))) + n
     = n * (lg(lg(n)) - 1) + n
     = n * lg(lg(n)) - n + n
     = T(n)
     = LHS