算法分析与设计PDF|Epub|txt|kindle电子书版本网盘下载

算法分析与设计PDF格式电子书版下载

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

第一部分　基础工具2

第1章　算法分析2

1.1　算法的分析方法学2

1.1.1　伪代码4

1.1.2　随机存取机（RAM）模型5

1.1.3　统计基本操作的数量6

1.1.4　递归算法分析7

1.2　渐近符号8

1.2.1　大O符号8

1.2.2 与大“O”相关的渐近符号10

1.2.3　渐近表示的重要性12

1.3　数学概览13

1.3.1 求和13

1.3.2　对数和指数14

1.3.3　简单证明技术16

1.3.4　概率基础18

1.4　算法分析案例研究20

1.4.1 二次时间前缀平均值算法21

1.4.2　线性时间前缀平均值算法22

1.5 平摊方法22

1.5.1 平摊技术23

1.5.2　扩展数组实现分析25

1.6　实验28

1.6.1　实验组织28

1.6.2　数据分析和可视化29

1.7　习题31

基础题31

创新题33

程序设计35

1.8　本章注记36

2.1.1 栈37

2.1　栈和队列37

第2章　基本数据结构37

2.1.2 队列40

2.2 向量、表和序列43

2.2.1 向量43

2.2.2　表44

2.2.3 序列48

2.3 树49

2.3.1　树抽象数据类型51

2.3.2　树的遍历52

2.3.3　二叉树55

2.3.4　表示树的数据结构60

2.4　优先队列和堆62

2.4.1　优先队列抽象数据类型63

2.4.2　PQ排序、选择排序和插入排序64

2.4.3 堆数据结构66

2.4.4　堆排序71

2.5　字典与散列表76

2.5.1 无序字典ADT76

2.5.2　散列表77

2.5.3　散列函数78

2.5.5　冲突处理模式80

2.5.4　压缩映射80

2.5.6 通用散列83

2.6　Java示例：堆85

2.7 习题87

基础题87

创新题89

程序设计91

2.8　本章注记91

第3章　查找树和跳跃表93

3.1　有序字典和二叉查找树94

3.1.1　有序表94

3.1.3　二叉查找树中的查找96

3.1.2　二叉查找树96

3.1.4　二叉查找树中的插入98

3.1.5　二叉查找树中的删除99

3.1.6　二叉查找树的性能100

3.2　AVL树101

3.2.1　更新操作102

3.2.2　性能105

3.3　深度有界查找树106

3.3.1　多路查找树106

3.3.2　（2,4）树108

3.3.3 红黑树113

3.4　伸展树123

3.4.1　伸展123

3.4.2　伸展过程的平摊分析128

3.5　跳跃表131

3.5.1 查找132

3.5.2　更新操作133

3.5.3　跳跃表的概率分析135

3.6　Java示例：AVL树和红黑树136

3.6.1　AVL树的Java实现138

3.6.2　红黑树的Java实现141

基础题143

3.7　习题143

创新题144

程序设计145

3.8　本章注记146

第4章　排序、集合和选择147

4.1 归并排序147

4.1.1 分治法148

4.1.2　归并排序和递归方程151

4.2　集合抽象数据类型152

4.2.1　简单的集合实现152

4.2.2　具有union-find操作的划分153

4.2.3　基于树的划分实现154

4.3　快速排序159

4.4　基于比较的排序下界162

4.5　桶排序和基数排序163

4.5.1 桶排序163

4.5.2　基数排序164

4.6　比较排序算法165

4.7 选择166

4.7.1　剪枝一查找法166

4.7.2　随机化快速选择166

4.7.3　随机化快速选择分析167

4.8　Java示例：原位快速排序168

4.9 习题170

基础题170

创新题171

程序设计172

4.10　本章注记173

第5章　基本技术174

5.1 贪心法174

5.1.1 背包问题175

5.1.2　任务调度176

5.2.1　分治递归方程177

5.2　分治法177

5.2.2　整数相乘182

5.2.3　矩阵相乘183

5.3　动态规划185

5.3.1 矩阵链乘185

5.3.2　一般技术187

5.3.3　0-1背包问题188

5.4 习题190

基础题190

创新题191

程序设计191

5.5　本章注记192

第二部分　图算法194

第6章　图194

6.1 图抽象数据类型194

6.2　图的数据结构199

6.2.1　边表结构199

6.2.2　邻接表结构201

6.2.3　邻接矩阵结构203

6.3 图的遍历204

6.3.1　深度优先查找204

6.3.2　双连通分量206

6.3.3　广度优先查找211

6.4　有向图213

6.4.1　遍历有向图214

6.4.2　传递闭包216

6.4.3　DFS和垃圾收集218

6.4.4　有向无环图219

6.5　Java示例：深度优先查找222

6.5.1　修饰模式222

6.5.2　DFS引擎223

6.5.3　模板方法设计模式224

基础题227

6.6　习题227

创新题228

程序设计229

6.7　本章注记229

第7章　加权图230

7.1　单源点最短路径231

7.1.1　Dijkstra算法231

7.1.2　Bellman-Ford最短路径算法236

7.1.3　有向无环图中的最短路径238

7.2　所有顶点对之间的最短路径240

7.2.1　动态规划最短路径算法240

7.2.2　利用矩阵相乘计算最短路径241

7.3　最小生成树244

7.3.1　Kruskal算法245

7.3.2　Prim-Jarník算法249

7.3.3　Bar？vka算法251

7.3.4　MST算法比较253

7.4　Java示例：Dijkstra算法253

7.5 习题256

基础题256

创新题256

程序设计257

7.6　本章注记258

第8章　网络流和匹配259

8.1　流和割260

8.1.1　流网络260

