《算法导论》第七章 续

7.4 快速排序分析

在7.2节中，我们给出了在最坏情况下快速排序性能的直观分析，以及它速度比较快的原因。在本节中，我们要给出快速排序性能的更严谨的分析。我们首先从最坏情况分析开始，其方法可以用于QUICKSORT和RANDOMIZED-QUICKSORT的分析，然后给出RANDOMIZED-QUICKSORT的期望运行时间。

7.4.1 最坏情况分析

在7.2节中，我们可以看到，在最坏情况下，快速排序的每一层递归的时间复杂度是Θ(n²)。从直观上来看，这也就是最坏情况下的运行时间。下面来证明这一点。利用代入法(见4.3节)，我们可以证明快速排序的时间复杂度为O(n²)。假设T(n)是最坏情况下QUICKSORT在输入规模为n的数据集合上所花费的时间，则有递归式：

因为PARTITION函数生成的两个子问题的规模加总为n-1，所以参数q的变化范围是0到n-1。我们不妨猜测T(n)≤cn²成立，其中c为常数。将此式代入递归式(7.1)中，得：

表达式q² +(n-q- 1)²在参数取值区间0≤q≤n-1的端点上取得最大值。由于该表达式对于q的二阶导数是正的(见练习7. 4-3)，我们可以得到表达式的上界(q²+(n-q-1)²)≤(n- 1)²=n²-2n+1将其代入上式的T(n)中，我们得到：

因为我们可以选择一个足够大的常数c，使得c(2n- 1)项能显著大于Θ(n)项，所以有T(n)=O(n²)。在7.2节中，我们看到了特例：当划分非平衡的时候，快速排序的运行时间为Θ(n²)。此外，在练习7.4-1中，要求你证明递归式(7.1)有另一个解T(n)=Ω(n²)。因此，快速排序的

(最坏情况)运行时间是Θ(n² )。

7.4.2 期望运行时间

我们已经从直观上了解了为什么RANDOMIZED-QUICKSORT的期望运行时间是O(n lgn)：如果在递归的每一层上，RANDOMIZED-PARTITION将任意常数比例的元素划分到一个子数组中，则算法的递归树的深度为Θ(lgn)，并且每一层上的工作量都是O(n)。即使在最不平衡的划分情况下，会增加一些新的层次，但总的运行时间仍然保持是O(nlgn)。要准确地分析RANDOMIZED-QUICKSORT的期望运行时间，首先要理解划分操作是如何进行的；然后，在此基础之上，推导出期望运行时间的一个O(lgn)的界。有了这一期望运行时间的上界，再加上7.2节中得到的最好情况界Θ(nlgn)，我们就能得到Θ(nlgn)这一期望运行时间。在这里，假设待排序的元素始终是互异的。

运行时间和比较操作

QUICKSORT和RANDOMIZED-QUICKSORT除了如何选择主元元素有差异以外，其他方面完全相同。因此，我们可以在讨论QUICKSORT和PARTITION的基础上分析RANDOMIZED-QUICKSORT。其中，RANDOMIZED-QUICKSORT随机地从子数组中选择元

素作为主元元素。

QUICKSORT的运行时间是由在PARTITION操作上所花费的时间决定的。每次对PARTITION的调用时，都会选择一个主元元素，而且该元素不会被包含在后续的对QUICKSORT和PARTITION的递归调用中。因此，在快速排序算法的整个执行期间，至多只可能调用PARTITION操作n次。调用一次PARTITION的时间为O(1)再加上一段循环时间。这段时间与第3~6行中for 循环的迭代次数成正比。这一for 循环的每一轮迭代都要在第 4行进行一次比较：比较主元元素与数组A中另一个元素。因此，如果我们可以统计第4行被执行的总次数，就能够给出在QUICKSORT的执行过程中，for 循环所花时间的界了。

引理7.1  当在一个包含n个元素的数组上运行QUICKSORT时，假设在PARTITION的第4行中所做比较的次数为X，那么QUICKSORT的运行时间为O(n+ X)。

