算法分析导论 第2版 英文版【2025|PDF下载-Epub版本|mobi电子书|kindle百度云盘下载】

算法分析导论 第2版 英文版PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

CHAPTER ONE：ANALYSIS OF ALGORITHMS3

1.1 Why Analyze an Algorithm?3

1.2 Theory of Algorithms6

1.3 Analysis of Algorithms13

1.4 Average-Case Analysis16

1.5 Example:Analysis of Quicksort18

1.6 Asymptotic Approximations27

1.7 Distributions30

1.8 Randomized Algorithms33

CHAPTER TWO：RECURRENCE RELATIONS41

2.1 Basic Properties43

2.2 First-Order Recurrences48

2.3 Nonlinear First-Order Recurrences52

2.4 Higher-Order Recurrences55

2.5 Methods for Solving Recurrences61

2.6 Binary Divide-and-Conquer Recurrences and Binary Numbers70

2.7 General Divide-and-Conquer Recurrences80

CHAPTER THREE：GENERATING FUNCTIONS91

3.1 Ordinary Generating Functions92

3.2 Exponential Generating Functions97

3.3 Generating Function Solution of Recurrences101

3.4 Expanding Generating Functions111

3.5 Transformations with Generating Functions114

3.6 Functional Equations on Generating Functions117

3.7 Solving the Quicksort Median-of-Three Recurrence with OGFs120

3.8 Counting with Generating Functions123

3.9 Probability Generating Functions129

3.10 Bivariate Generating Functions132

3.11 Special Functions140

CHAPTER FOUR：ASYMPTOTIC APPROXIMATIONS151

4.1 Notation for Asymptotic Approximations153

4.2 Asymptotic Expansions160

4.3 Manipulating Asymptotic Expansions169

4.4 Asymptotic Approximations of Finite Sums176

4.5 Euler-Maclaurin Summation179

4.6 Bivariate Asymptotics187

4.7 Laplace Method203

4.8"Normal"Examples from the Analysis of Algorithms207

4.9"Poisson"Examples from the Analysis of Algorithms211

CHAPTER FIVE：ANALYTIC COMBINATORICS219

5.1 Formal Basis220

5.2 Symbolic Method for Unlabelled Classes221

5.3 Symbolic Method for Labelled Classes229

5.4 Symbolic Method for Parameters241

5.5 Generating Function Coefficient Asymptotics247

CHAPTER SIX：TREES257

6.1 Binary Trees258

6.2 Forests andTrees261

6.3 Combinatorial Equivalences to Trees and Binary Trees264

6.4 Properties of Trees272

6.5 Examples of Tree Algorithms277

6.6 Binary Search Trees281

6.7 Average Path Length in Catalan Trees287

6.8 Path Length in Binary Search Trees293

6.9 Additive Parameters of Random Trees297

6.10 Height302

6.11 Summary of Average-Case Results on Properties of Trees310

6.12 Lagrange Inversion312

6.13 Rooted Unordered Trees315

6.14 Labelled Trees327

6.15 Other Types of Trees331

CHAPTER SEVEN：PERMUTATIONS345

7.1 Basic Properties of Permutations347

7.2 Algorithms on Permutations355

7.3 Representations of Permutations358

7.4 Enumeration Problems366

7.5 Analyzing Properties of Permutations with CGFs372

7.6 Inversions and Insertion Sorts384

7.7 Left-to-Right Minima and Selection Sort393

7.8 Cycles and In Situ Permutation401

7.9 Extremal Parameters406

CHAPTER EIGHT：STRINGS AND TRIES415

8.1 String Searching416

8.2 Combinatorial Properties of Bitstrings420

8.3 Regular Expressions432

8.4 Finite-State Automata and the Knuth-Morris-Pratt Algorithm437

8.5 Context-Free Grammars441

8.6 Tries448

8.7 Trie Algorithms453

8.8 Combinatorial Properties ofTries459

8.9 Larger Alphabets465

CHAPTER NINE：WORD S AND MAPPINGS473

9.1 Hashing with Separate Chaining474

9.2 The Balls-and-Urns Model and Properties of Words476

9.3 Birthday Paradox and Coupon Collector Problem485

9.4 Occupancy Restrictions and Extremal Parameters495

9.5 Occupancy Distributions501

9.6 Open Addressing Hashing509

9.7 Mappings519

9.8 Integer Factorization and Mappings532

List of Theorems543

List of Tables545

List of Figures547

Index551