algorithm - 递归关系 T(n) = T(n^(1/2)) + T(nn^(1/2)) + n

Question

我和我的朋友发现了这个问题，我们无法弄清楚如何解决它。它不是微不足道的，标准的替换方法并没有真正起作用（或者我们不能正确应用它）这应该是快速排序与等级问题的枢轴。

以下是重现：

T(n) = T(n^(1/2)) + T(nn^(1/2)) + n

任何帮助将非常感激。谢谢！

Answer 1

首先放轻松：

T(n) = T(nn^(1/2)) + n，迭代次数为 n^(1/2)，在每次迭代中，您将有 nk sqrt(n) 时间复杂度，因此总时间复杂度为: ∑nk sqrt(n) for 0<=k<=sqrt(n)，即 n^(3/2)。

现在解决你自己的问题：

T(n) = T(n^(1/2))+T(n-n^(1/2)) + n

再次计算到达零或 1 的步数：第一部分 `T(n^(1/2)) 花费 O(log log n) 时间，第二部分花费 O(sqrt(n)) 次到达零或 1（请参阅我对相关问题的回答），因此第二部分主导第一部分，而且在第二部分的每次迭代中，时间复杂度都会导致 sqrt(n) 额外项目，这不会影响第一部分的时间复杂度（n- sqrt(n))，所以你的总运行时间是 n*sqrt(n)。