算法导论：罗伯特·塞德威克与凯文·韦恩合著第四版

需积分: 9 134 浏览量更新于2024-07-18 收藏 12.2MB PDF 举报

"《算法》第四版，罗伯特·西德威克与凯文·韦恩合著，2011年，艾迪生·韦斯利出版社" 这本书是一部全面介绍当今最重要计算机算法的权威著作，旨在为已经掌握了基础编程技能和熟悉计算机系统的人群提供算法知识的概览。它被设计用作大学计算机科学第二课程的教材，适合在学生具备基本编程技能后学习。此外，该书对于进行系统开发或应用程序编程的自学者以及需要详细算法实现和性能信息的专业人士来说，也是一本宝贵的参考书。《算法》第四版涵盖了广泛的视角，使其成为进入算法领域的理想入门读物。书中不仅讲解了各种重要的算法，如排序、搜索、图论、动态规划等，还提供了这些算法的实际实现，使读者能够理解它们的工作原理并能够应用到实际问题中。同时，书中详细分析了算法的性能特征，包括时间复杂度和空间复杂度，这对于优化代码和解决实际问题至关重要。作者罗伯特·西德威克和凯文·韦恩都是普林斯顿大学的教授，他们在算法领域有着深厚的研究背景和丰富的教学经验。他们以清晰易懂的方式阐述复杂的概念，使得本书不仅适合大学课程，也适合自学。书中的每个算法都配有详细的步骤解释，有的还辅以图表和伪代码，帮助读者直观地理解算法的运行过程。此外，书中还讨论了如何选择合适的算法来解决问题，以及如何评估算法的有效性和效率。通过实际案例和问题集，读者可以练习应用所学知识，提升解决问题的能力。书中的练习题覆盖了各种难度级别，有助于巩固学习成果，并激发进一步探索的兴趣。在版权方面，出版商提醒读者注意，书中可能提及的一些制造商和销售商的产品名称可能是商标。在不影响阅读的前提下，已尽可能尊重这些商标权，但出版商不承担因错误或遗漏而产生的直接或间接损害责任。最后，出版商还提供批量购买或特殊销售的优惠，包括电子版本和/或定制版本，这为教育机构和组织提供了更灵活的选择，以便更广泛地传播和使用这本书的知识。《算法》第四版是一本深度和广度兼具的教科书，无论是对初学者还是专业人士，都能从中获益匪浅，深化对算法的理解，提高解决问题的能力。

ptg

1.1 Basic Programming Model. . . . . . . . . 8

1.2 Data Abstraction . . . . . . . . . . . . . . 64

1.3 Bags, Queues, and Stacks . . . . . . . 120

1.4 Analysis of Algorithms . . . . . . . . . 172

1.5 Case Study: Union-Find. . . . . . . . . 216

ONE

Fundamentals

ptg

A l g o r i t h m s When we write a computer program, we are generally implementing a

method that has been devised previously to solve some problem. This method is often

independent of the particular programming language being used—it is likely to be

equally appropriate for many computers and many programming languages. It is the

method, rather than the computer program itself, that speciﬁes the steps that we can

take to solve the problem. The term algorithm is used in computer science to describe

a ﬁnite, deterministic, and effective problem-solving method suitable for implementa-

tion as a computer program. Algorithms are the stuff of computer science: they are

central objects of study in the ﬁeld.

We ca n de ﬁne an al gor ithm by d esc rib ing a pro cedure fo r so lvi ng a prob lem in a

natural language, or by writing a computer program that implements the procedure,

as shown at right for Euclid’s algorithm for ﬁnding the greatest common divisor of

two numbers, a variant of which was devised

over 2,300 years ago. If you are not familiar

with Euclid’s algorithm, you are encour-

aged to work Exercise 1.1.24 and Exercise

1.1.25, perhaps after reading Section 1.1. In

this book, we use computer programs to de-

scribe algorithms. One important reason for

doing so is that it makes easier the task of

checking whether they are ﬁnite, determin-

istic, and effective, as required. But it is also

important to recognize that a program in a

particular language is just one way to express

an algorithm. The fact that many of the al-

gorithms in this book have been expressed

in multiple programming languages over the

past several decades reinforces the idea that each algorithm is a method suitable for

implementation on any computer in any programming language.

Most algorithms of interest involve organizing the data involved in the computa-

tion. Such organization leads to data structures, which also are central objects of study

in computer science. Algorithms and data structures go hand in hand. In this book we

take the view that data structures exist as the byproducts or end products of algorithms

and that we must therefore study them in order to understand the algorithms. Simple

algorithms can give rise to complicated data structures and, conversely, complicated

algorithms can use simple data structures. We shall study the properties of many data

structures in this book; indeed, we might well have titled the book Algorithms and Data

Structures.

Compute the greatest common divisor of

two nonnegative integers p and q as follows:

If q is 0, the answer is p. If not, divide p by q

and take the remainder r. The answer is the

greatest common divisor of q and r.

public static int gcd(int p, int q)

{

if (q == 0) return p;

int r = p % q;

return gcd(q, r);

}

Euclid’s algorithm

Java-language description

English-language description

4 CHAPTER 1

■

Fundamentals

ptg

When we use a computer to help us solve a problem, we typically are faced with a

number of possible approaches. For small problems, it hardly matters which approach

