《算法分析導論（第2版）（英文版）》是2015年6月電子工業出版社出版的圖書，作者是【美】Robert Sedgewick（羅伯特·塞奇威克）,Philippe Flajolet（菲利普·弗拉若萊）。
基本介紹
- 書名：算法分析導論（第2版）（英文版）
- 作者：【美】Robert Sedgewick（羅伯特·塞奇威克）,Philippe Flajolet（菲利普·弗拉若萊）
- ISBN：978-7-121-26070-4
- 頁數：588頁
- 定價：128.00元
- 出版社：電子工業出版社
- 出版時間：2015年6月
- 裝幀：平裝
- 開本：16開
內容簡介,內容提要,作者簡介,目錄,
內容簡介
《算法分析導論（第2版）（英文版）》全面介紹了算法的數學分析中所涉及的主要技術。涵蓋的內容來自經典的數學課題（包括離散數學、初等實分析、組合數學），以及經典的計算機科學課題（包括算法和數據結構）。《算法分析導論（第2版）（英文版）》的重點是“平均情況”或“機率性”分析，書中也論述了“最差情況”或“複雜性”分析所需的基本數學工具。
內容提要
《算法分析導論（第2版）（英文版）》全面介紹了算法的數學分析中所涉及的主要技術。涵蓋的內容來自經典的數學課題（包括離散數學、初等實分析、組合數學），以及經典的計算機科學課題（包括算法和數據結構）。《算法分析導論（第2版）（英文版）》的重點是“平均情況”或“機率性”分析，書中也論述了“最差情況”或“複雜性”分析所需的基本數學工具。
《算法分析導論（第2版）（英文版）》第 1 版為行業內的經典著作，本版不僅對書中圖片和代碼進行了更新，還補充了新章節。全書共 9 章，第 1 章是導論 ；第 2~5 章介紹數學方法 ；第 6~9 章介紹組合結構及其在算法分析中的套用。除每章包含的大量習題以及參考文獻外，《算法分析導論（第2版）（英文版）》特設配套免費學習網站，為讀者提供了很多關於算法分析的補充材料，包括課件和相關網站的連結，幫助讀者提高學習興趣，完成更深入的學習。
《算法分析導論（第2版）（英文版）》適合作為高等院校數學、計算機科學以及相關專業的本科生和研究生的教材，也可供相關技術人員和愛好者學習參考。
作者簡介
Robert Sedgewick於1985年開始在普林斯頓大學任教，是該校計算機系的發起人，現任該校的計算機科學William O. Baker教授。他曾任Adobe Systems公司總監，並在Xerox PARC、IDA和INRIA等公司從事研究。他是算法領域入門著作Algorithms，Fourth Edition（《算法》第4版）的作者。Sedgewick教授在史丹福大學師從Donald E. Knuth院士，獲得博士學位。
Philippe Flajolet曾任法國羅克庫爾INRIA資深研究總監，創建並領導了ALGO研究組。他因在算法分析領域的開創性研究而聲名鵲起，在分析組合學方面梳理並發展出了強大的新方法，解決了很多長期懸而未決的難題，並在世界各地從事算法分析的教學。Flajolet博士是法國科學院成員。
目錄
T A B L E O F C O N T E N T S
Chapter One: Analysis of Algorithms 3
1.1 Why Analyze an Algorithm? 3
1.2 Theory of Algorithms 6
1.3 Analysis of Algorithms 13
1.4 Average-Case Analysis 16
1.5 Example: Analysis of Quicksort 18
1.6 Asymptotic Approximations 27
1.7 Distributions 30
1.8 Randomized Algorithms 33
Chapter Two: Recurrence Relations 41
2.1 Basic Properties 43
2.2 First-Order Recurrences 48
2.3 Nonlinear First-Order Recurrences 52
2.4 Higher-Order Recurrences 55
2.5 Methods for Solving Recurrences 61
2.6 Binary Divide-and-Conquer Recurrences and Binary Numbers 70
2.7 General Divide-and-Conquer Recurrences 80
Chapter Three: Generating Functions 91
3.1 Ordinary Generating Functions 92
3.2 Exponential Generating Functions 97
3.3 Generating Function Solution of Recurrences 101
3.4 Expanding Generating Functions 111
3.5 Transformations with Generating Functions 114
3.6 Functional Equations on Generating Functions 117
3.7 Solving the Quicksort Median-of-Three Recurrence with OGFs 120
3.8 Counting with Generating Functions 123
3.9 Probability Generating Functions 129
3.10 Bivariate Generating Functions 132
3.11 Special Functions 140
Chapter Four: Asymptotic Approximations 151
4.1 Notation for Asymptotic Approximations 153
4.2 Asymptotic Expansions 160
4.3 Manipulating Asymptotic Expansions 169
4.4 Asymptotic Approximations of Finite Sums 176
4.5 Euler-Maclaurin Summation 179
4.6 Bivariate Asymptotics 187
4.7 Laplace Method 203
4.8 “Normal” Examples from the Analysis of Algorithms 207
4.9 “Poisson” Examples from the Analysis of Algorithms 211
Chapter Five: Analytic Combinatorics 219
5.1 Formal Basis 220
5.2 Symbolic Method for Unlabelled Classes 221
5.3 Symbolic Method for Labelled Classes 229
5.4 Symbolic Method for Parameters 241
5.5 Generating Function Coefficient Asymptotics 247
Chapter Six: Trees 257
6.1 Binary Trees 258
6.2 Forests and Trees 261
6.3 Combinatorial Equivalences to Trees and Binary Trees 264
6.4 Properties of Trees 272
6.5 Examples of Tree Algorithms 277
6.6 Binary Search Trees 281
6.7 Average Path Length in Catalan Trees 287
6.8 Path Length in Binary Search Trees 293
6.9 Additive Parameters of Random Trees 297
6.10 Height 302
6.11 Summary of Average-Case Results on Properties of Trees 310
6.12 Lagrange Inversion 312
6.13 Rooted Unordered Trees 315
6.14 Labelled Trees 327
6.15 Other Types of Trees 331
Chapter Seven: Permutations 345
7.1 Basic Properties of Permutations 347
7.2 Algorithms on Permutations 355
7.3 Representations of Permutations 358
7.4 Enumeration Problems 366
7.5 Analyzing Properties of Permutations with CGFs 372
7.6 Inversions and Insertion Sorts 384
7.7 Left-to-Right Minima and Selection Sort 393
7.8 Cycles and In Situ Permutation 401
7.9 Extremal Parameters 406
Chapter Eight: Strings and Tries 415
8.1 String Searching 416
8.2 Combinatorial Properties of Bitstrings 420
8.3 Regular Expressions 432
8.4 Finite-State Automata and the Knuth-Morris-Pratt Algorithm 437
8.5 Context-Free Grammars 441
8.6 Tries 448
8.7 Trie Algorithms 453
8.8 Combinatorial Properties of Tries 459
8.9 Larger Alphabets 465
Chapter Nine: Words and Mappings 473
9.1 Hashing with Separate Chaining 474
9.2 The Balls-and-Urns Model and Properties of Words 476
9.3 Birthday Paradox and Coupon Collector Problem 485
9.4 Occupancy Restrictions and Extremal Parameters 495
9.5 Occupancy Distributions 501
9.6 Open Addressing Hashing 509
9.7 Mappings 519
9.8 Integer Factorization and Mappings 532
List of Theorems 543
List of Tables 545
List of Figures 547
Index 551
