chap01.htm

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

<a name="06d6_1143">Consider the problem of adding two <I>n</I>-bit binary integers, stored in two <I>n</I>-element arrays <I>A</I> and <I>B</I>. The sum of the two integers should be stored in binary form in an (<I>n</I> + 1)-element array <I>C</I>. State the problem formally and write pseudocode for adding the two integers.<P>
<P>


<P>







<h1><a name="06d7_1146">1.2 Analyzing algorithms<a name="06d7_1146"></h1><P>
<a name="06d7_1144"><I><B>Analyzing</I></B> an algorithm has come to mean predicting the resources that the algorithm requires. Occasionally, resources such as memory, communication bandwidth, or logic gates are of primary concern, but most often it is computational time that we want to measure. Generally, by analyzing several candidate algorithms for a problem, a most efficient one can be easily identified. Such analysis may indicate more than one viable candidate, but several inferior algorithms are usually discarded in the process.<P>
<a name="06d7_1145">Before we can analyze an algorithm, we must have a model of the implementation technology that will be used, including a model for the resources of that technology and their costs. For most of this book, we shall assume a generic one-processor,<I> <B>random-access machine</I></B> <B>(</B><I><B>RAM</I>)</B> model of computation as our implementation technology and understand that our algorithms will be implemented as computer programs. In the RAM model, instructions are executed one after another, with no concurrent operations. In later chapters, however, we shall have occasion to investigate models for parallel computers and digital hardware.<P>
Analyzing even a simple algorithm can be a challenge. The mathematical tools required may include discrete combinatorics, elementary probability theory, algebraic dexterity, and the ability to identify the most significant terms in a formula. Because the behavior of an algorithm may be different for each possible input, we need a means for summarizing that behavior in simple, easily understood formulas.<P>
Even though we typically select only one machine model to analyze a given algorithm, we still face many choices in deciding how to express our analysis. One immediate goal is to find a means of expression that is simple to write and manipulate, shows the important characteristics of an algorithm's resource requirements, and suppresses tedious details.<P>