8.1.2　割261

8.2　最大流262

8.2.1　剩余容量和增大路径262

8.2.2　Ford-Fulkerson算法264

8.2.3 Ford-Fulkerson算法分析266

8.2.4　Edmonds-Karp算法267

8.3　最大二分匹配269

8.4　最小代价流270

8.4.1　增大回路271

8.4.2　连续最短路径272

8.4.3　修改权值273

8.5　Java示例：最小代价流276

8.6　习题281

基础题281

创新题281

程序设计282

8.7　本章注记282

第9章　文本处理284

9.1 串和模式匹配算法284

第三部分　因特网算法284

9.1.1 串操作285

9.1.2　蛮力模式匹配286

9.1.3　Boyer-Moore算法287

9.1.4　Knuth-Morris-Pratt算法289

9.2　trie292

9.2.1 标准trie292

9.2.2　压缩trie294

9.2.3 后缀trie295

9.3 文本压缩298

9.2.4　搜索引擎298

9.3.1　赫夫曼编码算法299

9.3.2　修正贪心法300

9.4　文本相似性测试301

9.4.1　最长公共子序列问题301

9.4.2 应用动态规划求解LCS问题301

9.5 习题303

基础题303

创新题304

程序设计305

9.6　本章注记305

10.1　与数有关的基本算法306

第10章　数论和密码学306

10.1.1　基本数论的一些事实307

10.1.2　欧几里得GCD算法308

10.1.3　模运算310

10.1.4　模指数运算313

10.1.5　模乘法逆元315

10.1.6　素性测试316

10.2　密码计算320

10.2.1 对称加密模式321

10.2.2　公钥密码系统322

10.2.3　RSA密码系统323

10.2.4　El Gamal密码系统325

10.3　信息安全算法和协议326

10.3.1　单向散列函数326

10.3.2　时间戳和认证字典327

10.3.3 硬币抛掷和比特承诺327

10.3.4　安全电子传输（SET）协议328

10.3.5　密钥分发和交换329

10.4　快速傅里叶变换330

10.4.1　本原单位根332

10.4.2　离散傅里叶变换333

10.4.3　快速傅里叶变换算法335

10.4.4　大整数相乘337

10.5　Java示例：FFT339

10.6　习题345

基础题345

创新题345

程序设计346

10.7　本章注记346

第11章　网络算法348

11.1.1　网络协议栈349

11.1.2　消息传递模型349

11.1 复杂性测度和模型349

11.1.3　网络算法的复杂性测度350

11.2　基本分布式算法351

11.2.1 环网上的领导人选举351

11.2.2　树网上的领导人选举354

11.2.3　广度优先查找356

11.2.4　最小生成树359

11.3　广播路由和单播路由360

11.3.1　广播路由的洪泛算法360

11.3.2　单播路由的距离矢量算法361

11.3.3　单播路由的链路-状态算法362

11.4.1　逆向路径转发363

11.4　多播路由363

11.4.2　中心树364

11.4.3　Steiner树365

11.5　习题367

基础题367

创新题367

程序设计369

11.6　本章注记369

12.1 范围树372

第12章　计算几何372

第四部分　其他主题372

12.1.1　一维范围查找373

12.1.2　二维范围查找375

12.2　优先查找树377

12.2.1　构造一棵优先查找树378

12.2.2　优先查找树中的查找378

12.2.3　优先范围树380

12.3　四叉树和k-d树380

12.3.1 四叉树381

12.3.2　k-d树382

12.4.1 正交线段相交383

12.4　平面扫描技术383

12.4.2　查找最近点对385

12.5　凸包388

12.5.1　几何对象表示388

12.5.2　点方位测试389

12.5.3 凸包的基本性质390

12.5.4　礼品包扎算法392

12.5.5　Graham扫描算法393

12.6　Java示例：凸包395

基础题398

创新题398

12.7　习题398

程序设计400

12.8　本章注记400

第13章　NP完全性401

13.1　P类和NP类402

13.1.1　定义复杂类P和复杂类NP402

13.1.2　NP中的一些有趣问题404

13.2　NP完全性406

13.2.1 多项式时间归约和NP困难度406

13.2.2　Cook-Levin定理407

13.3　重要的NP完全问题408

13.3.1　CNF-SAT和3SAT410

13.3.2 VERTEX-COVER412

13.3.3 CLIQUE和SET-COVER413

13.3.4　SUBSET-SUM和KNAPSACK415

13.3.5　HAMILTONIAN-CYCLE和TSP417

13.4　近似算法419

13.4.1　多项式时间的近似模式420

13.4.2　VERTEX-COVER的2-近似算法422

13.4.3　TSP特例的2-近似算法423

13.4.4　SET-COVER的对数近似算法424

13.5　回溯法和分枝限界法426

13.5.1　回溯法426

13.5.2　分枝限界法429

13.6　习题433

基础题433

创新题434

程序设计435

13.7　本章注记435

第14章　算法框架437

14.1　外存算法437

14.1.1　分层的存储器管理438

14.1.2　（a,b）树和B树440

14.1.3　外存排序443

14.2.1　并行计算模型445

14.2　并行算法445

14.2.2　简单并行分治法446

14.2.3 串行子集和Brent定理447

14.2.4　递归倍增447

14.2.5　并行归并和排序450

14.2.6　找出凸多边形的直径450

14.3　在线算法452

14.3.1　高速缓存算法452

14.3.2　拍卖策略457

14.3.3　竞争查找树458

创新题461

基础题461

14.4 习题461

程序设计462

14.5　本章注记462

附录A　有用的数学知识464

A.1 对数和指数464

A.2　整型函数和关系465

A.3　求和466

A.4　有用的数学技术467

参考书目468

索引476