快速排序时间复杂度递推式求通项公式~
发布网友
发布时间：2022-04-22 06:43
共1个回答
热心网友
时间：2022-06-16 18:01
两边同除以n(n+1)得到
C(n)/(n+1) = 2/(n+1) + C(n-1)/n
然后取n=1,2,...求和得到
C(n)/(n+1) = 2(1/2+...+1/(n+1)) + O(1) = 2lnn + O(1)
所以C(n)=2nlnn + O(n)