<h2>Analysis of insertion sort</h2><P>
<a name="06d8_1146">The time taken by the <FONT FACE="Courier New" SIZE=2>INSERTION</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT> procedure depends on the input: sorting a thousand numbers takes longer than sorting three numbers. Moreover, <FONT FACE="Courier New" SIZE=2>INSERTION</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT> can take different amounts of time to sort two input sequences of the same size depending on how nearly sorted they already are. In general, the time taken by an algorithm grows with the size of the input, so it is traditional to describe the running time of a program as a function of the size of its input. To do so, we need to define the terms &quot;running time&quot; and &quot;size of input&quot; more carefully.<P>
<a name="06d8_1147"><a name="06d8_1148">The best notion for <I><B>input size</I></B> depends on the problem being studied. For many problems, such as sorting or computing discrete Fourier transforms, the most natural measure is the <I>number of items in the input</I>--for example, the array size <I>n</I> for sorting. For many other problems, such as multiplying two integers, the best measure of input size is the <I>total</I> <I>number of bits</I> needed to represent the input in ordinary binary notation. Sometimes, it is more appropriate to describe the size of the input with two numbers rather than one. For instance, if the input to an algorithm is a graph, the input size can be described by the numbers of vertices and edges in the graph. We shall indicate which input size measure is being used with each problem we study.<P>
<a name="06d8_1149"><a name="06d8_114a">The <I><B>running time</I></B> of an algorithm on a particular input is the number of primitive operations or &quot;steps&quot; executed. It is convenient to define the notion of step so that it is as machine-independent as possible. For the moment, let us adopt the following view. A constant amount of time is required to execute each line of our pseudocode. One line may take a different amount of time than another line, but we shall assume that each execution of the <I>i</I>th line takes time <I>c<SUB>i</I></SUB>, where <I>c<SUB>i</I></SUB> is a constant. This viewpoint is in keeping with the RAM model, and it also reflects how the pseudocode would be implemented on most actual computers.<SUP>2</sup><P>
<SUP>2</SUP>There are some subtleties here. Computational steps that we specify in English are often variants of a procedure that requires more than just a constant amount of time. For example, later in this book we might say "sort the points by <I>x</I>-coordinate," which, as we shall see, takes more than a constant amount of time. Also, note that a statement that calls a subroutine takes constant time, though the subroutine, once invoked, may take more. That is, we separate the process of <I><B>calling</I></B> the subroutine--passing parameters to it, etc.--from the process of <I><B>executing</I></B> the subroutine<I>.</I><P>
In the following discussion, our expression for the running time of <FONT FACE="Courier New" SIZE=2>INSERTION</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT> will evolve from a messy formula that uses all the statement costs c<I><SUB>i</I></SUB> to a much simpler notation that is more concise and more easily manipulated. This simpler notation will also make it easy to determine whether one algorithm is more efficient than another.<P>
<a name="06d8_114b">We start by presenting the <FONT FACE="Courier New" SIZE=2>INSERTION</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT> procedure with the time &quot;cost&quot; of each statement and the number of times each statement is executed. For each <I>j</I> = 2, 3, . . . , <I>n</I>, where <I>n</I> = <I>length</I>[<I>A</I>], we let <I>t<SUB>j</I> </SUB>be the number of times the <B>while</B> loop test in line 5 is executed for that value of <I>j</I>.<SUB> </SUB>We assume that comments are not executable statements, and so they take no time.<P>
<img src="8_a.gif"><P>
The running time of the algorithm is the sum of running times for each statement executed; a statement that takes <I>c<SUB>i</I></SUB> steps to execute and is executed <I>n</I> times will contribute <I>c<SUB>i </SUB>n</I> to the total running time.<SUP>3</SUP>  To compute <I>T</I>(<I>n</I>), the running time of <FONT FACE="Courier New" SIZE=2>INSERTION</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT>, we sum the products of the <I>cost</I> and <I>times</I> columns, obtaining<P>
<img src="8_b.gif"><P>
<SUP>3</SUP>This characteristic does not necessarily hold for a resource such as memory. A statement that references <I>m</I> words of memory and is executed <I>n</I> times does not necessarily consume <I>mn</I> words of memory in total.<P>
Even for inputs of a given size, an algorithm's running time may depend on <I>which</I> input of that size is given. For example, in <FONT FACE="Courier New" SIZE=2>INSERTION</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT>, the best case occurs if the array is already sorted. For each <I>j </I>= 2, 3, . . . , <I>n,</I> we then find that <I>A</I>[<I>i</I>]<img src="../images/lteq12.gif"> <I>key</I> in line 5 when <I>i</I> has its initial value of <I>j</I> - <I>1</I>. Thus <I>tj</I> = 1 for <I><SUP>j</I></SUP> = 2,3, . . ., <I>n</I>, and the best-case running time is<P>
<pre><I>T</I>(<I>n</I>) = <I>c</I><SUB>1</SUB><I>n</I> + <I>c</I><SUB>2</SUB> (<I>n</I> - 1) + <I>c</I><SUB>4</SUB> (<I>n</I> - 1) + <I>c</I><SUB>5</SUB> (<I>n</I> - 1) + <I>c</I><SUB>8</SUB> (<I>n</I> - 1)</sub></sup></pre><P>
<pre>= (<I>c</I><SUB>1</SUB> + <I>c</I><SUB>2</SUB> + <I>c</I><SUB>4</SUB> + <I>c</I><SUB>8</SUB>)<I>n </I>- (<I>c</I><SUB>2</SUB> + <I>c</I><SUB>4</SUB> + <I>c</I><SUB>5</SUB> + <I>c</I><SUB>8</SUB>).</sub></sup></pre><P>
<a name="06d8_114c">This running time can be expressed as <I>an</I> + <I>b</I> for <I>constants</I> <I>a</I> and <I>b</I> that depend on the statement costs <I>c<SUB>i</I></SUB>; it is thus a <I><B>linear function</I></B> of <I>n.</I><P>
If the array is in reverse sorted order--that is, in decreasing order--the worst case results. We must compare each element <I>A</I>[<I>j</I>] with each element in the entire sorted subarray <I>A[</I>1. . <I>j</I> - 1], and so <I>t<SUB>j</I></SUB> = <I>j</I> for <I>j</I> = 2,3, . . . , <I>n.</I> Noting that<P>
<img src="8_c.gif"><P>
and<P>
<img src="9_a.gif"><P>
(we shall review these summations in Chapter 3), we find that in the worst case, the running time of <FONT FACE="Courier New" SIZE=2>INSERTION</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT> is<P>
<img src="9_b.gif"><P>
<a name="06d8_114d"><a name="06d8_114e"><a name="06d8_114f">This worst-case running time can be expressed as <I>an</I><SUP>2</SUP> + <I>bn</I>+ <I>c</I> for constants <I>a</I>, <I>b</I>, and <I>c</I> that again depend on the statement costs <I>c<SUB>i</I></SUB>; it is thus a <I><B>quadratic</I></B> <I><B>function</I></B> of <I>n</I>.<P>
Typically, as in insertion sort, the running time of an algorithm is fixed for a given input, although in later chapters we shall see some interesting &quot;randomized&quot; algorithms whose behavior can vary even for a fixed input.<P>
<P>







