chap08.htm

程序设计的艺术,此书是英文版的,经久不衰,非常的经典

<h1><a name="077f_1356">8.4 Analysis of quicksort<a name="077f_1356"></h1><P>
<a name="077f_1355">Section 8.2 gave some intuition for the worst-case behavior of quicksort and for why we expect it to run quickly. In this section, we analyze the behavior of quicksort more rigorously. We begin with a worst-case analysis, which applies to either <FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT> or <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT>, and conclude with an average-case analysis of <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT>.<P>





<h2><a name="0780_1357">8.4.1 Worst-case analysis<a name="0780_1357"></h2><P>
<a name="0780_1356">We saw in Section 8.2 that a worst-case split at every level of recursion in quicksort produces a <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>) running time, which, intuitively, is the worst-case running time of the algorithm. We now prove this assertion.<P>
Using the substitution method (see Section 4.1), we can show that the running time of quicksort is <I>O</I>(<I>n</I><SUP>2</SUP>). Let <I>T</I>(<I>n</I>) be the worst-case time for the procedure <FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT> on an input of size <I>n</I>. We have the recurrence<P>
<img src="163_a.gif"><P>
<h4><a name="0780_1358">(8.1)<a name="0780_1358"></sub></sup></h4><P>
where the parameter <I>q</I> ranges from 1 to <I>n</I> - 1 because the procedure <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> produces two regions, each having size at least 1. We guess that <I>T</I>(<I>n</I>)<I> </I><img src="../images/lteq12.gif"><I> cn</I><SUP>2 </SUP>for some constant <I>c</I>. Substituting this guess into (8.1), we obtain<P>
<img src="163_b.gif"><P>
The expression <I>q</I><SUP>2</SUP><I> + </I>(<I>n </I>-<I> q</I>)<SUP>2</SUP> achieves a maximum over the range 1 <img src="../images/lteq12.gif"> <I>q </I><img src="../images/lteq12.gif"> <I>n </I>- 1 at one of the endpoints, as can be seen since the second derivative of the expression with respect to <I>q</I> is positive (see Exercise 8.4-2). This gives us the bound max<SUB>1</SUB><img src="../images/lteq12.gif"><I>q</I><SUB><img src="../images/lteq12.gif"><I>n </I>- 1</SUB>(<I>q</I><SUP>2</SUP><I> </I>+<I> </I>(<I>n </I>-<I> q</I>)<SUP>2</SUP>) <img src="../images/lteq12.gif"><I> </I>1<SUP>2</SUP> <I>+</I> (<I>n </I>- 1)<SUP>2</SUP> =<I> n</I><SUP>2</SUP> - 2(<I>n</I> - 1).<P>
Continuing with our bounding of <I>T</I>(<I>n</I>)<I>,</I> we obtain<P>
<pre>T(<I>n</I>) <img src="../images/lteq12.gif"> <I>cn</I><SUP>2</SUP><I> </I>-<I> </I>2<I>c</I>(<I>n</I> - 1) + <img src="../images/bound.gif">(<I>n</I>)</sub></sup></pre><P>
<pre><img src="../images/lteq12.gif"> <I>cn</I><SUP>2 </SUP>,</sub></sup></pre><P>
since we can pick the constant <I>c</I> large enough so that the 2<I>c</I>(<I>n</I> - 1)<I> </I>term dominates the <img src="../images/bound.gif">(<I>n</I>) term. Thus, the (worst-case) running time of quicksort is <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>)<I>.</I><P>
<P>







<h2><a name="0781_1359">8.4.2 Average-case analysis<a name="0781_1359"></h2><P>
<a name="0781_1357"><a name="0781_1358">We have already given an intuitive argument why the average-case running time of <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT> is <img src="../images/bound.gif">(<I>n </I>1g <I>n</I>): if the split induced by <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>PARTITION</FONT> puts any constant fraction of the elements on one side of the partition, then the recursion tree has depth <img src="../images/bound.gif">(1g <I>n</I>) and <img src="../images/bound.gif">(<I>n</I>) work is performed at <img src="../images/bound.gif">(1g <I>n</I>) of these levels. We can analyze the expected running time of <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT> precisely by first understanding how the partitioning procedure operates. We can then develop a recurrence for the average time required to sort an <I>n</I>-element array and solve this recurrence to determine bounds on the expected running time. As part of the process of solving the recurrence, we shall develop tight bounds on an interesting summation.<P>





