📄 chap01.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 1: INTRODUCTION</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="parti.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="preface.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="06d1_0001">CHAPTER 1: INTRODUCTION<a name="06d1_0001"></h1><P>
This chapter will familiarize you with the framework we shall use throughout the book to think about the design and analysis of algorithms. It is self-contained, but it does include several references to material that will be introduced in Part I.<P>
We begin with a discussion of computational problems in general and of the algorithms needed to solve them, with the problem of sorting as our running example. We introduce a "pseudocode" that should be familiar to readers who have done computer programming to show how we shall specify our algorithms. Insertion sort, a simple sorting algorithm, serves as an initial example. We analyze the running time of insertion sort, introducing a notation that focuses on how that time increases with the number of items to be sorted. We also introduce the divide-and-conquer approach to the design of algorithms and use it to develop an algorithm called merge sort. We end with a comparison of the two sorting algorithms.<P>
<h1><a name="06d3_1129">1.1 Algorithms<a name="06d3_1129"></h1><P>
<a name="06d3_111d"><a name="06d3_111e"><a name="06d3_111f">Informally, an <I><B>algorithm</I></B> is any well-defined computational procedure that takes some value, or set of values, as <I><B>input</I></B><I> </I>and produces some value, or set of values, as <I><B>output</I></B>. An algorithm is thus a sequence of computational steps that transform the input into the output.<P>
<a name="06d3_1120"><a name="06d3_1121">We can also view an algorithm as a tool for solving a well-specified <I><B>computational problem</I></B>. The statement of the problem specifies in general terms the desired input/output relationship. The algorithm describes a specific computational procedure for achieving that input/output relationship.<P>
We begin our study of algorithms with the problem of sorting a sequence of numbers into nondecreasing order. This problem arises frequently in practice and provides fertile ground for introducing many standard design techniques and analysis tools. Here is how we formally define the <I><B>sorting problem</I>:</B><P>
<B>Input:</B> A sequence of <I>n</I> numbers <img src="../images/lftwdchv.gif"><I>a</I><SUB>1</SUB><I>, a</I><SUB>2</SUB><I>, . . . , a<SUB>n</I></SUB><img src="../images/wdrtchv.gif"><I>.</I><P>
<B>Output:</B><I> </I>A permutation (reordering) <img src="2_a.gif">of the input sequence such that <img src="2_b.gif">.<P>
<a name="06d3_1122"><a name="06d3_1123"><a name="06d3_1124">Given an input sequence such as <img src="../images/lftwdchv.gif">31, 41, 59, 26, 41, 58<img src="../images/wdrtchv.gif">, a sorting algorithm returns as output the sequence <img src="../images/lftwdchv.gif">26, 31, 41, 41, 58, 59<img src="../images/wdrtchv.gif">. Such an input sequence is called an <I><B>instance</I></B> of the sorting problem. In general, an <I><B>instance of a problem</I></B> consists of all the inputs (satisfying whatever constraints are imposed in the problem statement) needed to compute a solution to the problem.<P>
Sorting is a fundamental operation in computer science (many programs use it as an intermediate step), and as a result a large number of good sorting algorithms have been developed. Which algorithm is best for a given application depends on the number of items to be sorted, the extent to which the items are already somewhat sorted, and the kind of storage device to be used: main memory, disks, or tapes.<P>
<a name="06d3_1125"><a name="06d3_1126">An algorithm is said to be<I><B> correct</I></B> if, for every input instance, it halts with the correct output. We say that a correct algorithm <I><B>solves</I></B> the given computational problem. An incorrect algorithm might not halt at all on some input instances, or it might halt with other than the desired answer. Contrary to what one might expect, incorrect algorithms can sometimes be useful, if their error rate can be controlled. We shall see an example of this in Chapter 33 when we study algorithms for finding large prime numbers. Ordinarily, however, we shall be concerned only with correct algorithms.<P>
<a name="06d3_1127">An algorithm can be specified in English, as a computer program, or even as a hardware design. The only requirement is that the specification must provide a precise description of the computational procedure to be followed.<P>
<a name="06d3_1128">In this book, we shall typically describe algorithms as programs written in a <I><B>pseudocode</I></B> that is very much like C, Pascal, or Algol. If you have been introduced to any of these languages, you should have little trouble reading our algorithms. What separates pseudocode from "real" code is that in pseudocode, we employ whatever expressive method is most clear and concise to specify a given algorithm. Sometimes, the clearest method is English, so do not be surprised if you come across an English phrase or sentence embedded within a section of "real" code. Another difference between pseudocode and real code is that pseudocode is not typically concerned with issues of software engineering. Issues of data abstraction, modularity, and error handling are often ignored in order to convey the essence of the algorithm more concisely.<P>
<h2>Insertion sort</h2><P>
<a name="06d4_1129"><a name="06d4_112a">We start with <I><B>insertion sort</I></B>, which is an efficient algorithm for sorting a small number of elements. Insertion sort works the way many people sort a bridge or gin rummy hand. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position for a card, we compare it with each of the cards already in the hand, from right to left, as illustrated in Figure 1.1.<P>
<img src="3_a.gif"><P>
<h4><a name="06d4_112d">Figure 1.1 Sorting a hand of cards using insertion sort.<a name="06d4_112d"></sub></sup></h4><P>
<a name="06d4_112b"><a name="06d4_112c">Our pseudocode for insertion sort is presented as a procedure called <FONT FACE="Courier New" SIZE=2>INSERTION</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT>, which takes as a parameter an array <I>A</I>[1 . . <I>n</I>] containing a sequence of length <I>n</I> that is to be sorted. (In the code, the number <I>n </I>of elements in <I>A</I> is denoted by <I>length</I>[<I>A</I>].) The input numbers are <I><B>sorted in place</I></B>: the numbers are rearranged within the array <I>A</I>, with at most a constant number of them stored outside the array at any time. The input array <I>A</I> contains the sorted output sequence when <FONT FACE="Courier New" SIZE=2>INSERTION</FONT>-S<FONT FACE="Courier New" SIZE=2>ORT </FONT>is finished.<P>
<pre>INSERTION-SORT (<I>A</I>)</sub></sup></pre><P>
<pre>1 <B>for</B> <I>j </I><img src="../images/arrlt12.gif"> 2 <B>to</B> <I>length</I>[<I>A</I>]</sub></sup></pre><P>
<pre>2 <B>do</B> <I>key </I><img src="../images/arrlt12.gif"><I> A</I>[<I>j</I>]</sub></sup></pre><P>
<pre>3 <img src="3_b.gif"> Insert <I>A</I>[<I>j</I>] into the sorted sequence <I>A</I>[1 . . <I>j</I> - 1].</sub></sup></pre><P>
<pre>4 <I>i</I> <img src="../images/arrlt12.gif"> <I>j</I> - 1</sub></sup></pre><P>
<pre>5 <B>while</B> <I>i > </I>0 and<I> A</I>[<I>i</I>]<I> </I>><I> key</I></sub></sup></pre><P>
<pre><I>6 <B>do</I></B><I> A</I>[<I>i</I> + 1] <img src="../images/arrlt12.gif"> <I>A</I>[<I>i</I>]</sub></sup></pre><P>
<pre>7 <I>i </I><img src="../images/arrlt12.gif"><I> i</I> - 1</sub></sup></pre><P>
<pre>8 <I>A</I>[<I>i</I> + 1] <img src="../images/arrlt12.gif"> <I>key</I></sub></sup></pre><P>
Figure 1.2 shows how this algorithm works for <I>A</I> = <img src="../images/lftwdchv.gif">5, 2, 4, 6, 1, 3<img src="../images/wdrtchv.gif">. The index <I>j</I> indicates the "current card" being inserted into the hand. Array elements <I>A</I>[1.. <I>j</I> - 1] constitute the currently sorted hand, and elements <I>A</I>[<I>j</I> + 1 . . <I>n</I>] correspond to the pile of cards still on the table. The index <I>j </I>moves left to right through the array. At each iteration of the "outer" <B>for </B>loop, the element <I>A</I>[<I>j</I>] is picked out of the array (line 2). Then, starting in position <I>j</I> - 1, elements are successively moved one position to the right until the proper position for <I>A</I>[<I>j</I>] is found (lines 4-7), at which point it is inserted (line 8).<P>
<img src="4_a.gif"><P>
<h4><a name="06d4_112e">Figure 1.2 The operation of <FONT FACE="Courier New" SIZE=2>INSERTION<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>SORT<FONT FACE="Times New Roman" SIZE=2> on the array A = <img src="../images/lftwdchv.gif">5, 2, 4, 6, 1, 3<img src="../images/wdrtchv.gif">. The position of index j is indicated by a circle.<a name="06d4_112e"></FONT></FONT></FONT></FONT></h4><P>
<P>
<h2>Pseudocode conventions</h2><P>
<a name="06d5_112d">We use the following conventions in our pseudocode.<P>
<a name="06d5_112e"><a name="06d5_112f">1. Indentation indicates block structure. For example, the body of the <B>for</B> loop that begins on line 1 consists of lines 2-8, and the body of the <B>while</B> loop that begins on line 5 contains lines 6-7 but not line 8. Our indentation style applies to <B>if-then-else</B> statements as well. Using indentation instead of conventional indicators of block structure, such as <B>begin</B> and <B>end</B> statements, greatly reduces clutter while preserving, or even enhancing, clarity.<SUP>1</sup><P>
<SUP>1</SUP> In real programming languages, it is generally not advisable to use indentation alone to indicate block structure, since levels of indentation are hard to determine when code is split across pages.<P>
<a name="06d5_1130">2. The looping constructs <B>while, for</B>, and <B>repeat</B> and the conditional constructs <B>if</B>, <B>then</B>, and <B>else</B> have the the same interpretation as in Pascal.<P>
<a name="06d5_1131"><a name="06d5_1132">3. The symbol <img src="4_b.gif"> indicates that the remainder of the line is a comment. <P>
<a name="06d5_1133"><a name="06d5_1134">4. A multiple assignment of the form <I>i </I><img src="../images/arrlt12.gif"><I> j </I><img src="../images/arrlt12.gif"><I> e</I> assigns to both variables <I>i </I>and<I> j</I> the value of expression <I>e</I>; it should be treated as equivalent to the assignment <I>j </I><img src="../images/arrlt12.gif"><I> e</I> followed by the assignment <I>i </I><img src="../images/arrlt12.gif"><I> j</I>.<P>
<a name="06d5_1135"><a name="06d5_1136"><a name="06d5_1137">5. Variables (such as <I>i, j</I>, and <I>key</I>) are local to the given procedure. We shall not use global variables without explicit indication.<P>
<a name="06d5_1138">6. Array elements are accessed by specifying the array name followed by the index in square brackets. For example, <I>A</I>[<I>i</I>] indicates the <I>i</I>th element of the array<I> A</I>. The notation ". ." is used to indicate a range of values within an array. Thus, <I>A</I>[1<I>. . j</I>] indicates the subarray of <I>A</I> consisting of elements <I>A</I>[1], <I>A</I>[2], . . . , <I>A</I>[<I>j</I>].<P>
<a name="06d5_1139"><a name="06d5_113a"><a name="06d5_113b">7. Compound data are typically organized into <I><B>objects</I></B>, which are comprised of <I><B>attributes</I></B> or <I><B>fields</I></B>. A particular field is accessed using the field name followed by the name of its object in square brackets. For example, we treat an array as an object with the attribute <I>length</I> indicating how many elements it contains. To specify the number of elements in an array <I>A</I>, we write <I>length</I>[<I>A</I>]. Although we use square brackets for both array indexing and object attributes, it will usually be clear from the context which interpretation is intended.<P>
<a name="06d5_113c">A variable representing an array or object is treated as a pointer to the data representing the array or object. For all fields <I>f</I> of an object <I>x</I>, setting <I>y </I><img src="../images/arrlt12.gif"><I> x</I> causes <I>f</I>[<I>y</I>]<I> = f</I>[<I>x</I>]. Moreover, if we now set <I>f</I>[<I>x</I>] <img src="../images/arrlt12.gif"> 3, then afterward not only is <I>f</I>[<I>x</I>] = 3, but <I>f</I>[<I>y</I>] = 3 as well. In other words, <I>x</I> and <I>y</I> point to ("are") the same object after the assignment <I>y </I><img src="../images/arrlt12.gif"> x<I>.</I><P>
<a name="06d5_113d">Sometimes, a pointer will refer to no object at all. In this case, we give it the special value <FONT FACE="Times New Roman" SIZE=1>NIL</FONT>.<P>
<a name="06d5_113e"><a name="06d5_113f">8. Parameters are passed to a procedure <I><B>by value</I></B>: the called procedure receives its own copy of the parameters, and if it assigns a value to a parameter, the change is <I>not</I> seen by the calling routine. When objects are passed, the pointer to the data representing the object is copied, but the object's fields are not. For example, if <I>x</I> is a parameter of a called procedure, the assignment <I>x </I><img src="../images/arrlt12.gif"><I> y</I> within the called procedure is not visible to the calling procedure. The assignment <I>f</I>[<I>x</I>] <img src="../images/arrlt12.gif"> 3, however, is visible.<P>
<P>
<h2><a name="06d6_1144">Exercises<a name="06d6_1144"></h2><P>
<a name="06d6_1145">1.1-1<a name="06d6_1145"><P>
Using Figure 1.2 as a model, illustrate the operation of <FONT FACE="Courier New" SIZE=2>INSERTION</FONT>-<FONT FACE="Courier New" SIZE=2>SORT </FONT>on the array <I>A</I> = <img src="../images/lftwdchv.gif">31, 41, 59, 26, 41, 58<img src="../images/wdrtchv.gif">.<P>
<a name="06d6_1146">1.1-2<a name="06d6_1146"><P>
Rewrite the <FONT FACE="Courier New" SIZE=2>INSERTION</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT> procedure to sort into nonincreasing instead of nondecreasing order.<P>
<a name="06d6_1147">1.1-3<a name="06d6_1147"><P>
<a name="06d6_1140"><a name="06d6_1141"><a name="06d6_1142">Consider the <I><B>searching problem:</I></B><P>
<B>Input:</B> A sequence of <I>n</I> numbers <I>A</I> = <img src="../images/lftwdchv.gif"><I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . ,<I>a</I><SUB>n</SUB><img src="../images/wdrtchv.gif"> and a value <I>v</I>.<P>
<B>Output:</B> An index <I>i</I> such that <I>v = A</I>[<I>i</I>] or the special value <FONT FACE="Times New Roman" SIZE=1>NIL</FONT> if <I>v</I> does not appear in <I>A</I>.<P>
Write pseudocode for <I><B>linear search</I></B>, which scans through the sequence, looking for <I>v</I>.<P>
<a name="06d6_1148">1.1-4<a name="06d6_1148"><P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -