Table of Contents
Copyright..................................................................................................... 1
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
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
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use
requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved.
5星 · 超过95%的资源 需积分: 10 111 浏览量
2010-01-23
20:53:03
上传
评论 3
收藏 11.46MB PDF 举报 
MHW20062015-08-31很实用的算法手册，只是鄙人英文水平有限，看起来有点儿费劲
donaldknuth2011-12-26很好，pdf格式，有书签，看到很舒服，内容很充实，也很有挑战性~~~
biaosonya2013-06-21谢谢了，就是分值有点多。呵呵