<h2>Worst-case and average-case analysis</h2><P>
In our analysis of insertion sort, we looked at both the best case, in which the input array was already sorted, and the worst case, in which the input array was reverse sorted. For the remainder of this book, though, we shall usually concentrate on finding only the <I><B>worst-case running time</I></B>, that is, the longest running time for <I>any</I> input of size <I>n</I>. We give three reasons for this orientation.<P>
<FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif"></FONT>     The worst-case running time of an algorithm is an upper bound on the running time for any input. Knowing it gives us a guarantee that the algorithm will never take any longer. We need not make some educated guess about the running time and hope that it never gets much worse.<P>
<FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif"></FONT>     For some algorithms, the worst case occurs fairly often. For example, in searching a database for a particular piece of information, the searching algorithm's worst case will often occur when the information is not present in the database. In some searching applications, searches for absent information may be frequent.<P>
<FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif"></FONT>     The &quot;average case&quot; is often roughly as bad as the worst case. Suppose that we randomly choose <I>n</I> numbers and apply insertion sort. How long does it take to determine where in subarray <I>A</I>[1. . <I>j </I>- 1] to insert element <I>A</I>[<I>j</I>]? On average, half the elements in <I>A</I>[1. . <I>j</I> - 1] are less than <I>A</I>[<I>j</I>], and half the elements are greater. On average, therefore, we check half of the subarray <I>A</I>[1. . <I>j</I> - 1], so <I>t<SUB>j</I></SUB> = <I>j</I>/2. If we work out the resulting average-case running time, it turns out to be a quadratic function of the input size, just like the worst-case running time.<P>
<a name="06d9_1150"><a name="06d9_1151"><a name="06d9_1152"><a name="06d9_1153">In some particular cases, we shall be interested in the <I><B>average-case</I></B> or <I><B>expected</I></B> running time of an algorithm. One problem with performing an average-case analysis, however, is that it may not be apparent what constitutes an &quot;average&quot; input for a particular problem. Often, we shall assume that all inputs of a given size are equally likely. In practice, this assumption may be violated, but a randomized algorithm can sometimes force it to hold.<P>
<P>







