chap01.htm

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

Express the function <I>n</I><SUP>3</SUP>/1000 - 100<I>n</I><SUP>2</SUP> - 100<I>n</I> + 3 in terms of <img src="../images/bound.gif">-notation.<P>
<a name="06db_1163">1.2-6<a name="06db_1163"><P>
<a name="06db_115c">How can we modify almost any algorithm to have a good best-case running time?<P>
<P>


<P>







<h1><a name="06dc_115e">1.3 Designing algorithms<a name="06dc_115e"></h1><P>
<a name="06dc_115d">There are many ways to design algorithms. Insertion sort uses an <I><B>incremental</I></B> approach: having sorted the subarray <I>A</I>[1 . . <I>j</I> - 1], we insert the single element <I>A</I>[<I>j</I>] into its proper place, yielding the sorted subarray <I>A</I>[1 . . <I>j</I>].<P>
In this section, we examine an alternative design approach, known as &quot;divide-and-conquer.&quot; We shall use divide-and-conquer to design a sorting algorithm whose worst-case running time is much less than that of insertion sort. One advantage of divide-and-conquer algorithms is that their running times are often easily determined using techniques that will be introduced in Chapter 4.<P>





<h2><a name="06dd_1166">1.3.1 The divide-and-conquer approach<a name="06dd_1166"></h2><P>
<a name="06dd_115e">Many useful algorithms are <I><B>recursive</I></B> in structure: to solve a given problem, they call themselves recursively one or more times to deal with closely related subproblems. These algorithms typically follow a <I><B>divide-and-conquer </I></B>approach: they break the problem into several subproblems that are similar to the original problem but smaller in size, solve the subproblems recursively, and then combine these solutions to create a solution to the original problem.<P>
<a name="06dd_115f">The divide-and-conquer paradigm involves three steps at each level of the recursion:<P>
<B>Divide          </B>the problem into a number of subproblems.<P>
<B>Conquer          </B>the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.<P>
<B>Combine          </B>the solutions to the subproblems into the solution for the original problem.<P>
<a name="06dd_1160"><a name="06dd_1161"><a name="06dd_1162">The <I><B>merge sort</I></B> algorithm closely follows the divide-and-conquer paradigm. Intuitively, it operates as follows.<P>
<B>Divide:     </B>Divide the <I>n</I>-element sequence to be sorted into two subsequences of <I>n</I>/2 elements each.<P>
<B>Conquer:     </B>Sort the two subsequences recursively using merge sort.<P>
<B>Combine:     </B>Merge the two sorted subsequences to produce the sorted answer.<P>
We note that the recursion &quot;bottoms out&quot; when the sequence to be sorted has length 1, in which case there is no work to be done, since every sequence of length 1 is already in sorted order.<P>
<a name="06dd_1163"><a name="06dd_1164">The key operation of the merge sort algorithm is the merging of two sorted sequences in the &quot;combine&quot; step. To perform the merging, we use an auxiliary procedure <FONT FACE="Courier New" SIZE=2>MERGE</FONT>(<I>A,p,q,r</I>), where <I>A</I> is an array and <I>p,</I> <I>q, </I>and <I>r</I> are indices numbering elements of the array such that <I>p</I> <img src="../images/lteq12.gif"> <I>q</I> &lt; <I>r</I>. The procedure assumes that the subarrays <I>A</I>[<I>p</I>. .<I>q</I>] and <I>A</I>[<I>q</I> + 1. .<I>r</I>] are in sorted order. It <I><B>merges</I></B> them to form a single sorted subarray that replaces the current subarray <I>A</I>[<I>p</I>. .<I>r</I>].<P>
Although we leave the pseudocode as an exercise (see Exercise 1.3-2), it is easy to imagine a <FONT FACE="Courier New" SIZE=2>MERGE</FONT> procedure that takes time <img src="../images/bound.gif">(<I>n</I>), where <I>n</I> = <I>r</I> - <I>p</I> + 1 is the number of elements being merged. Returning to our card-playing motif, suppose we have two piles of cards face up on a table. Each pile is sorted, with the smallest cards on top. We wish to merge the two piles into a single sorted output pile, which is to be face down on the table. Our basic step consists of choosing the smaller of the two cards on top of the face-up piles, removing it from its pile (which exposes a new top card), and placing this card face down onto the output pile. We repeat this step until one input pile is empty, at which time we just take the remaining input pile and place it face down onto the output pile. Computationally, each basic step takes constant time, since we are checking just two top cards. Since we perform at most <I>n</I> basic steps, merging takes <img src="../images/bound.gif">(<I>n</I>) time.<P>
We can now use the <FONT FACE="Courier New" SIZE=2>MERGE</FONT> procedure as a subroutine in the merge sort algorithm. The procedure <FONT FACE="Courier New" SIZE=2>MERGE</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT>(<I>A,p,r</I>) sorts the elements in the subarray <I>A</I>[<I>p</I>. .<I>r</I>]. If <I>p</I> <img src="../images/gteq.gif"> <I>r</I>, the subarray has at most one element and is therefore already sorted. Otherwise, the divide step simply computes an index <I>q</I> that partitions <I>A</I>[<I>p</I>. .<I>r</I>] into two subarrays: <I>A</I>[<I>p</I>. .<I>q</I>], containing <I>n</I>/2] elements, and <I>A</I>[<I>q</I> + 1. .<I>r</I>], containing <img src="../images/hfbrdl12.gif"><I>n</I>/2<img src="../images/hfbrdr12.gif"> elements.<SUP>4<P>
<SUP>4</SUP>The expression <img src="../images/hfbrul14.gif"><I>x</I><img src="../images/hfbrur14.gif"><I> denotes the least integer greater than or equal to </I>x<I>, and <img src="../images/hfbrdl12.gif"></I>x<I><img src="../images/hfbrdr12.gif"></I> denotes the greatest integer less than or equal to <I>x</I>. These notations are defined in Chapter 2.<P>
<pre>MERGE-SORT(<I>A,p,r</I>)</sub></sup></pre><P>
<pre>1 <B>if</B> <I>p</I> &lt; <I>r</I></sub></sup></pre><P>
<pre>2     <B>then</B> <I>q</I> <img src="../images/arrlt12.gif"> <img src="../images/hfbrdl12.gif">(<I>p</I> + <I>r</I>)/2<img src="../images/hfbrdr12.gif"></sub></sup></pre><P>
<pre>3          MERGE-SORT(<I>A,p,q</I>)</sub></sup></pre><P>
<pre>4          MERGE-SORT(<I>A, q</I> + 1, <I>r</I>)</sub></sup></pre><P>
<pre>5          MERGE(<I>A,p,q,r</I>)</sub></sup></pre><P>
<a name="06dd_1165">To sort the entire sequence <I>A</I> = <img src="../images/lftwdchv.gif"><I>A</I>[1],<I>A</I>[2], . . . ,<I>A</I>[<I>n</I>]<img src="../images/wdrtchv.gif">, we call <FONT FACE="Courier New" SIZE=2>MERGE</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT>(<I>A</I>, 1, <I>length</I>[<I>A</I>]), where once again <I>length</I>[<I>A</I>] = <I>n</I>. If we look at the operation of the procedure bottom-up when <I>n</I> is a power of two, the algorithm consists of merging pairs of 1-item sequences to form sorted sequences of length 2, merging pairs of sequences of length 2 to form sorted sequences of length 4, and so on, until two sequences of length <I>n</I>/2 are merged to form the final sorted sequence of length <I>n</I>. Figure 1.3 illustrates this process.<P>
<P>