证明  根据上面的讨论，算法最多对PARTITION调用n次。每次调用都包括一个固定的工作量和执行若干次for循环。在每一次 for循环中，都要执行第4行。

因此，我们的目标是计算出X，即所有对PARTITION的调用中，所执行的总的比较次数。我们并不打算分析在每一次PARTITION调用中做了多少次比较，而是希望能够推导出关于总的比较次数的一个界。为此，我们必须了解算法在什么时候对数组中的两个元素进行比较，什么时候不进行比较。为了便于分析，我们将数组A的各个元素重新命名为z)，z，...，zn，其中z；是数组A中第i小的元素。此外，我们还定义Z_ij={z, Z+1， ...，z_j}为z_i与z_j之间(含i和j)的元素集合。

算法什么时候会比较z_i和z_j呢？为了回答这个问题，我们首先注意到每一对元素至多比较一次。为什么呢？因为各个元素只与主元元素进行比较，并且在某一次PARTITION调用结束之后，该次调用中所用到的主元元素就再也不会与任何其他元素进行比较了。

我们的分析要用到指示器随机变量(见5.2节)。定义

其中我们考虑的是比较操作是否在算法执行过程中任意时间发生，而不是局限在循环的一次迭代或对PARTITION的一次调用中是否发生。因为每一对元素至多被比较一次， 所以我们可以很容易地刻画出算法的总比较次数：

对上式两边取期望，再利用期望值的线性特性和引理5.1，可以得到：

上式中的Pr{z_i与z_j进行比较}还需要进一步计算。在我们的分析中，假设RANDOMIZED-PARTITION随机且独立地选择主元。

让我们考虑两个元素何时不会进行比较的情况。考虑快速排序的一个输入，它是由数字1到10所构成(顺序可以是任意的)，并假设第一个主元是7。那么，对PARTITION的第一次调用就将这些输入数字划分成两个集合: {1，2, 3，4, 5, 6}和{8, 9, 10}。在这一过程中，主元7要

与所有其他元素进行比较。但是，第一个集合中任何一个元素(例如2)没有(也不会)与第二个集合中的任何元素(例如9)进行比较。

通常我们假设每个元素的值是互异的，因此，一旦一个满足z_i<x<z_j的主元x被选择后，我们就知道z;和z;以后再也不可能被比较了。另一种情况，如果z_i在z_ij中的所有其他元素之前被选为主元，那么z_i就将与z_j中除了它自身以外的所有元素进行比较。类似地，如果z_i在z_j中其他元素之前被选为主元，那么z_i将与z_ij中除自身以外的所有元素进行比较。在我们的例子中，值7和9要进行比较，因为7是Z_7.9中被选为主元的第一个元素。与之相反的是，值2和9则始终不会被比较，因为从Z_2,9中选择的第一个主元为7。因此，z_i与z_j会进行比较，当且仅当

Z_ij中将被选为主元的第一个元素是z_i或者z_j。

我们现在来计算这一事件发生的概率。 在z_i中的某个元素被选为主元之前，整个集合z_j的元素都属于某一划分的同一分区。因此，z_i中的任何元素都会等可能地被首先选为主元。因为集合Z_ij中有j-i+1个元素，并且主元的选择是随机且独立的，所以任何元素被首先选为主元

的概率是1/(j-i+1)。于是，我们有：

上式中第二行成立的原因在于其中涉及的两个事件是互斥的。将公式(7.2)和公式(7.3)综合起来，有：

在求这个累加和时，可以将变量做个变换(k=j-i)，并利用公式(A. 7)中给出的有关调和级数的界，得到：

于是，我们可以得出结论:使用RANDOMIZED-PARTITION，在输入元素互异的情况下，快速排序算法的期望运行时间为O(n lgn)。

练习

7.4-1 证明：在递归式

中，T（n）=Ω（n²）。

7.4-2  证明：在最好情况下，快速排序的运行时间为Ω(n lgn)。

7.4-3  证明：在q=0, 1, ...，n-1区间内，当q=0或q=n-1时，q²+(n-q-1)²取得最大值。