<h2>Order of growth</h2><P>
We have used some simplifying abstractions to ease our analysis of the <FONT FACE="Courier New" SIZE=2>INSERTION</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT> procedure. First, we ignored the actual cost of each statement, using the constants<I> c</I><SUB>i</SUB> to represent these costs. Then, we observed that even these constants give us more detail than we really need: the worst-case running time is <I>an</I><SUP>2</SUP> + <I>bn</I> + <I>c</I> for some constants <I>a, b,</I> and <I>c</I> that depend on the statement costs <I>c<SUB>i</I></SUB>. We thus ignored not only the actual statement costs, but also the abstract costs <I>c<SUB>i</SUB>.</I><P>
We shall now make one more simplifying abstraction. It is the<I> <B>rate of growth</I>,</B> or <I><B>order of growth,</I></B><I> </I>of the running time that really interests us. We therefore consider only the leading term of a formula (e.g., <I>an</I><SUP>2</SUP>), since the lower-order terms are relatively insignificant for large <I>n</I>. We also ignore the leading term's constant coefficient, since constant factors are less significant than the rate of growth in determining computational efficiency for large inputs. Thus, we write that insertion sort, for example, has a worst-case running time of <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP><I>) (</I>pronounced &quot;theta of <I>n-</I>squared&quot;<I>). </I>We<I> </I>shall use <img src="../images/bound.gif">-notation informally in this chapter; it will be defined precisely<I> </I>in Chapter 2<I>.</I><P>
We usually consider one algorithm to be more efficient than another if its worst-case running time has a lower order of growth. This evaluation may be in error for small inputs, but for large enough inputs a <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>) algorithm, for example, will run more quickly in the worst case than a <img src="../images/bound.gif">(<I>n</I><SUP>3</SUP>) algorithm.<P>
<P>







<h2><a name="06db_115d">Exercises<a name="06db_115d"></h2><P>
<a name="06db_115e">1.2-1<a name="06db_115e"><P>
<a name="06db_1154"><a name="06db_1155">Consider sorting <I>n</I> numbers stored in array <I>A</I> by first finding the smallest element of <I>A</I> and putting it in the first entry of another array <I>B</I>. Then find the second smallest element of <I>A</I> and put it in the second entry of <I>B.</I> Continue in this manner for the <I>n</I> elements of <I>A.</I> Write pseudocode for this algorithm, which is known as <I><B>selection sort</I></B>. Give the best-case and worst-case running times of selection sort in <img src="../images/bound.gif">-notation. <P>
<a name="06db_115f">1.2-2<a name="06db_115f"><P>
<a name="06db_1156"><a name="06db_1157"><a name="06db_1158">Consider linear search again (see Exercise 1.1-3). How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in <img src="../images/bound.gif">-notation? Justify your answers.<P>
<a name="06db_1160">1.2-3<a name="06db_1160"><P>
Consider the problem of determining whether an arbitrary sequence <img src="../images/lftwdchv.gif"><I>x</I><SUB>1</SUB>, <I>x</I><SUB>2</SUB>, . . . , <I>x<SUB>n</I></SUB><img src="../images/wdrtchv.gif"> of <I>n</I> numbers contains repeated occurrences of some number. Show that this can be done in <img src="../images/bound.gif">(<I>n l</I>g <I>n</I>) time, where lg <I>n</I> stands for log<SUB>2</SUB> <I>n</I>.<P>
<a name="06db_1161">1.2-4<a name="06db_1161"><P>
<a name="06db_1159"><a name="06db_115a"><a name="06db_115b">Consider the problem of evaluating a polynomial at a point. Given <I>n </I>coefficients <I>a</I><SUB>0</SUB>, <I>a</I><SUB>1</SUB>, . . . , <I>a<SUB>n</I> </SUB>- 1 and a real number <I>x</I>, we wish to compute <img src="11_a.gif">. Describe a straightforward <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>)-time algorithm for this problem. Describe a <img src="../images/bound.gif">(<I>n</I>)-time algorithm that uses the following method (called Horner's rule) for rewriting the polynomial:<P>
<img src="11_b.gif"><P>
<a name="06db_1162">1.2-5<a name="06db_1162"><P>