求解递归关系T(n)=√nT(√n)+ n [英] Solving the recurrence relation T(n) = √n T(√n) + n

问题描述

是否可以解决递归关系

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

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

使用主定理?它不是形式

Using the Master Theorem? It is not of the form

T(n)=&s; T(n/b)+ f(n)

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

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

but this problem is given in the exercise of CLRS chapter 4.

推荐答案

这不能由主定理解决.但是，可以使用递归树方法将其解析为O(n log log n).

This cannot be solved by the Master Theorem. However, it can be solved using the recursion tree method to resolve to O(n log log n).

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

The intuition behind this is to notice that at each level of the tree, you're doing n work. The top level does n work explicitly. Each of the √n subproblems does √n work for a net total of n work, etc. So the question now is how deep the recursion tree is. Well, that is the number of times that you can take the square root of n before n gets sufficiently small (say, less than 2). If we write

n = 2 ^{lg n}

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

then on each recursive call n will have its square root taken. This is equivalent to halving the above exponent, so after k iterations we have that

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

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

我们要在小于2时停止，给予

We want to stop when this is less than 2, giving

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

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

lg n/(2 ^k )= 1

lg n/(2^k) = 1

lg n = 2 ^k

lg n = 2^k

lg lg n = k

lg lg n = k

因此，在平方根的lg lg次迭代之后，递归停止.而且，由于递归在每个级别上都是O(n)起作用的，因此总运行时间为O(n lg lg n).

So after lg lg n iterations of square rooting the recursion stops. And, since at each level the recursion does O(n) work, the total runtime is O(n lg lg n).

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

More generally, just as any algorithm that repeatedly cuts its input size in half should get you thinking "log n," any algorithm that repeatedly cuts its input size down by taking a square root should get you thinking "log log n.". van Emde Boas trees use this recurrence, for example.

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

Interestingly, this recurrence is used to obtain the runtime of a famous algorithm for solving the closest pair of points problem deterministically assuming that the computer can take the floor of an arbitrary real number in constant time.

这篇关于求解递归关系T(n)=√nT(√n)+ n的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！