快速排序最坏情况运行时间的重复性

Question

假设我们构建了一个快速排序算法，枢轴值花费线性时间。找到最坏情况下的递归公式。

我的回答： T(n)= T(n-1) + T(1) + theta(n)

当子数组完全不平衡时发生最坏情况。一个子数组中有1个元素，另一个子数组中有(n-1)个元素。theta(n)是因为寻找枢轴需要n的运行时间。

我做对了吗？

- Jonathan Lam

---

不是2的n次方？ - Four_lo

我刚刚发现了一个关于递归关系的非常好的教程，看起来是一个很棒的资源： http://www.cs.duke.edu/~ola/ap/recurrence.html - Nathan

@Nathan 真是一个非常好的资源。我一下子就明白了如何解决递归关系。谢谢。 - Gaurav Kumar

Answer 1

你的递归算法大致正确，但实际上你并没有进行两个递归调用。在快速排序的最坏情况下，枢轴将是数组中最大或最小的元素，因此您需要对一个大小为n-1的巨大数组进行递归操作。另一个子数组的长度为0，因此不进行任何递归调用。最后，在每个级别上完成的总工作量为Θ(n)，所以递推关系更应该是

T(n) = T(n - 1) + Θ(n)

这反过来又解决了Θ(n²)的问题。

希望这能帮到你！

- templatetypedef

Answer 2

根据我的研究，T(N) = T(N-K) + T(K-1) + n，因此我们在没有k的值之前无法观察到确切的值。

- Ali

Answer 3

T(n) = T(an/(a+b)) + T(bn/(a+b)) + n

其中a/(a+b)和b/(a+b)是考虑数组的分数。

- daddy_