是否有可能解决递归关系

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

使用主定理？ 它不是形式

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

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

大师定理不能解决这个问题。但是，可以使用递归树方法求解为O(n log log n)。

这背后的直觉是要注意，在树的每个级别上，您都在做n个工作。顶层不显式工作。 n个子问题中的每一个对于n个工作的总和都不会工作n，等等。因此，现在的问题是递归树的深度。好吧，这是您可以在n变得足够小(例如，小于2)之前取n的平方根的次数。如果我们写

n = 2lg n

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

n1/(2k) = 2lg n/(2k)

我们想在小于2时停止

2lg n/(2k) = 2

lg n/(2k) = 1

lg n = 2k

lg lg n = k

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

更笼统地说，就像任何算法将输入大小重复减少一半一样，会让您想到" log n"，任何算法通过平方根反复减少输入大小都会使您想到" log log n"。例如，van Emde Boas树使用这种重复性。

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