7.4-4  证明：RANDOMIZED-QUICKSORT期望运行时间是Ω(n lgn)。

7.4-5  当输入数据已经“几乎有序”时，插入排序速度很快。在实际应用中，我们可以利用这一特点来提高快速排序的速度。当对一个长度小于k的子数组调用快速排序时，让它不做任何排序就返回。当上层的快速排序调用返回后，对整个数组运行插入排序来完成排序过程。试证明：这一排序算法的期望时间复杂度为O(nk+ nlg(n/k))。分别从理论和实践的角度说明我们应该如何选择k？

*7.4-6 考虑对PARTITION过程做这样的修改：从数组A中随机选出三个元素，并用这三个元素的中位数(即这三个元素按大小排在中间的值)对数组进行划分。求以a的函数形式表示的、最坏划分比例为a∶(1- a)的近似概率，其中0<a<1。

思考题

7-1  (Hoate划分的正确性) 本章中的PARTITION算法并不是其最初的版本。下面给出的是最早由C. R. Hoare所设计的划分算法：

a.试说明HOARE-PARTTION在数组A=<13, 19，9，5，12，8，7, 4，11，2, 6，21>上的操作过程，并说明在每一次执行第 4~13行while循环时数组元素的值和辅助变量的值。后续的三个问题要求读者仔细论证HOARE-PARTITION的正确性。在这里假设子数组A[p..r]至少包含来2个元素，试证明下列问题：

b.下标i和j可以使我们不会访问在子数组A[p.. r]以外的数组A的元素。

c.当HOARE-PARTITION结束时，它返回的值j满足pSj<r.

d.当HOARE-PARTITION结束时，A[p.. j]中的每- -个元素都小于或等于A[j+1.. r]中的元素。

在7.1节的PARTTION过程中，主元(原来存储在A[r]中)是与它所划分的两个分区分离的。与之对应，在HOARE-PARTITION中，主元(原来存储在A[p]中)是存在于分区A[p..j]或A[j+1..r]中的。因为有p≤j<r，所以这一-划分总是非平凡的。

e.利用HOARE-PARTITION，重写QUICKSORT算法。

7-2  (针对相 同元素值的快速排序)在7. 4.2节对随机化快速排序的分析中，我们假设输入元素的值是互异的，在本题中，我们将看看如果这一假设不成立会出现什么情况。

a.如果所有输入元素的值都相同，那么随机化快速排序的运行时间会是多少？

b. PARTITION 过程返回一个数组下标q，使得A[p..q- 1]中的每个元素都小于或等于A[q]，而A[q+1.. r]中的每个元素都大于A[q]。修改PARTITION代码来构造一个新的PARTITION'(A，p，r)，它排列A[p.. r]的元素，返回值是两个数组下标q和t，其中p≤q≤t≤r，且有

• A[q..t]中的所有元素都相等。

• A[p..q- 1]中的每个元素都小于A[q]。

• A[t+1.. r门]中的每个元素都大于A[q]。

与PARTITION类似，新构造的PARTITION'的时间复杂度是Θ(r- p)。

c. 将RANDOMIZED-QUICKSORT过程改为调用PARTITION'，并重新命名为RANDOMIZED-QUICKSORT。修改QUICKSORT的代码构造一个新的QUICKSORT'(A，p，r),它调用RANDOMIZED-PARTITION'，并且只有分区内的元素互不相同的时候才做递归调用。

d.在QUICKSORT'中，应该如何改变7. 4.2节中的分析方法，从而避免所有元素都是互异的这一假设？

7-3  (另 一种快速排序的分析方法)对随机化版本的快速排序算法， 还有另一种性能分析方法，这一方法关注于每一次单独递归调用的期望运行时间，而不是比较的次数。

a. 证明：给定一个大小为n的数组，任何特定元素被选为主元的概率为1/n。 利用这一点来定义指示器随机变量X_i= I{第i小的元素被选为主元}，E[X_i]是什么？

b.设T(n)是一个表示快速排序在一个大小为n的数组上的运行时间的随机变量，试证明：

c.证明公式(7. 5)可以重写为：

