算法技术手册(英文影印版)

.algorithm pattern format
pseudocode pattern format
design format
empirical evaluation format
domains and algorithms
floating-point computations
manual memory allocation
choosing a programming language
references
part ii.
4. sorting algorithms
overview
insertion sort
median sort
quicksort
selection sort
heap sort
counting sort
bucket sort
criteria for choosing a sorting algorithm
references
5. searching
overview
sequential search
binary search
hash-based search
binary tree search ..
6. graph algorithms
overview
depth-first search
breadth-first search
single-source shortest path
all pairs shortest path
minimum spanning tree algorithms
references
7. path finding in ai
overview
depth-first search
breadth-first search
a*search
comparison
minimax
negmax
alphabeta
references
8. network flow algorithms
overview
maximum flow
bipartite matching
reflections on augmenting paths
minimum cost flow
transshipment
transportation
assignment
linear programming
references
9. computational geometry
overview
convex hull scan
linesweep
nearest neighbor queries
range queries
references
part iii.
10. when all else fails
variations on a theme
approximation algorithms
offline algorithms
parallel algorithms
randomized algorithms
algorithms that can be wrong, but with diminishing probability
references
11. epilogue
overview
principle: know your data
principle: decompose the problem into smaller problems
principle: choose the right data structure
principle: add storage to increase performance
principle: if no solution is evident, construct a search
principle: if no solution is evident, reduce your problem to another problem that has a solution
principle: writing algorithms is hard—testing algorithms is harder
part iv.
appendix: benchmarking
index ...

