随机化快速排序（Randomized Quicksort）的期望时间复杂度分析

字数 3232 2025-12-15 06:48:10

随机化快速排序（Randomized Quicksort）的期望时间复杂度分析

随机化快速排序是对经典快速排序的一种改进，通过在分区过程中随机选择基准元素（pivot）来避免最坏情况的发生，从而提高算法的平均性能。

一、问题描述

经典快速排序在最坏情况下（例如输入数组已排序或逆序）的时间复杂度为 \(O(n^2)\)，这在实际应用中是不可接受的。为了解决这个问题，我们引入随机化：在每次递归调用中，随机从当前子数组中选择一个元素作为基准元素。我们的目标是分析随机化快速排序的期望时间复杂度，证明其在期望意义下达到 \(O(n \log n)\)。

二、核心思想与算法步骤

随机化快速排序的整体框架与经典快速排序相同，唯一区别在于基准元素的选择方式。

1. 算法步骤

步骤1（基线条件）：如果子数组的长度为0或1，则直接返回（已经有序）。
步骤2（随机选择基准）：从当前子数组中随机选择一个元素作为基准（pivot）。
步骤3（分区）：重新排列数组，使得所有小于基准的元素都移到基准的左侧，所有大于基准的元素都移到基准的右侧（等于基准的元素可以放在任意一侧）。基准元素最终位于其正确的位置（即排序后最终所在的位置）。
步骤4（递归）：对基准左侧和右侧的两个子数组递归地执行随机化快速排序。

2. 随机化的意义

由于基准是随机选择的，我们无法预测具体的划分情况，但可以证明：对于任何固定的输入数组，随机化快速排序的期望运行时间是 \(O(n \log n)\)。这意味着算法的期望性能与输入数据的分布无关，从而避免了最坏情况。

三、期望时间复杂度分析

我们将详细推导随机化快速排序的期望比较次数（或期望运行时间）。设输入数组为 \(A\)，长度为 \(n\)。定义随机变量 \(X\) 为算法在整个排序过程中进行的元素比较的总次数。

1. 关键观察

快速排序的所有比较都发生在分区过程中。考虑数组中的两个元素 \(a_i\) 和 \(a_j\)（其中 \(i < j\)）。在排序过程中，\(a_i\) 和 \(a_j\) 最多比较一次（当其中一个被选为基准时，它们会被比较；之后它们会被划分到不同的子数组中，不会再比较）。

定义指示随机变量：

\[ X_{ij} = \begin{cases} 1 & \text{如果 } a_i \text{ 和 } a_j \text{ 在算法中被比较过} \\ 0 & \text{否则} \end{cases} \]

那么总比较次数 \(X = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} X_{ij}\)。

2. 计算 \(E[X_{ij}]\)

元素 \(a_i\) 和 \(a_j\) 被比较的充分必要条件是：在递归过程中，第一个被选为基准的元素是 \(a_i\) 或 \(a_j\)，且该基准元素来自包含 \(a_i\) 和 \(a_j\) 的当前子数组。换句话说，如果某个基准元素 \(a_k\)（满足 \(i < k < j\)）首先被选中，那么 \(a_i\) 和 \(a_j\) 会被划分到不同的子数组，之后永远不会再比较。

考虑集合 \(S_{ij} = \{a_i, a_{i+1}, \dots, a_j\}\)，共有 \(j-i+1\) 个元素。在算法中，第一次从 \(S_{ij}\) 中选出的基准元素决定了 \(a_i\) 和 \(a_j\) 的命运：

如果第一次选出的基准是 \(a_i\) 或 \(a_j\)，那么它们会被比较（概率为 \(\frac{2}{j-i+1}\)）。
如果第一次选出的基准是其他元素 \(a_k\)（\(i < k < j\)），那么 \(a_i\) 和 \(a_j\) 会被划分到两个不同的子数组中，之后永远不会再比较（因此 \(X_{ij}=0\)）。

由于基准选择是独立的，并且每个元素被选中的概率相等，因此：

\[ E[X_{ij}] = P(X_{ij}=1) = \frac{2}{j-i+1} \]

3. 计算期望总比较次数 \(E[X]\)

利用期望的线性性质（即使 \(X_{ij}\) 之间并不独立）：

\[ E[X] = E\left[ \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} X_{ij} \right] = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} E[X_{ij}] = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j-i+1} \]

令 \(k = j-i\)，则对于固定的 \(i\)，\(k\) 从 1 取到 \(n-i\)，且 \(j-i+1 = k+1\)。于是：

\[ E[X] = \sum_{i=1}^{n-1} \sum_{k=1}^{n-i} \frac{2}{k+1} \]

这个二重求和的上界可以简化。注意到内层求和 \(\sum_{k=1}^{m} \frac{2}{k+1} < \sum_{k=1}^{m} \frac{2}{k} = 2H_m\)，其中 \(H_m\) 是第 \(m\) 个调和数，满足 \(H_m \le \ln m + 1\)。因此：

