📄 chap10.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 10: MEDIANS AND ORDER STATISTICS</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="partiii.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="chap09.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="0797_13a1">CHAPTER 10: MEDIANS AND ORDER STATISTICS<a name="0797_13a1"></h1><P>
<a name="0797_139c"><a name="0797_139d"><a name="0797_139e"><a name="0797_139f">The <I>i</I>th <I><B>order statistic</I></B> of a set of <I>n</I> elements is the <I>i</I>th smallest element. For example, the <I><B>minimum</I></B> of a set of elements is the first order statistic (<I>i</I> = 1), and the <I><B>maximum</I></B> is the <I>n</I>th order statistic (<I>i</I> = <I>n</I>). A <I><B>median</I></B>, informally, is the "halfway point" of the set. When <I>n</I> is odd, the median is unique, occurring at <I>i</I> = (<I>n</I> + 1)/2. When <I>n</I> is even, there are two medians, occurring at <I>i</I> = <I>n</I>/2 and <I>i</I> = <I>n</I>/2 + 1. Thus, regardless of the parity of <I>n</I>, medians occur at <I>i</I> = <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>(<I>n</I> + 1)/2<FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrdr12.gif"></FONT> and <I>i</I> = <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrul14.gif"></FONT>(<I>n</I> + 1)/2<FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrur14.gif"></FONT>.<P>
<a name="0797_13a0">This chapter addresses the problem of selecting the <I>i</I>th order statistic from a set of <I>n</I> distinct numbers. We assume for convenience that the set contains distinct numbers, although virtually everything that we do extends to the situation in which a set contains repeated values. The <I><B>selection problem</I></B> can be specified formally as follows:<P>
<B>Input: </B>A set <I>A</I> of <I>n</I> (distinct) numbers and a number <I>i</I>, with 1 <img src="../images/lteq12.gif"> <I>i</I> <img src="../images/lteq12.gif"> <I>n</I>.<P>
<B>Output: </B>The element <I>x</I> <img src="../images/memof12.gif"> <I>A</I> that is larger than exactly <I>i</I> -1 other elements of <I>A</I>.<P>
The selection problem can be solved in <I>O</I>(<I>n </I>lg <I>n</I>) time, since we can sort the numbers using heapsort or merge sort and then simply index the <I>i</I>th element in the output array. There are faster algorithms, however.<P>
In Section 10.1, we examine the problem of selecting the minimum and maximum of a set of elements. More interesting is the general selection problem, which is investigated in the subsequent two sections. Section 10.2 analyzes a practical algorithm that achieves an <I>O</I>(<I>n</I>) bound on the running time in the average case. Section 10.3 contains an algorithm of more theoretical interest that achieves the <I>O</I>(<I>n</I>) running time in the worst case.<P>
<h1><a name="0799_13a4">10.1 Minimum and maximum<a name="0799_13a4"></h1><P>
<a name="0799_13a1"><a name="0799_13a2">How many comparisons are necessary to determine the minimum of a set of <I>n</I> elements? We can easily obtain an upper bound of <I>n</I> - 1 comparisons: examine each element of the set in turn and keep track of the smallest element seen so far. In the following procedure, we assume that the set resides in array <I>A</I>, where <I>length</I>[<I>A</I>] = <I>n</I>.<P>
<pre><a name="0799_13a3">MINIMUM (<I>A</I>)</sub></sup></pre><P>
<pre>1 <I>min</I> <img src="../images/arrlt12.gif"> <I>A</I>[1]</sub></sup></pre><P>
<pre>2 <B>for</B> <I>i</I> <img src="../images/arrlt12.gif"> 2 <B>to</B> <I>length</I>[<I>A</I>]</sub></sup></pre><P>
<pre>3 <B>do if</B> <I>min</I> > <I>A</I>[<I>i</I>]</sub></sup></pre><P>
<pre>4 <B>then</B> <I>min</I> <img src="../images/arrlt12.gif"> <I>A</I>[<I>i</I>]</sub></sup></pre><P>
<pre>5 <B>return</B> <I>min</I></sub></sup></pre><P>
Finding the maximum can, of course, be accomplished with <I>n</I> - 1 comparisons as well.<P>
Is this the best we can do? Yes, since we can obtain a lower bound of <I>n</I> - 1 comparisons for the problem of determining the minimum. Think of any algorithm that determines the minimum as a tournament among the elements. Each comparison is a match in the tournament in which the smaller of the two elements wins. The key observation is that every element except the winner must lose at least one match. Hence, <I>n</I> - 1 comparisons are necessary to determine the minimum, and the algorithm <FONT FACE="Courier New" SIZE=2>MINIMUM</FONT> is optimal with respect to the number of comparisons performed.<P>
An interesting fine point of the analysis is the determination of the expected number of times that line 4 is executed. Problem 6-2 asks you to show that this expectation is <img src="../images/bound.gif">(lg <I>n</I>).<P>
<h2>Simultaneous minimum and maximum</h2><P>
In some applications, we must find both the minimum and the maximum of a set of <I>n</I> elements. For example, a graphics program may need to scale a set of (<I>x, y</I>) data to fit onto a rectangular display screen or other graphical output device. To do so, the program must first determine the minimum and maximum of each coordinate.<P>
It is not too difficult to devise an algorithm that can find both the minimum and the maximum of <I>n</I> elements using the asymptotically optimal <img src="../images/omega12.gif">(<I>n</I>) number of comparisons. Simply find the minimum and maximum independently, using <I>n</I> - 1 comparisons for each, for a total of 2<I>n</I> - 2 comparisons.<P>
In fact, only 3<FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrul14.gif"><I>n</I></FONT>/2<FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrur14.gif"></FONT> comparisons are necessary to find both the minimum and the maximum. To do this, we maintain the minimum and maximum elements seen thus far. Rather than processing each element of the input by comparing it against the current minimum and maximum, however, at a cost of two comparisons per element, we process elements in pairs. We compare pairs of elements from the input first with <I>each other</I>, and then compare the smaller to the current minimum and the larger to the current maximum, at a cost of three comparisons for every two elements.<P>
<P>
<h2><a name="079b_0001">Exercises<a name="079b_0001"></h2><P>
<a name="079b_0002">10.1-1<a name="079b_0002"><P>
Show that the second smallest of <I>n</I> elements can be found with <I>n</I>+ <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrul14.gif"></FONT>lg <I>n</I><FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrur14.gif"></FONT> - 2 comparisons in the worst case. (<I>Hint:</I> Also find the smallest element.)<P>
<a name="079b_0003">10.1-2<a name="079b_0003"><P>
Show that <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrul14.gif"></FONT>3<I>n</I>/2<FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrur14.gif"></FONT> - 2 comparisons are necessary in the worst case to find both the maximum and minimum of <I>n</I> numbers. (<I>Hint:</I> Consider how many numbers are potentially either the maximum or minimum, and investigate how a comparison affects these counts.)<P>
<P>
<P>
<h1><a name="079c_13a9">10.2 Selection in expected linear time<a name="079c_13a9"></h1><P>
<a name="079c_13a4"><a name="079c_13a5"><a name="079c_13a6"><a name="079c_13a7">The general selection problem appears more difficult than the simple problem of finding a minimum, yet, surprisingly, the asymptotic running time for both problems is the same: <img src="../images/bound.gif">(<I>n</I>). In this section, we present a divide-and-conquer algorithm for the selection problem. The algorithm <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>SELECT</FONT> is modeled after the quicksort algorithm of Chapter 8. As in quicksort, the idea is to partition the input array recursively. But unlike quicksort, which recursively processes both sides of the partition, <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>SELECT</FONT> only works on one side of the partition. This difference shows up in the analysis: whereas quicksort has an expected running time of <img src="../images/bound.gif">(<I>n </I>lg <I>n</I>), the expected time of <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>SELECT</FONT> is <img src="../images/bound.gif">(<I>n</I>).<P>
<FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>SELECT</FONT> uses the procedure <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>PARTITION</FONT> introduced in Section 8.3. Thus, like <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT>, it is a randomized algorithm, since its behavior is determined in part by the output of a random-number generator. The following code for <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>SELECT</FONT> returns the <I>i</I>th smallest element of the array <I>A</I>[<I>p . . r</I>].<P>
<pre>RANDOMIZED-SELECT(<I>A, p, r, i</I>)</sub></sup></pre><P>
<pre>1 <B>if</B> <I>p</I> = <I>r</I></sub></sup></pre><P>
<pre>2 <B>then return</B> <I>A</I>[<I>p</I>]</sub></sup></pre><P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -