递归关系T(n)= T(n ^(1/2))+ T(n-n ^(1/2))+ n [英] Recurrence Relation T(n) = T(n^(1/2)) + T(n-n^(1/2)) + n

问题描述

我和我的朋友已经找到了这个问题，我们无法解决.它的琐碎和标准的替换方法实际上是行不通的(否则我们将无法正确应用它)这应该是快速排序的关键问题.

My friend and I have found this problem and we cannot figure out how to solve it. Its not trivial and standard substitution method does not really work(or we cannot apply it correctly) This should be quicksort with pivots at rank problem.

以下是复发:

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

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

任何帮助将不胜感激.谢谢！

Any help would be much appreciated. Thanks!

推荐答案

首先放松一下:

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

T(n) = T(n-n^(1/2)) + n, number of iteration is n^(1/2), in each iteration you'll have n-ksqrt(n) time complexity, so total time complexity is: ∑n-ksqrt(n) for 0<=k<=sqrt(n), which is n^(3/2).

现在解决您自己的问题:

Now solve your own problem:

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).

again calculate number of steps till arriving to zero or 1: first part `T(n^(1/2)) takes O(log log n) time, and second part takes O(sqrt(n)) times to arriving to zero or 1 (See my answer to related question), So second part dominates first part, Also in each iteration time complexity of second part causes to sqrt(n) extra item, which doesn't effect to the first part time complexity (n-sqrt(n)), so your total runtime is n*sqrt(n).

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