\[ E[X] < \sum_{i=1}^{n-1} 2H_{n-i} \le \sum_{i=1}^{n-1} 2(\ln(n-i) + 1) \]

令 \(t = n-i\)，则 \(t\) 从 1 到 \(n-1\)：

\[ E[X] < \sum_{t=1}^{n-1} 2(\ln t + 1) = 2\sum_{t=1}^{n-1} \ln t + 2(n-1) \]

利用对数性质：\(\sum_{t=1}^{n-1} \ln t = \ln((n-1)!)\)，且由斯特林近似 \(\ln(n!) \approx n \ln n - n + O(\ln n)\)，可得：

\[ E[X] < 2\left( (n-1)\ln(n-1) - (n-1) + O(\ln n) \right) + 2(n-1) = 2(n-1)\ln(n-1) + O(\ln n) \]

因此，\(E[X] = O(n \log n)\)。由于快速排序的每一次比较以及其他操作（如交换）的总时间与比较次数成线性关系，所以随机化快速排序的期望时间复杂度为 \(O(n \log n)\)。

四、为什么这比最坏情况好？

经典快速排序的最坏情况发生在每次分区都极不平衡时（例如，每次基准都是最小或最大元素），导致递归树深度为 \(n\)，总比较次数为 \(\sum_{i=1}^{n} (n-i) = O(n^2)\)。随机化通过均匀随机选择基准，使得每次分区平衡的概率大大增加。虽然仍然可能出现不平衡的划分，但概率很低，因此期望性能达到 \(O(n \log n)\)。

五、实际应用与变体

实际实现：通常随机选择基准的方法是与子数组的第一个（或最后一个）元素交换，然后进行经典的分区操作。
工程优化：常结合其他策略，如三数取中（median-of-three）来进一步减少最坏情况概率，或当子数组较小时切换到插入排序。
稳定性：随机化快速排序是不稳定的排序算法（相等元素的相对顺序可能改变）。

六、总结

随机化快速排序通过简单的随机化策略，将最坏情况时间复杂度从 \(O(n^2)\) 降低到期望 \(O(n \log n)\)，且常数因子较小，在实践中非常高效。其期望复杂度的分析依赖于指示随机变量和调和数的性质，是概率分析在算法设计中的经典应用。

