算法设计与分析PDF电子书下载
- 电子书积分:9 积分如何计算积分?
- 作 者:徐义春,万书振,解德祥编著
- 出 版 社:北京:清华大学出版社
- 出版年份:2016
- ISBN:9787302437892
- 页数:178 页
第1章 算法与性能 1
1.1 算法的概念 1
1.2 算法的表达 1
1.2.1 自然语言 1
1.2.2 结构化图形工具 2
1.2.3 计算机高级语言 3
1.3 算法的评价 3
1.3.1 算法的正确性 4
1.3.2 算法的空间复杂性 5
1.3.3 算法的时间复杂性 5
1.4 最差时间复杂性和平均时间复杂性 6
1.5 函数的阶与渐进性分析 7
1.5.1 复杂性函数的阶 7
1.5.2 函数的渐进性阶的比较 8
1.5.3 函数的渐进性阶的运算 8
1.5.4 函数的渐进性表示与函数集合 9
1.6 本章习题 9
第2章 递推与递归 10
2.1 递推关系与递推算法 10
2.2 递归函数 21
2.3 递归函数的执行过程 22
2.4 递归函数的时间复杂性与递归树 24
2.5 估计递归函数的复杂度的主方法 26
2.6 本章习题 27
第3章 分治法 29
3.1 二分搜索算法 29
3.1.1 问题分析与算法设计 29
3.1.2 时间复杂性分析 30
3.2 合并排序算法 30
3.2.1 问题分析与算法设计 31
3.2.2 Merge函数 31
3.2.3 时间复杂性分析 32
3.3 快速排序算法 32
3.3.1 固定主元的快速排序 32
3.3.2 随机选主元的快速排序 34
3.4 搜索第k元 35
3.4.1 平均时间为线性 36
3.4.2 最差时间为线性 37
3.5 最近点对 39
3.5.1 一维空间中的最近点对 39
3.5.2 二维空间中的最近点对 40
3.6 本章习题 44
第4章 动态规划 45
4.1 递归方法中的重复计算 45
4.2 最长公共子序列 47
4.2.1 问题描述 47
4.2.2 递推关系分析 47
4.2.3 算法实现 48
4.3 最大子段和 49
4.3.1 问题描述 49
4.3.2 递推分析 49
4.3.3 算法实现 50
4.4 矩阵连乘问题 51
4.4.1 问题描述 51
4.4.2 递推分析 52
4.4.3 算法实现 52
4.5 数据压缩问题 53
4.5.1 问题描述 53
4.5.2 递推分析 54
4.5.3 算法实现 55
4.6 0-1背包问题 56
4.6.1 问题描述 56
4.6.2 递推分析 56
4.6.3 算法描述 56
4.7 消费和储蓄问题 57
4.7.1 问题描述 57
4.7.2 递推分析 58
4.7.3 算法实现 58
4.8 最优二叉搜索树问题 59
4.8.1 问题描述 59
4.8.2 递推分析 60
4.8.3 算法实现 60
4.9 本章习题 61
第5章 贪心算法 63
5.1 活动安排问题 64
5.1.1 问题描述 64
5.1.2 问题分析 64
5.1.3 算法实现 64
5.2 服务调度问题 65
5.2.1 问题描述 65
5.2.2 问题分析 66
5.2.3 算法实现 66
5.3 最迟时间限制服务调度问题 67
5.3.1 问题描述 67
5.3.2 问题分析 67
5.3.3 算法实现 69
5.4 ε-背包问题 70
5.4.1 问题描述 70
5.4.2 问题分析 70
5.4.3 算法实现 70
5.5 最小生成树问题 72
5.5.1 问题描述 72
5.5.2 Prim算法原理 72
5.5.3 Prim算法实现 72
5.5.4 Kruskal算法原理 74
5.5.5 Kruskal算法实现 75
5.6 单源最短路径问题 77
5.6.1 问题描述 77
5.6.2 Dijkstra算法原理 77
5.6.3 Dijkstra算法实现 78
5.7 本章习题 80
第6章 深度优先搜索 81
6.1 树的搜索 81
6.1.1 解空间、子集树与排列树 81
6.1.2 深度优先搜索 82
6.1.3 0-1背包问题的回溯算法 84
6.1.4 n皇后问题 86
6.1.5 旅行推销员问题 88
6.1.6 最大团问题 90
6.1.7 图着色问题 91
6.1.8 连续邮资问题 92
6.2 图的搜索 94
6.2.1 狼羊过河问题 95
6.2.2 分油问题 98
6.3 本章习题 100
第7章 宽度优先搜索 102
7.1 宽度优先搜索一般形式 102
7.1.1 基本算法 102
7.1.2 算法性能 103
7.1.3 算法设计要素 104
7.2 树的分支定界法 104
7.2.1 0-1背包问题 104
7.2.2 旅行推销员问题 107
7.3 图的分支定界法 109
7.3.1 狼羊过河问题 109
7.3.2 分油问题 112
7.4 本章习题 115
第8章 近似算法 116
8.1 近似算法的概念 116
8.2 0-1背包问题的0.5 -近似算法 117
8.2.1 贪心算法 117
8.2.2 0.5 -近似算法 118
8.3 0-1背包问题的(1-ε)-近似算法 118
8.3.1 一种动态规划算法 118
8.3.2 (1-ε)-近似算法 120
8.4 旅行推销员问题的2-近似算法 121
8.5 本章习题 124
第9章 随机算法 126
9.1 数值型随机算法 126
9.1.1 数值积分随机算法 126
9.1.2 随机计数器 127
9.2 蒙特卡洛算法 128
9.2.1 矩阵乘法验证 128
9.2.2 质数检测 129
9.3 Las Vegas算法 132
9.3.1 n皇后问题 132
9.3.2 通用散列算法 134
9.4 本章习题 135
第10章 高级数据结构(一) 136
10.1 线段树 136
10.1.1 线段树的应用背景 136
10.1.2 线段树的结构 136
10.1.3 线段树的性质 137
10.1.4 线段树的基本存储结构 138
10.1.5 线段树的基本操作 138
10.1.6 线段树的应用举例 140
10.2 树状数组 142
10.2.1 树状数组的应用背景 142
10.2.2 树状数组的定义 142
10.2.3 树状数组的实现 143
10.2.4 树状数组的应用 143
10.3 伸展树 144
10.3.1 伸展树的应用背景 144
10.3.2 伸展树的定义及特点 144
10.3.3 伸展树的主要操作 145
10.4 Treap 151
10.4.1 概述 151
10.4.2 Treap基本操作 151
10.4.3 Treap的其他操作 153
10.4.4 总结 155
10.5 本章习题 156
第11章 高级数据结构(二) 157
11.1 块状链表 157
11.1.1 块状链表基本思想 157
11.1.2 块状链表基本操作 157
11.1.3 块状链表的应用 162
11.2 后缀树 163
11.2.1 模式匹配问题 163
11.2.2 后缀树简介 163
11.2.3 后缀树定义 163
11.2.4 后缀树的构建 164
11.2.5 后缀树的应用 166
11.3 树链剖分 168
11.3.1 树链剖分的思想和性质 168
11.3.2 树链剖分的实现及应用 169
11.4 本章习题 177
参考文献 178
- 《水面舰艇编队作战运筹分析》谭安胜著 2009
- 《分析化学》陈怀侠主编 2019
- 《指向核心素养 北京十一学校名师教学设计 英语 七年级 上 配人教版》周志英总主编 2019
- 《设计十六日 国内外美术院校报考攻略》沈海泯著 2018
- 《影响葡萄和葡萄酒中酚类特征的因素分析》朱磊 2019
- 《计算机辅助平面设计》吴轶博主编 2019
- 《高校转型发展系列教材 素描基础与设计》施猛责任编辑;(中国)魏伏一,徐红 2019
- 《仪器分析技术 第2版》曹国庆 2018
- 《景观艺术设计》林春水,马俊 2019
- 《全国普通高等中医药院校药学类专业十三五规划教材 第二轮规划教材 分析化学实验 第2版》池玉梅 2018
- 《市政工程基础》杨岚编著 2009
- 《家畜百宝 猪、牛、羊、鸡的综合利用》山西省商业厅组织技术处编著 1959
- 《《道德经》200句》崇贤书院编著 2018
- 《高级英语阅读与听说教程》刘秀梅编著 2019
- 《计算机网络与通信基础》谢雨飞,田启川编著 2019
- 《看图自学吉他弹唱教程》陈飞编著 2019
- 《法语词汇认知联想记忆法》刘莲编著 2020
- 《培智学校义务教育实验教科书教师教学用书 生活适应 二年级 上》人民教育出版社,课程教材研究所,特殊教育课程教材研究中心编著 2019
- 《国家社科基金项目申报规范 技巧与案例 第3版 2020》文传浩,夏宇编著 2019
- 《流体力学》张扬军,彭杰,诸葛伟林编著 2019
- 《大学计算机实验指导及习题解答》曹成志,宋长龙 2019
- 《指向核心素养 北京十一学校名师教学设计 英语 七年级 上 配人教版》周志英总主编 2019
- 《大学生心理健康与人生发展》王琳责任编辑;(中国)肖宇 2019
- 《大学英语四级考试全真试题 标准模拟 四级》汪开虎主编 2012
- 《大学英语教学的跨文化交际视角研究与创新发展》许丽云,刘枫,尚利明著 2020
- 《北京生态环境保护》《北京环境保护丛书》编委会编著 2018
- 《复旦大学新闻学院教授学术丛书 新闻实务随想录》刘海贵 2019
- 《大学英语综合教程 1》王佃春,骆敏主编 2015
- 《大学物理简明教程 下 第2版》施卫主编 2020
- 《指向核心素养 北京十一学校名师教学设计 英语 九年级 上 配人教版》周志英总主编 2019