算法設計與分析基礎（第2版）（簡體書）

本書采用了一種算法設計技術的新分類方法，不但比傳統分類法包容性更強，而且更直觀，也更有效，因此廣受好評。 這種分類框架條理清晰，契合教育學原理，非常適合算法教學。網上提供了詳盡的教學指南供教師和學生下載，書中還為學生安排了習題提示和每章小結。為了提高學習興趣，書中應用了許多流行的謎題和游戲，需要重點思考的地方則往往會用反問來提醒注意。

(美) Anany Levitin是Villanova大學計算科學系的教授。他的論文A New Road Map of Algorithm Design Techniques：Picking Up Where the Traditi。onal Classification Leaves Off(《算法設計技術新途徑：彌補傳統分類法的缺·感》)受到業內人士極高的評價。在SIGCSE會議上，作者做過多次關于算法教學的演講。

Preface 1 Introduction 1.1 What is an Algorithm? Exercises 1.1 1.2 Fundamentals of Algorithmic Problem Solving Understanding the Problem Ascertaining the Capabilities of a Computational Device Choosing between Exact and Approximate Problem Solving Deciding on Appropriate Data Structures Algorithm Design Techniques Methods of Specifying an Algorithm Proving an Algorithm's Correctness Analyzing an Algorithm Coding an Algorithm Exercises 1.2 1.3 Important Problem Types Sorting Searching String Processing Graph Problems Combinatorial Problems Geometric Problems Numerical Problems Exercises 1.3 1.4 Fundamental Data Structures Linear Data Structures Graphs Trees Sets and Dictionaries Exercises 1.4 Summary 2 Fundamentals of the Analysis of Algorithm Efficiency 2.1 Analysis Framework Measuring an Input's Size Units for Measuring Running -[]me Orders of Growth Worst-Case, Best-Case, and Average-Case Efficlencies Recapitulation of the Analysis Framework Exercises 2.1 2.2 Asymptotic Notations and Basic Efficiency Classes Informal Introduction O-notation 9-notation Onotation Useful Property Involving the Asymptotic Notations Using Limits for Comparing Orders of Growth Basic Efficiency Classes Exercises 2.2 2.3 Mathematical Analysis of Nonrecursive Algorithms Exercises 2.3 2.4 Mathematical Analysis of Recursive Algorithms Exercises 2.4 2.5 Example: Fibonacci Numbers Explicit Formula for the nth Fibonacci Number Algorithms for Computing Fibonacci Numbers Exercises 2.5 3 Brute Force 4 Divide-and-Conquer 5 Decrease-and-Conquer 6 Transform-and-Conquer 7 Space and lime Tradeoffs 8 Dynamic Programming 9 Greedy Technique 10 Iterative Improvement 11 Limitations of Algorithm Power 12 Coping with the Limitations of Algorithm Power Epilogue APPENDIX A Useful Formulas for the Analysis of Algorithms APPENDIX B Short Tutorial on Recurrence Relations Bibliography Hints to Exercises Index