如何得到这个递归的时间复杂度：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

Answer 2

这些类型的递归可以通过展开递归、发现元素之间的相似性来解决。

现在递归会在某个时刻自行耗尽。如果 T(...) = T(a) = b，就会发生这种情况。任何合理的 a 都可以，所以我选择了 2。通过对两边取 log 来求解方程 n^(1/2^k) = 2，您会得到：k = log(log(n))。现在将它替换回你的递归：

如果n -> infinity，2^(-loglogn)的极限等于0，所以求和的第一个元素等于b。复杂度是O(n * log log (n))

看看其他一些 sqrt 重复：

T(n) = 2T(n^(1/2)) + log n?
T(n) = T(n^(1/2)) + Θ(lg lg n)
T(n) = 2T(n^(1/2)) + log n?

也没有人会在面试时给你这个。

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

How to get the time complexity of this recurrence: T(n) = sqrt(n) * T(sqrt(n)) + n

algorithm

big-o

recurrence

time-complexity

asymptotic-complexity