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.
我的内容管理
收起
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助 
评论7