第1章 基础

The objective of this book is to study a broad variety of important and usefulalgorithms—methods for solving problems that are suited for computer implementation.Algorithms go hand in hand with data structures—schemes for organizingdata that leave them amenable to effi cient processing by an algorithm. Thischapter introduces the basic tools that we need to study algorithms and data structures.

First, we introduce our basic programming model. All of our programs are implementedusing a small subset of the Java programming language plus a few of our ownlibraries for input/output and for statistical calculations. Section 1.1 is a summary oflanguage constructs, features, and libraries that we use in this book.

Next, we emphasize data abstraction, where we defi ne abstract data types (ADTs) inthe service of modular programming. In Section 1.2 we introduce the process of implementingan ADT in Java, by specifying an applications programming interface (API)and then using the Java class mechanism to develop an implementation for use in clientcode.

As important and useful examples, we next consider three fundamental ADTs: thebag, the queue, and the stack. Section 1.3 describes APIs and implementations of bags,queues, and stacks using arrays, resizing arrays, and linked lists that serve as models andstarting points for algorithm implementations throughout the book.

Performance is a central consideration in the study of algorithms. Section 1.4 describesour approach to analyzing algorithm performance. The basis of our approach isthe scientifi c method: we develop hypotheses about performance, create mathematicalmodels, and run experiments to test them, repeating the process as necessary.We conclude with a case study where we consider solutions to a connectivity problemthat uses algorithms and data structures that implement the classic union-fi nd ADT.

Algorithms When we write a computer program, we are generally implementing amethod that has been devised previously to solve some problem. This method is oftenindependent of the particular programming language being used—it is likely to beequally appropriate for many computers and many programming languages. It is themethod, rather than the computer program itself, that specifi es the steps that we cantake to solve the problem. The term algorithm is used in computer science to describea fi nite, deterministic, and effective problem-solving method suitable for implementationas a computer program. Algorithms are the stuff of computer science: they arecentral objects of study in the fi eld.

We can defi ne an algorithm by describing a procedure for solving a problem in anatural language, or by writing a computer program that implements the procedure,as shown at right for Euclid’s algorithm for fi nding the greatest common divisor oftwo numbers, a variant of which was devisedover 2,300 years ago. If you are not familiarwith Euclid’s algorithm, you are encouragedto work Exercise 1.1.24 and Exercise1.1.25, perhaps after reading Section 1.1. Inthis book, we use computer programs to describealgorithms. One important reason fordoing so is that it makes easier the task ofchecking whether they are fi nite, deterministic,and effective, as required. But it is alsoimportant to recognize that a program in aparticular language is just one way to expressan algorithm. The fact that many of the algorithmsin this book have been expressedin multiple programming languages over thepast several decades reinforces the idea that each algorithm is a method suitable forimplementation on any computer in any programming language.

Most algorithms of interest involve organizing the data involved in the computation.Such organization leads to data structures, which also are central objects of studyin computer science. Algorithms and data structures go hand in hand. In this book wetake the view that data structures exist as the byproducts or end products of algorithmsand that we must therefore study them in order to understand the algorithms. Simplealgorithms can give rise to complicated data structures and, conversely, complicatedalgorithms can use simple data structures. We shall study the properties of many datastructures in this book; indeed, we might well have titled the book Algorithms and DataStructures.

enter image description here

When we use a computer to help us solve a problem, we typically are faced with anumber of possible approaches. For small problems, it hardly matters which approachwe use, as long as we have one that correctly solves the problem. For huge problems (orapplications where we need to solve huge numbers of small problems), however, wequickly become motivated to devise methods that use time and space effi ciently.

The primary reason to learn about algorithms is that this discipline gives us thepotential to reap huge savings, even to the point of enabling us to do tasks that wouldotherwise be impossible. In an application where we are processing millions of objects,it is not unusual to be able to make a program millions of times faster by using a welldesignedalgorithm. We shall see such examples on numerous occasions throughoutthe book. By contrast, investing additional money or time to buy and install a newcomputer holds the potential for speeding up a program by perhaps a factor of only 10or 100. Careful algorithm design is an extremely effective part of the process of solvinga huge problem, whatever the applications area.

When developing a huge or complex computer program, a great deal of effort mustgo into understanding and defi ning the problem to be solved, managing its complexity,and decomposing it into smaller subtasks that can be implemented easily. Often,many of the algorithms required after the decomposition are trivial to implement. Inmost cases, however, there are a few algorithms whose choice is critical because mostof the system resources will be spent running those algorithms. These are the types ofalgorithms on which we concentrate in this book. We study fundamental algorithmsthat are useful for solving challenging problems in a broad variety of applications areas.