<h2><a name="06de_1167">1.3.2 Analyzing divide-and-conquer algorithms<a name="06de_1167"></h2><P>
<a name="06de_1166">When an algorithm contains a recursive call to itself, its running time can often be described by a <I><B>recurrence equation</I></B> or <I><B>recurrence</I></B>, which describes the overall running time on a problem of size <I>n</I> in terms of the running time on smaller inputs. We can then use mathematical tools to solve the recurrence and provide bounds on the performance of the algorithm.<P>
A recurrence for the running time of a divide-and-conquer algorithm is based on the three steps of the basic paradigm. As before, we let <I>T</I>(<I>n</I>) be the running time on a problem of size <I>n</I>. If the problem size is small enough, say <I>n</I> <img src="../images/lteq12.gif"> <I>c</I> for some constant <I>c</I>, the straightforward solution takes constant time, which we write as <img src="../images/bound.gif">(1). Suppose we divide the problem into <I>a</I> subproblems, each of which is 1/<I>b</I> the size of the original. If we take <I>D</I>(<I>n</I>) time to divide the problem into subproblems and <I>C</I>(<I>n</I>) time to combine the solutions to the subproblems into the solution to the original problem, we get the recurrence<P>
<img src="14_a.gif"><P>
<h4><a name="06de_1168">Figure 1.3 The operation of merge sort on the array A = <img src="../images/lftwdchv.gif">5, 2, 4, 6, 1, 3, 2, 6<img src="../images/wdrtchv.gif">. The lengths of the sorted sequences being merged increase as the algorithm progresses from bottom to top.<a name="06de_1168"></sub></sup></h4><P>
<img src="14_b.gif"><P>
In Chapter 4, we shall see how to solve common recurrences of this form.<P>





