目录

资源下载第1章算法概述1

1.1算法无处不在1

1.2算法定义2

1.3算法的描述4

1.4算法设计的基本步骤7

1.5算法性能分析9

1.6时间复杂度10

1.6.1函数的渐进的界11

1.6.2最坏/最好/平均时间复杂度14

1.6.3常见时间复杂度类型14

1.6.4递归形式的算法分析20

1.6.5主定理21

1.7空间复杂度22

1.8本章小结23

习题123

第2章数据结构基础25

2.1算法与数据结构25

2.2线性数据结构26

2.2.1数组26

2.2.2链表26

2.2.3栈28

2.2.4队列30

2.3树状数据结构33

2.3.1树的基本概念33

2.3.2二叉树33

2.3.3二叉排序树40

2.3.4平衡二叉树41

2.3.5堆排序44

2.4图数据结构48

2.4.1图的基本概念48

2.4.2图的存储50

2.4.3图的遍历53

2.5本章小结56

习题256

第3章递归与分治58

3.1递归的概念58

3.2递归法经典案例59

3.2.1二分查找59

3.2.2整数划分问题60

3.2.3汉诺塔问题62

3.3分治法64

3.3.1分治的基本策略65

3.3.2分治法适用情况65

3.3.3分治法一般的算法设计模式65

3.3.4复杂性分析66

3.4分治法经典案例66

3.4.1大整数乘法66

3.4.2快速排序68

3.4.3合并排序71

3.4.4Strassen矩阵乘法74

3.4.5线性时间选择77

3.5本章小结82

习题383

第4章动态规划85

4.1动态规划思想85

4.2动态规划基本要素89

4.3动态规划求解的基本步骤90

4.4动态规划经典案例90

4.4.1最大子字段和问题90

4.4.201背包92

4.4.3最长公共子序列100

4.4.4矩阵连乘问题103

4.4.5最优二叉搜索树108

4.5本章小结115

习题4115

第5章贪心算法117

5.1贪心算法的基本要素117

5.1.1贪心选择性质117

5.1.2最优子结构性质118

5.1.3贪心算法与动态规划算法的差异118

5.2贪心算法经典案例119

5.2.1活动安排问题119

5.2.2背包问题121

5.2.3哈夫曼编码122

5.2.4最小生成树130

5.2.5单元最短路径135

5.2.6多机调度问题138

5.3本章小结140

习题5140

第6章回溯法142

6.1回溯法的基本原理142

6.1.1问题的解空间143

6.1.2解空间树143

6.1.3回溯法搜索过程145

6.1.4回溯法适用条件147

6.2回溯法的经典案例148

6.2.1装载问题148

6.2.201背包问题150

6.2.3n皇后问题151

6.2.4图的着色问题154

6.2.5旅行商问题156

6.2.6批处理作业调度158

6.2.7电路板排列问题160

6.3本章小结162

习题6163

第7章分支限界法164

7.1分支限界法的基本思想164

7.1.1结点的扩展方式165

7.1.2限界函数的选择167

7.1.3最优解的确定方法170

7.2分支限界法的经典案例170

7.2.101背包问题170

7.2.2单元最短路径问题176

7.2.3最优装载问题179

7.2.4布线问题181

7.2.5最大团问题184

7.3本章小结187

习题7187

附录A主定理证明188

附录B卡特兰数190

参考文献192