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

Question

Closed. This question is off-topic。它当前不接受答案。












想改善这个问题吗？ Update the question，因此它是 on-topic，用于堆栈溢出。

已关闭8年。



Improve this question





是否有可能解决递归关系


T（n）=√nT（√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 = 2 lg 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树使用这种重复性。
有趣的是，该递归用于获得著名算法的运行时间，该算法可以确定性地假定计算机可以在恒定时间内取任意实数的底限，从而确定最接近的点对问题。

关于math - 求解递归关系T(n)=√nT(√n)+ n，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7280224/

上一篇：math - 求解递推关系 T(n) = √n T(√n) + n

下一篇：puredata - 纯数据帮助。如何在 Pd 中使用条件逻辑

相关文章：

javascript - 在Javascript中计算弧度的正确方法？

javascript - 是否有可能确定特定算术运算是否导致溢出

c++ - 如何在递归函数中计算返回结果？

c - 了解列表上通过引用调用的函数

Java二叉搜索树递归删除删除元素

loops - 我如何在最大值中使用循环来绘制多个向量？

algorithm - 如何找到两条线交点旁边的4个点

r - R中%in%的时间复杂度；有没有办法让它像 Python 中的集合一样 O(1)？

algorithm - 如何让它在 O(n) 中工作？

python - cProfile.run 函数调用与复杂性

Answer 1

大师定理不能解决这个问题。但是，可以使用递归树方法求解为O（n log log n）。
这背后的直觉是要注意到，在树的每个级别上，您都在做n个工作。顶层不显式工作。 √n个子问题中的每一个都对n个工作的总和进行√n个工作，依此类推。因此，现在的问题是递归树的深度。好吧，这就是您可以在n变得足够小（例如，小于2）之前取n的平方根的次数。如果我们写

n = 2 lg 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树使用这种重复性。
有趣的是，该递归用于获得著名算法的运行时间，该算法可以确定性地假定计算机可以在恒定时间内取任意实数的底限，从而确定最接近的点对问题。