內容簡介
本書為全英文。它全麵介紹瞭算法的數學分析中使用的基本方法,所涉及的內容來自經典的數學素材(包括離散數學、初等實分析、組閤數學),以及經典的計算機科學素材(包括算法和數據結構)。雖然書中論述瞭“最壞情形”和“復雜性問題”分析所需的基本數學工具,但是重點還是討論“平均情形”或“概率”分析。論題涉及遞歸、生成函數、漸近性、樹、串、映射等內容,以及對排序、樹查找、串查找和散列諸算法的分析。
本書全麵介紹瞭算法的數學分析中使用的基本方法,所涉及的內容來自經典的數學素材(包括離散數學、初等實分析、組閤數學),以及經典的計算機科學素材(包括算法和數據結構)。雖然書中論述瞭“最壞情形”和“復雜性問題”分析所需的基本數學工具,但是重點還是討論“平均情形”或“概率”分析。論題涉及遞歸、生成函數、漸近性、樹、串、映射等內容,以及對排序、樹查找、串查找和散列諸算法的分析。
盡管人們極為關注算法的數學分析,但是廣泛使用的方法和模型方麵的基本信息尚不能為該領域的工作和研究所直接使用。作者在本書中處理這種需求,把該領域齣現的挑戰以及為跟上新的研究以迎接這些挑戰所必需的背景資料完美地結閤在一起。
精彩書評
分析算法的人享有雙重的幸福。首先,他們能夠體驗到優雅數學模式純粹的美,這處模式存在於優美的計算過程之中。其次,當他們的理論使得其他工作能夠做得更快、更經濟時,他們得到的是實際的褒奬。因此,我們盼望已久的這部著作極受歡迎。該書作者不僅是該領域世界範圍內的領袖,而且還是闡述的大師。
——Donald E. Knuth
目錄
CHAPTER ONE:ANALYSIS OF ALGORITHMS
1.1 Why Analyze an Algorithm?
1.2 Computational Complexity
1.3 Analysis of Algorithms
1.4 Average-Case Analysis
1.5 Example: Analysis of Quieksort
1.6 Asymptotic Approximations
1.7 Distributions
1.8 Probabilistic Algorithms
CHAPTER TWO: RECURRENCE RELATIONS
2.1 Basic Properties
2.2 First-Order Recurrences
2.3 Nonlinear First-Order Recurrences
2.4 Higher-Order Recurrences
2.5 Methods for Solving Recurrences
2.6 Binary Divide-and-Conquer Recurrences and Binary
Numbers
2.7 General Divide-and-Conquer Recurrences
CHAPTER THREE: GENERATING FUNCTIONS
3.1 Ordinary Generating Functions
3.2 Exponential Generating Functions
3.3 Generating Function Solution of Recurrences
3.4 Expanding Generating Functions
3.5 Transformations with Generating Functions
3.6 Functional Equations on Generating Functions
3.7 Solving the Quicksort Median-of-Three Recurrencewith OGFS
3.8 Counting with Generating Functions
3.9 The Symbolic Method
3.10 Lagrange Inversion
3.11 Probability Generating Functions
3.12 Bivariate Generating Functions
3.13 Special Functions
CHAPTER FOUR: ASYMPTOTIC APPROXIMATIONS
4.1 Notation for Asymptotic Approximations
4.2 Asymptotic Expansions
4.3 Manipulating Asymptotic Expansions
4.4 Asymptotic Approximations of Finite Sums
4.5 Euler-Maclaurin Summation
4.6 Bivariate Asymptotics
4.7 Laplace Method
4.8 “Normal”Examples from the Analysis of Algorithms
4.9 “Poisson” Examples from the Analysis of Algorithms
4.10 Generating Function Asymptotics
CHAPTER FIVE: TREES
5.1 Binary Trees
5.2 Trees and Forests
5.3 Properties of Trees
5.4 Tree Algorithms
5.5 Binary Search Trees
5.6 Average Path Length in Catalan Trees
5.7 Path Length in Binary Search Trees
5.8 Additive Parameters of Random Trees
5.9 Height
5.10 Summary of Average-Case Results on Properties of Trees
5.11 Representations of Trees and Binary Trees
5.12 Unordered Trees
5.13 Labelled Trees
5.14 Other Types of Trees
CHAPTER SIX: PERMUTATIONS
6.1 Basic Properties of Permutations
6.2 Algorithms on Permutations
6.3 Representations of Permutations
6.4 Enumeration Problems
6.5 Analyzing Properties of Permutations with CGFs
6.6 Inversions and Insertion Sorts
6.7 Left-to-Right Minima and Selection Sort
6.8 Cycles and In Situ Permutation
6.9 Extremal Parameters
CHAPTER SEVEN:STRINGS AND TRIES
7.1 String Searching
7.2 Combinatorial Properties of Bitstrings
7.3 Regular Expressions
7.4 Finite-State Automata and the Knuth-Morris-Pratt
Algorithm
7.5 Context-Free Grammars
7.6 Tries
7.7 Trie Algorithms
7.8 Combinatorial Properties of Tries
7.9 Larger Alphabets
CHAPTER EIGHT: WORDS AND MAPS
8.1 Hashing with Separate Chaining
8.2 Basic Properties of Words
8.3 Birthday Paradox and Coupon Collector Problem
8.4 Occupancy Restrictions and Extremal Parameters
8.5 Occupancy Distributions
8.6 Open Addressing Hashing
8.7 Maps
8.8 Integer Facterization and Maps
List of Theorems
Index
前言/序言
算法分析導論(英文版) epub pdf mobi txt 電子書 下載 2024
算法分析導論(英文版) 下載 epub mobi pdf txt 電子書