计算递归方程的时间复杂度

Question

3

我在计算以下递归方程的复杂度时遇到了问题。

对我来说解决这个问题相当困难。有人能帮我解决这个问题吗？谢谢提前。

- guapi

1

请问您能否确认T(n)是复杂度还是您正在寻找计算T(n)的算法的复杂度？ - Stef

1

@Stef T(n) 是算法时间复杂度的递归方程。例如，归并排序的时间复杂度递归方程为 T(n) = 2T(n/2) + n，那么我们可以得到 T(n) = O(nlogn)。 - guapi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Hikmat Farhat · Accepted Answer

这是快速排序平均情况下的复杂度递归式，附有解决方案。

T(n)=O(n log n)

这里提供了快速排序算法的推导过程。