随机快速排序的期望运行时间分析

本文将探讨对大小为 n 的数组应用随机快速排序的不同分析方法。

(a) 对于 i ∈ {1, 2, ..., n}，令 Xi 为指示随机变量，表示数组中第 i 小的数字被选为枢轴的事件。也就是说，如果此事件发生，则 Xi = 1，否则 Xi = 0。推导出 E(Xi)。

解答：

在随机选择枢轴的情况下，每个元素被选为枢轴的概率是相等的，即 1/n。因此，E(Xi) 可以表示为：

E(Xi) = 1 * (1/n) + 0 * (1 - 1/n) = 1/n

(b) 令 T(n) 为表示随机快速排序在大小为 n 的数组上的运行时间的随机变量。证明：

E[T(n)] = 2 * (E[T(n/2)] + E[T(n/2 - 1)]) + n

证明：

随机快速排序的运行时间可以分为两个部分：选择枢轴和递归调用。选择枢轴的时间复杂度为 O(1)，递归调用的时间复杂度为 T(n/2) + T(n/2-1)。

对于选择枢轴的部分，根据 (a) 的结果，每个元素被选为枢轴的概率为 1/n。因此，选择枢轴的时间复杂度的期望可以表示为：

E[选择枢轴的时间复杂度] = (1/n) * O(1) = O(1/n)

对于递归调用的部分，根据递归的定义，我们可以将问题分解为两个子问题，大小为 n/2 和 n/2-1 的数组。因此，递归调用的时间复杂度的期望可以表示为：

E[递归调用的时间复杂度] = E[T(n/2)] + E[T(n/2 - 1)]

综上所述，我们可以得到：

E[T(n)] = 2 * (O(1/n) + E[T(n/2)] + E[T(n/2 - 1)]) + n = 2 * (E[T(n/2)] + E[T(n/2 - 1)]) + n

(c) 证明 E[T(n)] = E[T(0)] + n。

证明：

根据 (b) 的结论，我们有：

E[T(n)] = 2 * (E[T(n/2)] + E[T(n/2 - 1)]) + n

当 n = 0 时，数组的大小为 0，即 T(0)。因此，我们可以得到：

E[T(0)] = 2 * (E[T(0/2)] + E[T(0/2 - 1)]) + 0 = 2 * (E[T(0)] + E[T(-1)])

由于空数组的排序时间为 0，我们可以假设 E[T(-1)] = 0。将其代入原式中，我们可以得到：

E[T(n)] = 2 * (E[T(n/2)] + E[T(n/2 - 1)]) + n = 2 * (E[T(n/2)] + E[T(n/2 - 1)]) + 2 * E[T(0)] = 2 * (E[T(n/2)] + E[T(n/2 - 1)] + E[T(0)]) + n = E[T(0)] + n

因此，E[T(n)] = E[T(0)] + n。

(d) 证明 -k log k < n log n - n。

证明：

我们将问题分为两种情况来证明。

情况 1： k = 2, 3, ..., (n/2) - 1

对于这种情况，我们有 k < n/2，因此 k log k < (n/2) log (n/2)。

情况 2： k = n/2, ..., n - 1

对于这种情况，我们有 k > n/2，因此 k log k < (n - 1) log (n - 1)。

综上所述，对于所有的 k，我们都有 -k log k < n log n - n。

(e) 使用 (d) 证明递归在 (c) 中的关系导致 E[T(n)] = O(n log n)。

证明：

根据 (c) 的结果，我们有 E[T(n)] = E[T(0)] + n。

当 n 足够大时，我们可以假设存在一个正常数 c，使得 E[T(n)] < c n log n。

将这个假设代入 (c) 的结果中，我们有：

E[T(n)] < c n log n + n < c n log n + n log n = (c + 1) n log n

因此，我们可以得出结论 E[T(n)] = O(n log n)。