.　　We mathematically analyze the performance of each algorithm in this book to help programmers understand the conditions under which each algorithm performs at its best. We provide live code examples, and in the accompanying code repository there are numerous JUnk (http://sourceforge.net/projects/junit) test cases to document the proper implementation of each algorithm. We generate benchmark performance data to provide empirical evidence regarding the performance of each algorithm.
　　We classify each algorithm into a specific performance family and provide benchmark data showing the execution performance to support the analysis. We avoid algorithms that are interesting only to the mathematical algorithmic designer trying to prove that an approach performs better at the expense of being impossible to implement. We execute our algorithms on a variety of programming platforms to demonstrate that the design of the algorithm--not the underlying platform--is the driving factor in efficiency.
　　The appendix contains the full details of our approach toward benchmarking, and can be used to independently validate the performance results we describe in this book. The advice we give you is common in the open source community: "Your mileage may vary." Although you won't be able to duplicate our results exactly, you will be able to verify the trends that we document, and we encourage you to use the same empirical approach when deciding upon algorithms for your own use.
　　Audience
　　If you were trapped on a desert island and could have only one algorithms book, we recommend the complete box set of The Art of Computer Programming, Volumes 1-3, by Donald Knuth (1998). Knuth describes numerous data structures and algorithms and provides exquisite treatment and analysis. Complete with historical footnotes and exercises, these books could keep a programmer active and content for decades. It would certainly be challenging, however, to put directly into practice the ideas from Knuth's book.
　　But you are not trapped on a desert island, are you? No, you have sluggish code that must be improved by Friday and you need to understand how to do it!
　　We intend our book to be your primary reference when you are faced with an algorithmic question and need to either (a) solve a particular problem, or (b) improve on the performance of an existing solution. We cover a range of existing algorithms for solving a large number of problems and adhere to the following principles:
　　When describing each algorithm, we use a stylized pattern to properly frame each discussion and explain the essential points of the algorithm. By using patterns, we create a readable book whose consistent presentation shows the impact that similar design decisions have on different algorithms.
　　We use a variety of languages to describe the algorithms in the book (including C, C++, Java, and Ruby). In doing so, we make concrete the discussion on algorithms and speak using languages that you are already familiar with.
　　We describe the expected performance of each algorithm and empirically provide evidence that supports these claims. Whether you trust in mathematics or in demonstrable execution times, you will be persuaded. ..
　　We intend this book to be most useful to software practitioners, programmers, and designers. To meet your objectives, you need access to a quality resource that explains real solutions to real algorithms that you need to solve real problems.
　　You already know how' to program in a variety of programming languages. You know about the essential computer science data structures, such as arrays, linked lists, stacks, queues, hash tables, binary trees, and undirected and directed graphs. You don't need to implement these data structures, since they are typically provided by code libraries.
　　We expect that you will use this book to learn about tried and tested solutions to solve problems efficiently. You will learn some advanced data structures and some novel ways to apply standard data structures to improve the efficiency of algorithms. Your problem-solving abilities will improve when you see the key decisions for each algorithm that make for efficient solutions.
　　Contents of This Book
　　This book is divided into three parts. Part I (Chapters 1-3) provides the mathematical introduction to algorithms necessary to properly understand the descriptions used in this book. We also describe the pattern-based style used throughout in the presentation of each algorithm. This style is carefully designed to ensure consistency, as well as to highlight the essential aspects of each algorithm. Part II contains a series of chapters (4-9), each consisting of a set of related algorithms. The individual sections of these chapters are self-contained descriptions of the algorithms.
　　Part III (Chapters 10 and 11) provides resources that interested readers can use to pursue these topics further. A chapter on approaches to take when "all else fails" provides helpful hints on solving problems when there is (as yet) no immediate efficient solution. We close with a discussion of important areas of study that we omitted from Part II simply because they were too advanced, too niche-oriented, or too new to have proven themselves. In Part IV, we include a benchmarking appendix that describes the approach used throughout this book to generate empirical data that supports the mathematical analysis used in each chapter. Such benchmarking is standard in the industry yet has been noticeably lacking in textbooks describing algorithms.
　　Conventions Used in This Book
　　The following typographical conventions are used in this book:
　　Code
　　Ail code examples appear in this typecase.
　　This code is replicated directly from the code repository and reflects real code.
　　Italic
　　Indicates key terms used to describe algorithms and data structures. Also used when referring to variables within a pseudocode description of an example.
　　Constant width
　　Indicates the name of actual software elements within an implementation, such as a Java class, the name of an array within a C implementation, and constants such as true or false.
　　SMALL CAPS
　　Indicates the name of an algorithm.
　　We cite numerous books, articles, and websites throughout the book. These citations appear in text using parentheses, such as (Cormen et al., 2001), and each chapter closes with a listing of references used within that chapter. When the reference citation immediately follows the name of the author in the text, we do not duplicate the name in the reference. Thus, we refer to the Art of Computer Programming books by Donald Knuth (1998) by just including the year in parentheses.
　　All URLs used in the book were verified as of August 2008 and we tried to use only URLs that should be around for some time. We include small URLs, such as http://www. oreilly.com, directly within the text; otherwise, they appear in footnotes and within the references at the end of a chapter.
　　Using Code Examples
　　This book is here to help you get your job done. In general, you may use the code in this book in your programs and documentation. You do not need to contact us for permission unless you're reproducing a significant portion of the code. For example, writing a program that uses several chunks of code from this book does not require permission. Selling or distributing a CD-ROM of examples from O'Reilly books does require permission. Answering a question by citing this book and quoting example code does not require permission. Incorporating a significant amount of example code from this book into your product's documentation does require permission.
　　We appreciate, but do not require, attribution. An attribution usually includes the title, author, publisher, and ISBN. For example: "Algorithms in a Nutshell by George T. Heineman, Gary Pollice, and Stanley Selkow. Copyright 2009 George Heineman, Gary Pollice, and Stanley Selkow, 978-0-596-51624-6."
　　If you feel your use of code examples falls outside fair use or the permission given here, feel free to contact us at permissions@oreilly.com.
　　Comments and Questions
　　Please address comments and questions concerning this book to the publisher:
　　O'Reilly Media, Inc.
　　1005 Gravenstein Highway North
　　Sebastopol, CA 95472
　　800-998-9938 (in the United States or Canada)
　　707-829-0515 (international or local)
　　707-829-0104 (fax)
　　We have a web page for this book, where we list errata, examples, and any additional information. You can access this page at:
　　http://www.oreilly.com/catalog/9780596516246
　　To comment or ask technical questions about this book, send email to:
　　bookquestions@oreilly.com
　　For more information about our books, conferences, Resource Centers, and the O'ReiUy Network, see our website at:
　　http://www.oreilly.com
　　Safari Books Online
　　When you see a Safari Books Online icon on the cover of your favorite technology book, that means the book is available online through the O'Reilly Network Safari Bookshelf.
　　Safari offers a solution that's better than e-books. It's a virtual library that lets you easily search thousands of top tech books, cut and paste code samples, download chapters, and find quick answers when you need the most accurate, current information. Try it for free at http://safari.oreilly.com.
　　Acknowledgments
　　We would like to thank the book reviewers for their attention to detail and suggestions, which improved the presentation and removed defects from earlier drafts: Alan Davidson, Scot Drysdale, Krzysztof Duleba, Gene Hughes, Murali Mani, Jeffrey Yasskin, and Daniel Yoo.
　　George Heineman would like to thank those who helped instill in him a passion for algorithms, including Professors Scot Drysdale (Dartmouth College) and Zvi Galil (Columbia University). As always, George thanks his wife, Jennifer, and his children, Nicholas (who always wanted to know what "notes" Daddy was working on) and Alexander (who was born as we prepared the final draft of the book).
　　Gary Pollice would like to thank his wife Vikki for 40 great years. He also wants to thank the WPI computer science department for a great environment and a great job.
　　Stanley Selkow would like to thank his wife, Deb. This book was another step on their long path together.
　　References
　　Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, Second Edition. McGraw-Hill, 2001.
　　Knuth, Donald E., The Art of Computer Programming, Volumes 1-3, Boxed Set Second Edition. Addison-Wesley Professional, 1998. ...