<h3>Analysis of partitioning</h3><P>
<a name="0782_1359">We first make some observations about the operation of <FONT FACE="Courier New" SIZE=2>PARTITION</FONT>. When <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> is called in line 3 of the procedure <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>PARTITION</FONT>, the element <I>A</I>[<I>p</I>] has already been exchanged with a random element in <I>A</I>[<I>p . . r</I>]. To simplify the analysis, we assume that all input numbers are distinct. If all input numbers are not distinct, it is still true that quick-sort's average-case running time is <I>O</I>(<I>n</I> lg <I>n</I>), but a somewhat more intricate analysis than we present here is required.<P>
<a name="0782_135a">Our first observation is that the value of <I>q</I> returned by <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> depends only on the rank of <I>x = A</I>[<I>p</I>] among the elements in <I>A</I>[<I>p . . r</I>]<I>.</I> (The <I><B>rank</I></B> of a number in a set is the number of elements less than or equal to it.) If we let <I>n</I> =<I> r</I> - <I>p</I> + 1 be the number of elements in <I>A</I>[<I>p . . r</I>], swapping <I>A</I>[<I>p</I>] with a random element from <I>A</I>[<I>p . . r</I>] yields a probability 1/<I>n </I>that rank(<I>x</I>) = <I>i</I> for <I>i</I> = 1,2, . . . , <I>n.</I><P>
We next compute the likelihoods of the various outcomes of the partitioning. If rank(<I>x</I>) = 1, then the first time through the <B>while </B>loop in lines 4-11 of <FONT FACE="Courier New" SIZE=2>PARTITION</FONT>, index <I>i</I> stops at <I>i</I> = <I>p</I> and index <I>j</I> stops at <I>j</I> = <I>p.</I> Thus, when <I>q</I> = <I>j</I> is returned, the &quot;low&quot; side of the partition contains the sole element <I>A</I>[<I>p</I>]. This event occurs with probability 1/<I>n</I> since that is the probability that rank(<I>x</I>) = 1.<P>
If rank(<I>x</I>) <img src="../images/gteq.gif"> 2, then there is at least one element smaller than <I>x = A</I>[<I>p</I>]<I>.</I> Consequently, the first time through the <I><B>while</I></B> loop, index <I>i</I> stops at <I>i</I> = <I>p</I> but <I>j</I> stops before reaching <I>p</I>. An exchange with <I>A</I>[<I>p</I>] is then made to put <I>A</I>[<I>p</I>] in the high side of the partition. When <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> terminates, each of the rank(<I>x</I>) - 1 elements in the low side of the partition is strictly less than <I>x</I>. Thus, for each <I>i</I> = 1,2, . . . , <I>n</I> - l, when rank(<I>x</I>) <img src="../images/gteq.gif"> 2, the probability is 1/<I>n</I> that the low side of the partition has <I>i</I> elements.<P>
Combining these two cases, we conclude that the size <I>q</I> - <I>p</I> + 1 of the low side of the partition is 1 with probability 2/<I>n</I> and that the size is <I>i</I> with probability 1 /<I>n</I> for <I>i</I> = 2,3, . . . , <I>n</I> - 1.<P>
<P>