we use, as long as we have one that correctly solves the problem. For huge problems (or

applications where we need to solve huge numbers of small problems), however, we

quickly become motivated to devise methods that use time and space efﬁciently.

The primary reason to learn about algorithms is that this discipline gives us the

potential to reap huge savings, even to the point of enabling us to do tasks that would

otherwise 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 well-

designed algorithm. We shall see such examples on numerous occasions throughout

the book. By contrast, investing additional money or time to buy and install a new

computer holds the potential for speeding up a program by perhaps a factor of only 10

or 100. Careful algorithm design is an extremely effective part of the process of solving

a huge problem, whatever the applications area.

When developing a huge or complex computer program, a great deal of effort must

go into understanding and deﬁning the problem to be solved, managing its complex-

ity, and decomposing it into smaller subtasks that can be implemented easily. Often,

many of the algorithms required after the decomposition are trivial to implement. In

most cases, however, there are a few algorithms whose choice is critical because most

of the system resources will be spent running those algorithms. These are the types of

algorithms on which we concentrate in this book. We study fundamental algorithms

that are useful for solving challenging problems in a broad variety of applications areas.

The sharing of programs in computer systems is becoming more widespread, so

although we might expect to be using a large fraction of the algorithms in this book, we

also might expect to have to implement only a small fraction of them. For example, the

Java libraries contain implementations of a host of fundamental algorithms. However,

implementing simple versions of basic algorithms helps us to understand them bet-

ter and thus to more effectively use and tune advanced versions from a library. More

important, the opportunity to reimplement basic algorithms arises frequently. The pri-

mary reason to do so is that we are faced, all too often, with completely new computing

environments (hardware and software) with new features that old implementations

may not use to best advantage. In this book, we concentrate on the simplest reasonable

implementations of the best algorithms. We do pay careful attention to coding the criti-

cal parts of the algorithms, and take pains to note where low-level optimization effort

could be most beneﬁ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 sci-

ence that comprises the study of such questions is called analysis of algorithms. Many

5CHAPTER 1

■

Fundamentals

ptg

of the algorithms that we study have been shown through analysis to have excellent

theoretical performance; others are simply known to work well through experience.

Our primary goal is to learn reasonable algorithms for important tasks, yet we shall also

pay careful attention to comparative performance of the methods. We should not use

an algorithm without having an idea of what resources it might consume, so we strive

to 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, giv-

ing speciﬁc topics covered and an indication of our general orientation toward the

material. This set of topics is intended to touch on as many fundamental algorithms as

possible. Some of the areas covered are core computer-science areas that we study in

depth to learn basic algorithms of wide applicability. Other algorithms that we discuss

are from advanced ﬁelds of study within computer science and related ﬁelds. The algo-

rithms that we consider are the products of decades of research and development and

continue 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 and

methodology that we use to implement, analyze, and compare algorithms. We consider

our Java programming model, data abstraction, basic data structures, abstract data

types for collections, methods of analyzing algorithm performance, and a case study.

Sorting algorithms (Chapter 2) for rearranging arrays in order are of fundamental

importance. We consider a variety of algorithms in considerable depth, including in-

sertion sort, selection sort, shellsort, quicksort, mergesort, and heapsort. We also en-

counter algorithms for several related problems, including priority queues, selection,

and merging. Many of these algorithms will ﬁnd application as the basis for other algo-

rithms later in the book.

Searching algorithms (Chapter 3) for ﬁnding speciﬁc items among large collections

of items are also of fundamental importance. We discuss basic and advanced methods

for searching, including binary search trees, balanced search trees, and hashing. We

note relationships among these methods and compare performance.

Graphs (Chapter 4) are sets of objects and connections, possibly with weights and

orientation. Graphs are useful models for a vast number of difﬁcult and important

problems, and the design of algorithms for processing graphs is a major ﬁeld of study.

We con side r d epth -ﬁrs t s earch , bre adt h-ﬁr st se arch, co nnec tiv it y p ro ble ms, a nd s ev -

eral algorithms and applications, including Kruskal’s and Prim’s algorithms for ﬁnding

minimum spanning tree and Dijkstra’s and the Bellman-Ford algorithms for solving

shortest-paths problems.

6 CHAPTER 1

■

Fundamentals

剩余968页未读，继续阅读

嘎嘎嘎嘎嘎1嘎

粉丝: 20
资源: 11

算法导论：罗伯特·塞德威克与凯文·韦恩合著第四版

Algorithms_4th by Robert Sedgewick and Kevin Wayne

Algorithms (4th Edition) (英语)Robert Sedgewick (作者), Kevin Wayne (作者)

算法 第4版(中文版扫描版+英文双色版+代码+说明). Robert.Sedgewick.&.Kevin.Wayne. 谢路云 译

[AddisonWesley]Algorithms_In_Java_3rd.zip

Algorithms fourth edition part1

身份证信息管理系统.docx

数据结构哈夫曼编码实验报告.pdf

数据结构课程设计-一元多项式计算器.docx

数据结构课程设计(快速排序).docx

算法分析与设计实验报告-单源最短路径、最小生成树.doc

最新资源

算法第4版(中文版扫描版+英文双色版+代码+说明). Robert.Sedgewick.&.Kevin.Wayne. 谢路云译