随机化快速排序（Randomized Quicksort）的期望时间复杂度分析随机化快速排序是对经典快速排序的一种改进，通过在分区过程中随机选择基准元素（pivot）来避免最坏情况的发生，从而提高算法的平均性能。一、问题描述经典快速排序在最坏情况下（例如输入数组已排序或逆序）的时间复杂度为 \(O(n^2)\)，这在实际应用中是不可接受的。为了解决这个问题，我们引入随机化：在每次递归调用中，随机从当前子数组中选择一个元素作为基准元素。我们的目标是分析随机化快速排序的期望时间复杂度，证明其在期望意义下达到 \(O(n \log n)\)。二、核心思想与算法步骤随机化快速排序的整体框架与经典快速排序相同，唯一区别在于基准元素的选择方式。 1. 算法步骤步骤1（基线条件）：如果子数组的长度为0或1，则直接返回（已经有序）。步骤2（随机选择基准）：从当前子数组中随机选择一个元素作为基准（pivot）。步骤3（分区）：重新排列数组，使得所有小于基准的元素都移到基准的左侧，所有大于基准的元素都移到基准的右侧（等于基准的元素可以放在任意一侧）。基准元素最终位于其正确的位置（即排序后最终所在的位置）。步骤4（递归）：对基准左侧和右侧的两个子数组递归地执行随机化快速排序。 2. 随机化的意义由于基准是随机选择的，我们无法预测具体的划分情况，但可以证明：对于任何固定的输入数组，随机化快速排序的期望运行时间是 \(O(n \log n)\) 。这意味着算法的期望性能与输入数据的分布无关，从而避免了最坏情况。三、期望时间复杂度分析我们将详细推导随机化快速排序的期望比较次数（或期望运行时间）。设输入数组为 \(A\)，长度为 \(n\)。定义随机变量 \(X\) 为算法在整个排序过程中进行的元素比较的总次数。 1. 关键观察快速排序的所有比较都发生在分区过程中。考虑数组中的两个元素 \(a_ i\) 和 \(a_ j\)（其中 \(i < j\)）。在排序过程中，\(a_ i\) 和 \(a_ j\) 最多比较一次（当其中一个被选为基准时，它们会被比较；之后它们会被划分到不同的子数组中，不会再比较）。定义指示随机变量： \[ X_ {ij} = \begin{cases} 1 & \text{如果 } a_ i \text{ 和 } a_ j \text{ 在算法中被比较过} \\ 0 & \text{否则} \end{cases} \] 那么总比较次数 \(X = \sum_ {i=1}^{n-1} \sum_ {j=i+1}^{n} X_ {ij}\)。 2. 计算 \(E[ X_ {ij} ]\) 元素 \(a_ i\) 和 \(a_ j\) 被比较的充分必要条件是：在递归过程中，第一个被选为基准的元素是 \(a_ i\) 或 \(a_ j\)，且该基准元素来自包含 \(a_ i\) 和 \(a_ j\) 的当前子数组。换句话说，如果某个基准元素 \(a_ k\)（满足 \(i < k < j\)）首先被选中，那么 \(a_ i\) 和 \(a_ j\) 会被划分到不同的子数组，之后永远不会再比较。考虑集合 \(S_ {ij} = \{a_ i, a_ {i+1}, \dots, a_ j\}\)，共有 \(j-i+1\) 个元素。在算法中，第一次从 \(S_ {ij}\) 中选出的基准元素决定了 \(a_ i\) 和 \(a_ j\) 的命运：如果第一次选出的基准是 \(a_ i\) 或 \(a_ j\)，那么它们会被比较（概率为 \(\frac{2}{j-i+1}\)）。如果第一次选出的基准是其他元素 \(a_ k\)（\(i < k < j\)），那么 \(a_ i\) 和 \(a_ j\) 会被划分到两个不同的子数组中，之后永远不会再比较（因此 \(X_ {ij}=0\)）。由于基准选择是独立的，并且每个元素被选中的概率相等，因此： \[ E[ X_ {ij}] = P(X_ {ij}=1) = \frac{2}{j-i+1} \] 3. 计算期望总比较次数 \(E[ X ]\) 利用期望的线性性质（即使 \(X_ {ij}\) 之间并不独立）： \[ E[ X] = E\left[ \sum_ {i=1}^{n-1} \sum_ {j=i+1}^{n} X_ {ij} \right] = \sum_ {i=1}^{n-1} \sum_ {j=i+1}^{n} E[ X_ {ij}] = \sum_ {i=1}^{n-1} \sum_ {j=i+1}^{n} \frac{2}{j-i+1} \] 令 \(k = j-i\)，则对于固定的 \(i\)，\(k\) 从 1 取到 \(n-i\)，且 \(j-i+1 = k+1\)。于是： \[ E[ X] = \sum_ {i=1}^{n-1} \sum_ {k=1}^{n-i} \frac{2}{k+1} \] 这个二重求和的上界可以简化。注意到内层求和 \(\sum_ {k=1}^{m} \frac{2}{k+1} < \sum_ {k=1}^{m} \frac{2}{k} = 2H_ m\)，其中 \(H_ m\) 是第 \(m\) 个调和数，满足 \(H_ m \le \ln m + 1\)。因此： \[ E[ X] < \sum_ {i=1}^{n-1} 2H_ {n-i} \le \sum_ {i=1}^{n-1} 2(\ln(n-i) + 1) \] 令 \(t = n-i\)，则 \(t\) 从 1 到 \(n-1\)： \[ E[ X] < \sum_ {t=1}^{n-1} 2(\ln t + 1) = 2\sum_ {t=1}^{n-1} \ln t + 2(n-1) \] 利用对数性质：\(\sum_ {t=1}^{n-1} \ln t = \ln((n-1)!)\)，且由斯特林近似 \(\ln(n !) \approx n \ln n - n + O(\ln n)\)，可得： \[ E[ X] < 2\left( (n-1)\ln(n-1) - (n-1) + O(\ln n) \right) + 2(n-1) = 2(n-1)\ln(n-1) + O(\ln n) \] 因此，\(E[ X] = O(n \log n)\)。由于快速排序的每一次比较以及其他操作（如交换）的总时间与比较次数成线性关系，所以随机化快速排序的期望时间复杂度为 \(O(n \log n)\) 。四、为什么这比最坏情况好？经典快速排序的最坏情况发生在每次分区都极不平衡时（例如，每次基准都是最小或最大元素），导致递归树深度为 \(n\)，总比较次数为 \(\sum_ {i=1}^{n} (n-i) = O(n^2)\)。随机化通过均匀随机选择基准，使得每次分区平衡的概率大大增加。虽然仍然可能出现不平衡的划分，但概率很低，因此期望性能达到 \(O(n \log n)\)。五、实际应用与变体实际实现：通常随机选择基准的方法是与子数组的第一个（或最后一个）元素交换，然后进行经典的分区操作。工程优化：常结合其他策略，如三数取中（median-of-three）来进一步减少最坏情况概率，或当子数组较小时切换到插入排序。稳定性：随机化快速排序是不稳定的排序算法（相等元素的相对顺序可能改变）。六、总结随机化快速排序通过简单的随机化策略，将最坏情况时间复杂度从 \(O(n^2)\) 降低到期望 \(O(n \log n)\)，且常数因子较小，在实践中非常高效。其期望复杂度的分析依赖于指示随机变量和调和数的性质，是概率分析在算法设计中的经典应用。