<h3>A recurence for the average case</h3><P>
We now establish a recurrence for the expected running time of <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT>. Let <I>T</I>(<I>n</I>) denote the average time required to sort an <I>n</I>-element input array. A call to <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT> with a 1-element array takes constant time, so we have <I>T</I>(1) = <img src="../images/bound.gif">(1). A call to <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT> with an array <I>A</I>[l<I> . . n</I>] of length <I>n</I> uses time <img src="../images/bound.gif">(<I>n</I>) to partition the array. The <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> procedure returns an index <I>q,</I> and then <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT> is called recursively with subarrays of length <I>q</I> and <I>n</I> - <I>q</I>. Consequently, the average time to sort an array of length <I>n</I> can be expressed as<P>
<img src="165_a.gif"><P>
<h4><a name="0783_0001">(8.2)<a name="0783_0001"></sub></sup></h4><P>
The value of <I>q</I> has an almost uniform distribution, except that the value <I>q</I> = 1 is twice as likely as the others, as was noted above. Using the facts that <I>T</I>(1) = <img src="../images/bound.gif">(1) and <I>T</I>(<I>n</I> - 1) = <I>O</I>(<I>n</I><SUP>2</SUP>) from our worst-case analysis, we have<P>
<img src="165_b.gif"><P>
and the term <img src="../images/bound.gif">(<I>n</I>) in equation (8.2) can therefore absorb the expression <img src="165_c.gif">. We can thus restate recurrence (8.2) as<P>
<img src="165_d.gif"><P>
<h4><a name="0783_0002">(8.3)<a name="0783_0002"></sub></sup></h4><P>
Observe that for <I>k</I> = 1,2, . . . ,<I> n</I> - 1, each term <I>T</I>(<I>k</I>) of the sum occurs once as <I>T</I>(<I>q</I>) and once as <I>T</I>(<I>n - q</I>). Collapsing the two terms of the sum yields<P>
<img src="165_e.gif"><P>
<h4><a name="0783_0003">(8.4)<a name="0783_0003"></sub></sup></h4><P>
<P>







<h3>Solving the recurrence</h3><P>
We can solve the recurrence (8.4) using the substitution method. Assume inductively that <I>T</I>(<I>n</I>) <img src="../images/lteq12.gif"> <I>an</I> 1g <I>n </I>+<I> b</I> for some constants <I>a</I> &gt;<I> </I>0 and <I>b</I> &gt; 0 to be determined. We can pick <I>a</I> and <I>b</I> sufficiently large so that <I>an </I>1g <I>n</I> +<I> b</I> is greater than <I>T</I>(1). Then for <I>n</I> &gt; 1, we have by substitution<P>
<img src="166_a.gif"><P>
We show below that the summation in the last line can be bounded by<P>
<img src="166_b.gif"><P>
<h4><a name="0784_0001">(8.5)<a name="0784_0001"></sub></sup></h4><P>
Using this bound, we obtain<P>
<img src="166_c.gif"><P>
since we can choose <I>a</I> large enough so that <img src="166_d.gif"> dominates <img src="../images/bound.gif">(<I>n</I>) + <I>b</I>. We conclude that quicksort's average running time is <I>O</I>(<I>n</I> lg <I>n</I>).<P>
<P>







<h3>Tight bounds on the key summation</h3><P>
It remains to prove the bound (8.5) on the summation<P>
<img src="166_e.gif"><P>
Since each term is at most <I>n</I> lg <I>n</I>, we have the bound<P>
<img src="166_f.gif"><P>
which is tight to within a constant factor. This bound is not strong enough to solve the recurrence as <I>T</I>(<I>n</I>) = <I>O</I>(<I>n</I> lg <I>n</I>), however. Specifically, we need a bound of <img src="166_g.gif"> for the solution of the recurrence to work out.<P>
We can get this bound on the summation by splitting it into two parts, as discussed in Section 3.2 on page 48. We obtain<P>
<img src="167_a.gif"><P>
The lg <I>k</I> in the first summation on the right is bounded above by 1g(<I>n</I>/2) = 1g <I>n</I> - 1. The lg <I>k</I> in the second summation is bounded above by lg <I>n</I>. Thus,<P>
<img src="167_b.gif"><P>
if <I>n</I> <img src="../images/gteq.gif"> 2. This is the bound (8.5).<P>
<P>