d.证明：

e.利用公式(7. 7)中给出的界证明：公式(7. 6)中的递归式有解E[T(n)]=Θ(nlgn)。(提示：使用代入法，证明对于某个正常数a和足够大的n，有E[T(n)]≤an lgn。)

7-4  (快速排序的栈深度) 7.1 节中的QUICKSORT算法包含了两个对其自身的递归调用。在调用PARTITION后，QUICKSORT分别递归调用了左边的子数组和右边的子数组。QUICKSORT中的第二个递归调用并不是必须的。我们可以用一个循环控制结构来代替它。这一技术称为尾递归，好的编译器都提供这一功能。考虑下面这个版本的快速排序，它模拟了尾递归情况：

a.证明：TAIL-RECURSIVE-QUICKSORT(A, 1, A. length)能正确地对数组A进行排序。编译器通常使用栈来存储递归执行过程中的相关信息，包括每一次递归调用的参数等。最新调用的信息存在栈的顶部，而第一次调用的信息存在栈的底部。当一个过程被调用时，其相关信息被压入栈中；当它结束时，其信息则被弹出。因为我们假设数组参数是用指针来指示的，所以每次过程调用只需要O(1)的栈空间。栈深度是在一次计算中会用到的栈空间的最大值。

b.请描述一种场景，使得针对一个包含n个元素数组的TAIL-RECURSIVE-QUICKSORT的栈深度是Θ(n)。

c.修改TAIL-RECURSIVE-QUICKSORT的代码，使其最坏情况下栈深度是Θ(lgn)，并且能够保持O(n lgn)的期望时间复杂度。

7-5 (三数取中划分) 一种改进 RANDOMIZED-QUICKSORT的方法是在划分时，要从子数组中更细致地选择作为主元的元素(而不是简单地随机选择)。常用的做法是三数取中法：从子数组中随机选出三个元素，取其中位数作为主元(见练习7.4-6)。对于这个问题的分析，

我们不妨假设数组A[1.. n]的元素是互异的且有n≥3。我们用A'[1.. n]来表示已排好序的数组。用三数取中法选择主元x，并定义p_i=Pr{x=A'[i]}。

a.对于i=2, 3，...，n-1，请给出以n和i表示的p_i的准确表达式(注意p₁=p_n=0)。

b.与平凡实现相比，在这种实现中，选择x=A'[「(n+ 1)/2」](即A[1.. n]的中位数)的值作为主元的概率增加了多少？假设n→∞,请给出这一概率的极限值。

c.如果我们定义一个“好”划分意味着主元选择x=A'[i]，其中n/3≤i≤2n/3。与平凡实现相比，这种实现中得到一个好划分的概率增加了多少？(提示：用积分来近似累加和。)

d.证明：对快速排序而言，三数取中法只影响其时间复杂度Ω(n lgn)的常数项因子。

7-6  (对区间的模糊排序)考虑这样的一种排序问题：我们无法准确知道待排序的数字是什么。但对于每一个数， 我们知道它属于实数轴上的某个区间。也就是说，我们得到了n个形如[a_i，b_i]的闭区间，其中a_i≤b_i。我们的目标是实现这些区间的模糊排序，即对j=1, 2, ... n,

生成一个区间的排列<i，in, .. in)， 且存在c_j∈[a_ij，b_ij]，满足c₁≤c₂≤...≤c_n。

a.为n个区间的模糊排序设计一个随机算法。你的算法应该具有算法的一般结构，它可以对左边端点(即a_i的值)进行快速排序，同时它也能利用区间的重叠性质来改善时间性能。(当区间重叠越来越多的时候，区间的模糊排序问题会变得越来越容易。你的算法应

能充分利用这一重叠性质。)

b.证明：在一般情况下，你的算法的期望运行时间为Θ(nlgn)。但是，当所有的区间都有重叠的时候，算法的期望运行时间为Θ(n)(也就是说，存在一个值x，对所有的i，都有x∈[a_i，b_i]。)你的算法不必显式地检查这种情况，而是随着重叠情况的增加，算法的性能自然地提高。