<h3>Analysis of merge sort</h3><P>
Although the pseudocode for <FONT FACE="Courier New" SIZE=2>MERGE</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT> works correctly when the number of elements is not even, our recurrence-based analysis is simplified if we assume that the original problem size is a power of two. Each divide step then yields two subsequences of size exactly <I>n</I>/2. In Chapter 4, we shall see that this assumption does not affect the order of growth of the solution to the recurrence.<P>
We reason as follows to set up the recurrence for <I>T</I>(<I>n</I>), the worst-case running time of merge sort on <I>n</I> numbers. Merge sort on just one element takes constant time. When we have <I>n</I> &gt; 1 elements, we break down the running time as follows.<P>
<B>Divide:     </B>The divide step just computes the middle of the subarray, which takes constant time. Thus, <I>D</I>(<I>n</I>) = <img src="../images/bound.gif">(1).<P>
<B>Conquer:     </B>We recursively solve two subproblems, each of size <I>n</I>/2, which contributes 2<I>T</I>(<I>n</I>/2) to the running time.<P>
<B>Combine:     </B>We have already noted that the <FONT FACE="Courier New" SIZE=2>MERGE</FONT> procedure on an <I>n</I>-element subarray takes time <img src="../images/bound.gif">(<I>n</I>), so <I>C</I>(<I>n</I>) = <img src="../images/bound.gif">(n).<P>
When we add the functions <I>D</I>(<I>n</I>) and <I>C</I>(<I>n</I>) for the merge sort analysis, we are adding a function that is <img src="../images/bound.gif">(<I>n</I>) and a function that is <img src="../images/bound.gif">(1). This sum is a linear function of <I>n</I>, that is, <img src="../images/bound.gif">(<I>n</I>). Adding it to the 2<I>T</I>(<I>n</I>/2) term from the "conquer" step gives the recurrence for the worst-case running time <I>T</I>(<I>n</I>) of merge sort:<P>
<img src="15_a.gif"><P>
In Chapter 4, we shall show that T(<I>n</I>) is <img src="../images/bound.gif">(<I>n</I> 1g <I>n</I>), where 1g <I>n</I> stands for log<SUB>2</SUB> <I>n</I>. For large enough inputs, merge sort, with its <img src="../images/bound.gif">(<I>n</I> lg <I>n</I>) running time, outperforms insertion sort, whose running time is <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>), in the worst case.<P>
<P>


<P>







<h2><a name="06e0_116e">Exercises<a name="06e0_116e"></h2><P>
<a name="06e0_116f">1.3-1<a name="06e0_116f"><P>
Using Figure 1.3 as a model, illustrate the operation of merge sort on the array <I>A</I> = <img src="../images/lftwdchv.gif">3, 41, 52, 26, 38, 57, 9, 49<img src="../images/wdrtchv.gif">.<P>
<a name="06e0_1170">1.3-2<a name="06e0_1170"><P>
<a name="06e0_1167">Write pseudocode for <FONT FACE="Courier New" SIZE=2>MERGE</FONT>(<I>A,p,q,r</I>).<P>
<a name="06e0_1171">1.3-3<a name="06e0_1171"><P>