math - 求解递推关系 T(n) = √n T(√n) + n

Question

是否可以解决递推关系

T(n) = √n T(√n) + n

使用主定理？它不是这样的形式

T(n) = a ⋅ T(n / b) + f(n)

但是这个问题是在 CLRS 第 4 章的练习中给出的。

Answer 1

这不能用主定理解决。不过可以使用递归树的方法来解决，解析为O(n log log n)。

这背后的直觉是注意到在树的每个级别，您都在做 n 项工作。顶层明确地工作。每个 √n 子问题都对 √n 项工作，总共完成 n 项工作，等等。所以现在的问题是递归树有多深。嗯，这是在 n 变得足够小(例如小于 2)之前可以对 n 求平方根的次数。如果我们写

n = 2^{lg n}

然后在每次递归调用时 n 将取其平方根。这相当于将上述指数减半，因此经过 k 次迭代后我们得到

n^1/(2k) = 2^{lg n/(2k)}

当这个值小于 2 时，我们想停止

2^{lg n/(2k)} = 2

lg n/(2^k) = 1

lg n = 2^k

lg lg n = k

因此，在 lg lg n 次平方根迭代之后，递归停止。并且，由于在每个级别递归的工作时间为 O(n)，因此总运行时间为 O(n lg lg n)。

更一般地说，就像任何反复将其输入大小减半的算法都会让您想到“log n”一样，任何通过取平方根反复减少其输入大小的算法都会让您想到“log log n”。 ”。例如，van Emde Boas 树就使用这种递归。

有趣的是，这种递归用于获取著名算法的运行时间，该算法用于确定性地解决最近点对问题，假设计算机可以在恒定时间内取任意实数的下限。