The sharing of programs in computer systems is becoming more widespread, soalthough we might expect to be using a large fraction of the algorithms in this book, wealso might expect to have to implement only a small fraction of them. For example, theJava libraries contain implementations of a host of fundamental algorithms. However,implementing simple versions of basic algorithms helps us to understand them betterand thus to more effectively use and tune advanced versions from a library. Moreimportant, the opportunity to reimplement basic algorithms arises frequently. The primaryreason to do so is that we are faced, all too often, with completely new computingenvironments (hardware and software) with new features that old implementationsmay not use to best advantage. In this book, we concentrate on the simplest reasonableimplementations of the best algorithms. We do pay careful attention to coding the criticalparts of the algorithms, and take pains to note where low-level optimization effortcould be most benefi cial.

The choice of the best algorithm for a particular task can be a complicated process,perhaps involving sophisticated mathematical analysis. The branch of computer sciencethat comprises the study of such questions is called analysis of algorithms. Many of the algorithms that we study have been shown through analysis to have excellenttheoretical performance; others are simply known to work well through experience.Our primary goal is to learn reasonable algorithms for important tasks, yet we shall alsopay careful attention to comparative performance of the methods. We should not usean algorithm without having an idea of what resources it might consume, so we striveto be aware of how our algorithms might be expected to perform.

Summary of topics  As an overview, we describe the major parts of the book, givingspecifi c topics covered and an indication of our general orientation toward thematerial. This set of topics is intended to touch on as many fundamental algorithms aspossible. Some of the areas covered are core computer-science areas that we study indepth to learn basic algorithms of wide applicability. Other algorithms that we discussare from advanced fi elds of study within computer science and related fi elds. The algorithmsthat we consider are the products of decades of research and development andcontinue to play an essential role in the ever-expanding applications of computation.

Fundamentals (Chapter 1) in the context of this book are the basic principles andmethodology that we use to implement, analyze, and compare algorithms. We considerour Java programming model, data abstraction, basic data structures, abstract datatypes for collections, methods of analyzing algorithm performance, and a case study.

Sorting algorithms (Chapter 2) for rearranging arrays in order are of fundamentalimportance. We consider a variety of algorithms in considerable depth, including insertionsort, selection sort, shellsort, quicksort, mergesort, and heapsort. We also encounteralgorithms for several related problems, including priority queues, selection,and merging. Many of these algorithms will fi nd application as the basis for other algorithmslater in the book.

Searching algorithms (Chapter 3) for fi nding specifi c items among large collectionsof items are also of fundamental importance. We discuss basic and advanced methodsfor searching, including binary search trees, balanced search trees, and hashing. Wenote relationships among these methods and compare performance.

Graphs (Chapter 4) are sets of objects and connections, possibly with weights andorientation. Graphs are useful models for a vast number of diffi cult and importantproblems, and the design of algorithms for processing graphs is a major fi eld of study.We consider depth-fi rst search, breadth-fi rst search, connectivity problems, and severalalgorithms and applications, including Kruskal’s and Prim’s algorithms for fi ndingminimum spanning tree and Dijkstra’s and the Bellman-Ford algorithms for solvingshortest-paths problems.

Strings (Chapter 5) are an essential data type in modern computing applications.We consider a range of methods for processing sequences of characters. We begin withfaster algorithms for sorting and searching when keys are strings. Then we considersubstring search, regular expression pattern matching, and data-compression algorithms.Again, an introduction to advanced topics is given through treatment of someelementary problems that are important in their own right.

Context (Chapter 6) helps us relate the material in the book to several other advancedfi elds of study, including scientifi c computing, operations research, and the theory ofcomputing. We survey event-based simulation, B-trees, suffi x arrays, maximum fl ow,and other advanced topics from an introductory viewpoint to develop appreciation forthe interesting advanced fi elds of study where algorithms play a critical role. Finally, wedescribe search problems, reduction, and NP-completeness to introduce the theoreticalunderpinnings of the study of algorithms and relationships to material in this book.

THE STUDY OF ALGORITHMS IS INTERESTING AND EXCITING because it is a new fi eld(almost all the algorithms that we study are less than 50 years old, and some were justrecently discovered) with a rich tradition (a few algorithms have been known for hundredsof years). New discoveries are constantly being made, but few algorithms arecompletely understood. In this book we shall consider intricate, complicated, and diffi -cult algorithms as well as elegant, simple, and easy ones. Our challenge is to understandthe former and to appreciate the latter in the context of scientifi c and commercial applications.In doing so, we shall explore a variety of useful tools and develop a style ofalgorithmic thinking that will serve us well in computational challenges to come.

目录