算法技术手册(英文影印版)AlgorithmsinaNutshell_in去重算法的思路

5星 · 超过95%的资源需积分: 10 131 浏览量更新于2023-03-03 评论 3 收藏 11.46MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

Table of Contents

Preface........................................................................................................ 2

Part I: I....................................................................................................... 9

Chapter 1. Algorithms Matter....................................................................................................................................................... 10

Section 1.1. Understand the Problem......................................................................................................................................... 11

Section 1.2. Experiment if Necessary........................................................................................................................................ 12

Section 1.3. Side Story................................................................................................................................................................ 16

Section 1.4. The Moral of the Story............................................................................................................................................ 17

Section 1.5. References.............................................................................................................................................................. 18

Chapter 2. The Mathematics of Algorithms.................................................................................................................................. 19

Section 2.1. Size of a Problem Instance..................................................................................................................................... 19

Section 2.2. Rate of Growth of Functions.................................................................................................................................. 21

Section 2.3. Analysis in the Best, Average, and Worst Cases................................................................................................... 25

Section 2.4. Performance Families........................................................................................................................................... 29

Section 2.5. Mix of Operations.................................................................................................................................................. 42

Section 2.6. Benchmark Operations......................................................................................................................................... 43

Section 2.7. One Final Point...................................................................................................................................................... 45

Section 2.8. References............................................................................................................................................................. 45

Chapter 3. Patterns and Domains................................................................................................................................................. 46

Section 3.1. Patterns: A Communication Language................................................................................................................. 46

Section 3.2. Algorithm Pattern Format.................................................................................................................................... 48

Section 3.3. Pseudocode Pattern Format.................................................................................................................................. 49

Section 3.4. Design Format....................................................................................................................................................... 50

Section 3.5. Empirical Evaluation Format................................................................................................................................ 51

Section 3.6. Domains and Algorithms...................................................................................................................................... 53

Section 3.7. Floating-Point Computations................................................................................................................................ 54

Section 3.8. Manual Memory Allocation................................................................................................................................... 57

Section 3.9. Choosing a Programming Language..................................................................................................................... 60

Section 3.10. References............................................................................................................................................................ 61

Part II: II................................................................................................... 62

Chapter 4. Sorting Algorithms...................................................................................................................................................... 63

Section 4.1. Overview................................................................................................................................................................ 63

Section 4.2. Insertion Sort........................................................................................................................................................ 69

Section 4.3. Median Sort........................................................................................................................................................... 73

Section 4.4. Quicksort............................................................................................................................................................... 84

Section 4.5. Selection Sort......................................................................................................................................................... 91

Section 4.6. Heap Sort............................................................................................................................................................... 92

Section 4.7. Counting Sort......................................................................................................................................................... 97

Section 4.8. Bucket Sort............................................................................................................................................................ 99

Section 4.9. Criteria for Choosing a Sorting Algorithm.......................................................................................................... 105

Section 4.10. References.......................................................................................................................................................... 109

Chapter 5. Searching.................................................................................................................................................................... 111

Section 5.1. Overview................................................................................................................................................................ 111

Section 5.2. Sequential Search................................................................................................................................................. 112

Section 5.3. Binary Search....................................................................................................................................................... 118

Section 5.4. Hash-based Search.............................................................................................................................................. 122

Section 5.5. Binary Tree Search............................................................................................................................................... 135

Chapter 6. Graph Algorithms...................................................................................................................................................... 142

Section 6.1. Overview............................................................................................................................................................... 142

Section 6.2. Depth-First Search.............................................................................................................................................. 148

Section 6.3. Breadth-First Search............................................................................................................................................ 155

Section 6.4. Single-Source Shortest Path................................................................................................................................ 159

Section 6.5. All Pairs Shortest Path.......................................................................................................................................... 171

Section 6.6. Minimum Spanning Tree Algorithms................................................................................................................. 175

Section 6.7. References............................................................................................................................................................ 177

Chapter 7. Path Finding in AI...................................................................................................................................................... 178

Algorithms in a Nutshell

Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:

9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: miyi@CISCO.COM

Licensed by Ming Yi

Print Publication Date: 2008/10/21 User number: 594243

Section 7.1. Overview............................................................................................................................................................... 178

Section 7.2. Depth-First Search............................................................................................................................................... 187

Section 7.3. Breadth-First Search............................................................................................................................................ 196

Section 7.4. A*Search.............................................................................................................................................................. 200

Section 7.5. Comparison.......................................................................................................................................................... 210

Section 7.6. Minimax............................................................................................................................................................... 213

Section 7.7. NegMax................................................................................................................................................................ 219

Section 7.8. AlphaBeta............................................................................................................................................................ 223

Section 7.9. References........................................................................................................................................................... 230

Chapter 8. Network Flow Algorithms......................................................................................................................................... 232

Section 8.1. Overview.............................................................................................................................................................. 232

Section 8.2. Maximum Flow................................................................................................................................................... 235

Section 8.3. Bipartite Matching.............................................................................................................................................. 245

Section 8.4. Reflections on Augmenting Paths...................................................................................................................... 248

Section 8.5. Minimum Cost Flow............................................................................................................................................ 252

Section 8.6. Transshipment.................................................................................................................................................... 252

Section 8.7. Transportation..................................................................................................................................................... 253

Section 8.8. Assignment.......................................................................................................................................................... 254

Section 8.9. Linear Programming........................................................................................................................................... 255

Section 8.10. References......................................................................................................................................................... 256

Chapter 9. Computational Geometry.......................................................................................................................................... 257

Section 9.1. Overview............................................................................................................................................................... 257

Section 9.2. Convex Hull Scan................................................................................................................................................ 266

Section 9.3. LineSweep............................................................................................................................................................ 274

Section 9.4. Nearest Neighbor Queries.................................................................................................................................. 286

Section 9.5. Range Queries..................................................................................................................................................... 298

Section 9.6. References........................................................................................................................................................... 304

Part III: III.............................................................................................. 305

Chapter 10. When All Else Fails................................................................................................................................................. 306

Section 10.1. Variations on a Theme....................................................................................................................................... 306

Section 10.2. Approximation Algorithms............................................................................................................................... 307

Section 10.3. Offline Algorithms............................................................................................................................................. 307

Section 10.4. Parallel Algorithms........................................................................................................................................... 308

Section 10.5. Randomized Algorithms................................................................................................................................... 308

Section 10.6. Algorithms That Can Be Wrong, but with Diminishing Probability................................................................. 315

Section 10.7. References.......................................................................................................................................................... 318

Chapter 11. Epilogue.................................................................................................................................................................... 319

Section 11.1. Overview.............................................................................................................................................................. 319

Section 11.2. Principle: Know Your Data................................................................................................................................. 319

Section 11.3. Principle: Decompose the Problem into Smaller Problems.............................................................................. 320

Section 11.4. Principle: Choose the Right Data Structure....................................................................................................... 321

Section 11.5. Principle: Add Storage to Increase Performance.............................................................................................. 322

Section 11.6. Principle: If No Solution Is Evident, Construct a Search.................................................................................. 323

Section 11.7. Principle: If No Solution Is Evident, Reduce Your Problem to Another Problem That Has a Solution.......... 323

Section 11.8. Principle: Writing Algorithms Is Hard—Testing Algorithms Is Harder........................................................... 324

Part IV: IV............................................................................................... 326

Appendix A. Benchmarking........................................................................................................................................................ 327

Section A.1. Statistical Foundation......................................................................................................................................... 327

Section A.2. Hardware............................................................................................................................................................ 328

Section A.3. Reporting............................................................................................................................................................. 337

Section A.4. Precision.............................................................................................................................................................. 338

About the Authors................................................................................... 340

Colophon................................................................................................ 340

Algorithms in a Nutshell

Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:

9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: miyi@CISCO.COM

Licensed by Ming Yi

Print Publication Date: 2008/10/21 User number: 594243

Algorithms in a Nutshell

by George T. Heineman, Gary Pollice, and Stanley Selkow

Printed in the United States of America.

Published by O’Reilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 95472.

O’Reilly books may be purchased for educational, business, or sales promotional use. Online

editions are also available for most titles (safari.oreilly.com). For more information, contact

our corporate/institutional sales department: (800) 998-9938 or corporate@oreilly.com.

Editor:

Mary Treseler

Production Editor:

Rachel Monaghan

Production Services:

Newgen Publishing

and Data Services

Copyeditor:

Genevieve d’Entremont

Proofreader:

Rachel Monaghan

Indexer:

John Bickelhaupt

Cover Designer:

Karen Montgomery

Interior Designer:

David Futato

Illustrator:

Robert Romano

Printing History:

October 2008: First Edition.

Nutshell Handbook, the Nutshell Handbook logo, and the O’Reilly logo are registered

trademarks of O’Reilly Media, Inc. The In a Nutshell series designations, Algorithms in a

Nutshell, the image of a hermit crab, and related trade dress are trademarks of O’Reilly Media,

Inc.

Many of the designations used by manufacturers and sellers to distinguish their products are

claimed as trademarks. Where those designations appear in this book, and O’Reilly Media,

Inc. was aware of a trademark claim, the designations have been printed in caps or initial

caps.

While every precaution has been taken in the preparation of this book, the publisher and

authors assume no responsibility for errors or omissions, or for damages resulting from the

use of the information contained herein.

This book uses RepKover

™

, a durable and flexible lay-flat binding.

ISBN: 978-0-596-51624-6

[M]

Algorithms in a Nutshell Page 1 Return to Table of Contents

Algorithms in a Nutshell

Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:

9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: miyi@CISCO.COM

Licensed by Ming Yi

Print Publication Date: 2008/10/21 User number: 594243

Chapter 2

Preface

As Trinity states in the movie The Matrix:

It’s the question that drives us, Neo. It’s the question that brought you here.

You know the question, just as I did.

As authors of this book, we answer the question that has led you here:

Can I use algorithm X to solve my problem? If so, how do I implement it?

You likely do not need to understand the reasons why an algorithm is correct—if

you do, turn to other sources, such as the 1,180-page bible on algorithms, Intro-

duction to Algorithms, Second Edition, by Thomas H. Cormen et al. (2001). There

you will find lemmas, theorems, and proofs; you will find exercises and step-by-step

examples showing the algorithms as they perform. Perhaps surprisingly, however,

you will not find any real code, only fragments of “pseudocode,” the device used by

countless educational textbooks to present a high-level description of algorithms.

These educational textbooks are important within the classroom, yet they fail the

software practitioner because they assume it will be straightforward to develop real

code from pseudocode fragments.

We intend this book to be used frequently by experienced programmers looking

for appropriate solutions to their problems. Here you will find solutions to the

problems you must overcome as a programmer every day. You will learn what

decisions lead to an improved performance of key algorithms that are essential for

the success of your software applications. You will find real code that can be

adapted to your needs and solution methods that you can learn.

All algorithms are fully implemented with test suites that validate the correct

implementation of the algorithms. The code is fully documented and available as

a code repository addendum to this book. We rigorously followed a set of princi-

ples as we designed, implemented, and wrote this book. If these principles are

meaningful to you, then you will find this book useful.

Algorithms in a Nutshell Page 2 Return to Table of Contents

Algorithms in a Nutshell

Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:

9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: miyi@CISCO.COM

Licensed by Ming Yi

Print Publication Date: 2008/10/21 User number: 594243

剩余343页未读，继续阅读

MHW2006

2015-08-31

很实用的算法手册，只是鄙人英文水平有限，看起来有点儿费劲

大师兄技术私享

粉丝: 9
资源: 18

会员权益专享

算法技术手册(英文影印版) Algorithms in a Nutshell

评论3

会员权益专享

最新资源

算法技术手册(英文影印版) Algorithms in a Nutshell

评论3

算法技术手册 Algorithms in a Nutshell Second Edition 英文版

Algorithms in a Nutshell 算法技术手册 英文版

Algorithms in a Nutshell

C#数据结构与算法书籍推荐

算法 algorithms(中文第4版)

python算法数据结构书籍

algorithms in c++pdf

数据结构和算法的推荐书籍和视频

data structures and algorithms in python

数据结构与算法初级阶段书籍推荐

使用python去检测不安全加密算法

数据结构与算法推荐课程

data structure and algorithms in java 6th pdf

data structures and algorithms in java 2nd 编程作业

Whether from a visual or quantitative perspective,our NWCTV-WTTV method surpasses other comparative algorithms in abdominal image restoration.这个有语法错误吗？

c++数据结构与算法推荐书籍

introduction to algorithms 3rd

会员权益专享

最新资源

Algorithms in a Nutshell 算法技术手册英文版