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

Question

我和我的 friend 发现了这个问题，但我们不知道如何解决。它不是微不足道的标准替换方法并没有真正起作用(或者我们无法正确应用它)这应该是在等级问题上使用枢轴的快速排序。

这是重复的:

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

任何帮助将不胜感激。谢谢!

Answer 1

先放轻松:

T(n) = T(n-n^(1/2)) + n，迭代次数为n^(1/2)，在每次迭代中你将有n-ksqrt(n)的时间复杂度, 所以总的时间复杂度是: ∑n-ksqrt(n) 对于 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(参见我的 answer 相关问题)，因此第二部分支配第一部分，同样在每次迭代中第二部分的时间复杂度导致 sqrt(n) 额外项目，这对第一部分没有影响时间复杂度 (n-sqrt(n))，因此您的总运行时间为 n*sqrt(n)。