1

我试图证明 Quicksort 算法的以下最坏情况，但遇到了一些麻烦。最初，我们有一个大小为 n 的数组，其中 n = ij。这个想法是，在快速排序的每个分区步骤中，您最终都会得到两个子数组，其中一个大小为 i，另一个大小为 i(j-1)。在这种情况下，i 是一个大于 0 的整数常数。我已经绘制了一些示例的递归树，并理解为什么这是最坏的情况，并且运行时间将是 theta(n^2)。为了证明这一点，我使用了迭代方法来求解递推方程：

T(n) = T(ij) = m if j = 1
T(n) = T(ij) = T(i) + T(i(j-1)) + cn if j > 1

T(i) = m
T(2i) = m + m + c*2i = 2m + 2ci
T(3i) = m + 2m + 2ci + 3ci = 3m + 5ci

所以看起来复发是：

                  j 
T(n) = jm + ci * sum k - 1 
                 k=1

在这一点上，我有点不知道该怎么做。看起来如果展开，最后的总和将导致 j^2，但我需要证明它以某种方式等于 n^2。任何有关如何继续此操作的解释将不胜感激。

4

2 回答 2

1

请注意，快速排序算法最坏的情况是当您有两个大小为 0 和 n-1 的子问题时。在这种情况下，每个级别都有这个递归方程：

T(n)   = T(n-1) + T(0) < -- at first level of tree
T(n-1) = T(n-2) + T(0) < -- at second level of tree
T(n-2) = T(n-3) + T(0) < -- at third level of tree
.
.
.

每个级别的成本总和是一个算术级数：

        n       n(n-1)
T(n) = sum k =  ------ ~ n^2 (for n -> +inf)
       k=1        2

它是 O(n^2)。

于 2012-08-19T10:05:10.070 回答
0

这是一个简单的数学问题。您正确计算的复杂性是

O(jm + ij^2)

你发现的是一个参数化的复杂性。标准 O(n^2) 包含在其中，如下所示 - 假设 i=1 你有一个标准的基本情况，所以 m=O(1) 因此 j=n 因此我们得到 O(n^2)。如果你把 ij=n 你会得到 O(nm/i+n^2/i) 。现在你应该记住的是 m 是 i 的函数，这取决于你将使用什么作为基本情况算法，因此 m=f(i) 因此你剩下 O(nf(i)/i + n^2/i ）。现在再次注意，由于没有用于一般排序的线性算法，因此 f(i) = omega(igi) 会给你 O(nlogi + n^2/i)。所以你只有一个自由度，就是 i。检查对于 i 的任何值，您不能将其降低到 nlogn 以下，这是基于比较的最佳界限。

现在我感到困惑的是，您正在做一些快速排序的最坏情况分析。这不是它的做法。当您说最坏情况时，这意味着您正在使用随机化，在这种情况下，最坏情况将始终是 i=1 时，因此最坏情况界限将是 O(n^2)。R. Motwani 和 Raghavan 在随机算法书中解释了一种优雅的方法，如果你是程序员，那么你可以看看 Cormen。

于 2012-08-24T14:04:01.253 回答