解决递归关系式 T(n) = √n T(√n) + n，其中涉及到编程和计算问题。

Question

是否可能使用主定理（Master Theorem）解决递归关系式

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

？它不是形如

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

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

- ahollyhock

---

一个类似的问题：http://math.stackexchange.com/questions/689887/asymptotic-solution-of-recurrence-equation/689898#689898 - gt6989b

Answer 1

这个问题不能通过主定理来解决。但是，可以使用递归树方法来解决到O(n log log n)。

其背后的直觉是注意到在树的每个层级上，都需要n个单位的工作量。顶层显式地执行n个单位的工作。每个√n子问题执行√n工作，总共共同完成n个单位的工作，以此类推。那么现在的问题就是递归树有多深。好吧，这是您可以对n进行平方根多少次，直到n变得足够小（比如小于2）的次数。如果我们写成

n = 2^{lg n}

那么在每次递归调用中，n将会被取其平方根。这相当于将上面的指数除以2，因此经过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 log log n)。

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

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

- templatetypedef

---

谢谢！我尝试使用递归树来解决它，但完全忽略了每个级别的成本将是常数= n的要点！！ :) - ahollyhock

实际上，如果您将n = 2 ^（2 ^ k）重写，则可以使用主定理。在这种情况下，T（n）=√n T（√n）+ n变为：T（2 ^（2 ^ k））= 2 ^（2 ^ k-1）T（2 ^（2 ^ k-1））+ 2 ^（2 ^ k）。但是，在这里'a'和'b'不是常数。我认为应该有一种方法，但现在想不出任何方法。 - dhruvbird

感谢您的清晰解释。在推导log log n时，我认为从n^(1/(2^k)) = 2开始更容易理解，然后将两边都提高到(2^k)，结果为n = 2^(2^k)，然后就可以得到如上所述的log log n = k。 - iano

你所说的是针对 T(sqrt n) 的，但是在乘法中有一个 (sqrt n)。这不会被考虑吗？ - Coffee_lover

T(n) = 4*T(sqrt(n)) + n，我们能否也使用上述方法来解决这个问题？问题链接：http://stackoverflow.com/questions/13458399/how-to-solve-this-recurrence-relation-tn-4tsqrtn-n - Coffee_lover