算法详解 卷1 Part 1 算法基础 The basicsPDF|Epub|txt|kindle电子书版本网盘下载

算法详解 卷1 Part 1 算法基础 The basicsPDF格式电子书版下载

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

第1章 绪论1

1.1为什么要学习算法1

1.2整数乘法3

1.2.1问题和解决方案3

1.2.2整数乘法问题3

1.2.3小学算法4

1.2.4操作数量的分析5

1.2.5还能做得更好吗5

1.3 Karatsuba乘法6

1.3.1一个具体的例子6

1.3.2一种递归算法7

1.3.3 Karatsuba乘法9

1.4 MergeSort算法11

1.4.1推动力11

1.4.2排序12

1.4.3一个例子13

1.4.4伪码14

1.4.5 Merge子程序15

1.5 MergeSort算法分析16

1.5.1 Merge的运行时间17

1.5.2 MergeSort的运行时间18

1.5.3定理1.2的证明19

1.5.4小测验1.1～1.2的答案23

1.6算法分析的指导原则23

1.6.1第1个原则：最坏情况分析24

1.6.2第2个原则：全局分析25

1.6.3第3个原则：渐进性分析26

1.6.4什么是“快速”算法27

1.7本章要点28

1.8习题29

挑战题31

编程题31

第2章 渐进性表示法32

2.1要旨32

2.1.1推动力32

2.1.2高级思维33

2.1.3 4个例子34

2.1.4小测验2.1～2.4的答案38

2.2大Ο表示法40

2.2.1文本定义40

2.2.2图形定义40

2.2.3数学定义41

2.3两个基本例子42

2.3.1 k阶多项式是O（nk）42

2.3.2 k阶多项式不是O（nk-1 ）43

2.4大Ω和大Θ表示法44

2.4.1大Ω表示法44

2.42大？表示法45

2.4.3小O表示法46

2.4.4渐进性表示法的来源47

2.4.5小测验2.5的答案48

2.5其他例子48

2.5.1在指数中添加一个常数48

2.5.2指数乘以一个常数49

2.5.3最大值vs.和49

2.6本章要点50

2.7习题51

第3章 分治算法53

3.1分治法规范53

3.2以O（n log n）时间计数逆序对54

3.2.1问题54

3.2.2一个例子54

3.2.3协同筛选55

3.2.4穷举搜索法55

3.2.5分治法56

3.2.6高级算法57

3.2.7关键思路：站在MergeSort的肩膀上57

3.2.8重温Merge58

3.2.9 Merge和分离逆序对60

3.2.10 Merge_ and CountSplitInv61

3.2.11正确性61

3.2.12运行时间62

3.2.13小测验3.1～3.2的答案62

3.3 Strassen的矩阵相乘算法63

3.3.1矩阵相乘63

3.3.2例子（n＝2）64

3.3.3简单算法64

3.3.4分治法65

3.3.5节省一个递归调用67

3.3.6细节68

3.3.7小测验3.3的答案69

3.4 O（n log n）时间的最近点对（Closest Pair）算法70

3.4.1问题70

3.4.2热身：1D情况71

3.4.3预处理71

3.4.4一种分治方法72

3.4.5一个微妙的变化74

3.4.6 ClosestSplitPair74

3.4.7正确性76

3.4.8辅助结论3.3 （a）的证明77

3.4.9辅助结论3.3 （b）的证明78

3.4.10小测验3.4的答案80

3.5本章要点80

3.6习题81

挑战题81

编程题82

第4章 主方法83

4.1重温整数乘法83

4.1.1RecIntMult算法84

4.1.2 Karatsuba算法84

4.1.3比较递归过程85

4.2形式声明86

4.2.1标准递归过程86

4.2.2主方法的陈述和讨论87

4.3.6个例子88

4.3.1重温MergeSort89

4.3.2二分搜索89

4.3.3整数乘法的递归算法90

4.3.4 Karatsuba乘法90

4.3.5矩阵乘法91

4.3.6一个虚构的递归过程92

4.3.7小测验4.2～4.3的答案93

4.4主方法的证明94

4.4.1前言94

4.4.2重温递归树95

4.4.3单层所完成的工作96

4.4.4各层累计97

4.4.5正义与邪恶：需要考虑3种情况98

4.4.6预告运行时间上界99

4.4.7最后的计算：第一种情况100

4.4.8迂回之旅：几何级数101

4.4.9最后的计算：第二种情况和第三种情况102

4.4.10小测验4.4～4.5的答案103

4.5本章要点103

4.6习题104

第5章 快速排序（QuickSort）107

5.1概述107

5.1.1排序108

5.1.2根据基准元素进行划分108

5.1.3高级描述110

5.1.4内容前瞻110

5.2围绕基准元素进行划分111

5.2.1简易方法111

5.2.2原地实现：高级计划112

5.2.3例子113

5.2.4 Partition子程序的伪码115

5.2.5 QuickSort的伪码117

5.3良好的基准元素的重要性117

5.3.1 ChoosePivot的简单实现118

5.3.2 ChoosePivot的过度实现118

5.3.3小测验5.1～5.2的答案119

5.4随机化的QuickSort121

5.4.1 ChoosePivot的随机化实现121

5.4.2随机化QuickSort的运行时间122

5.4.3直觉：随机基准元素为什么很好123

5.5随机化QuickSort的分析124

5.5.1预备工作125

5.5.2分解蓝图126

5.5.3应用蓝图128

5.5.4计算比较的概率130

5.5.5最后的计算132

5.5.6小测验5.3的答案133

5.6排序需要Ω（n log n）的比较134

5.6.1基于比较的排序算法134

5.6.2具有更强前提的更快速排序135

5.6.3定理5.5的证明136

5.7本章要点138

5.8习题139

挑战题140

编程题141

第6章 线性时间级的选择142

6.1 RSelect算法143

6.1.1选择问题143

6.1.2简化为排序144

6.1.3分治法145

6.1.4 RSelect的伪码146

6.1.5 RSelect的运行时间147

6.1.6小测验6.1～6.2的答案149

6.2 RSelect的分析150

6.2.1根据阶段追踪进展150

6.2.2简化为掷硬币151

6.2.3综合结论153

6.3 DSelect算法154

6.3.1基本思路：中位的中位元素154

6.3.2 DSelect的伪码155

6.3.3理解DSelect156

6.3.4 DSelect的运行时间157

6.4 DSelect的分析159

6.4.1递归调用之外所完成的工作159

6.4.2一个粗略的递归过程159

6.4.3 30-70辅助结论160

6.4.4解析递归过程163

6.4.5先猜后验方法164

6.5本章要点166

6.6本章习题166

挑战题167

编程题168

附录A快速回顾数学归纳法169

附录B快速回顾离散概率173