在好例子网，分享、交流、成长！
您当前所在位置：首页 → Others 开发实例 → 一般编程问题 → 国科大 - 算法设计与分析 - 卜东波 - 讲义.pdf

国科大 - 算法设计与分析 - 卜东波 - 讲义.pdf

一般编程问题

下载此实例
  • 开发语言：Others
  • 实例大小：1.97M
  • 下载次数：34
  • 浏览次数：1032
  • 发布时间：2020-11-27
  • 实例类别：一般编程问题
  • 发 布 人：ezra22
  • 文件格式：.pdf
  • 所需积分：2
 相关标签： 讲义 分析 设计 算法
网友评论 举报投诉 收藏该页

实例介绍

【实例简介】

【实例截图】

from clipboard

【核心代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
目录
序（一） iii
序（二） iv
前言 i
第一章 绪论 2
1.1 什么是算法问题？ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 怎样进行算法设计？ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 观察问题内在结构的途径 . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 “分而治之”算法设计过程简介 . . . . . . . . . . . . . . . . . . . 7
1.2.3 “逐步改进”算法设计过程简介 . . . . . . . . . . . . . . . . . . . 10
1.2.4 智能枚举算法设计过程简介 . . . . . . . . . . . . . . . . . . . . 12
1.3 算法的复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.1 时间复杂度与空间复杂度 . . . . . . . . . . . . . . . . . . . . . 21
1.3.2 大 O 记号 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
第二章 “分而治之”算法 27
2.1 引言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2 排序问题：对数组的归约 . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.1 依据元素下标拆分数组：插入排序与归并排序 . . . . . . . . . . 28
2.2.2 “分而治之”算法时间复杂度分析及 Master 定理 . . . . . . . . . 34
2.2.3 依据元素的值拆分数组：QuickSort 算法 . . . . . . . . . . . 36
2.3 一个密切相关的问题：数组中的逆序对计数 . . . . . . . . . . . . . . . 44
2.4 选择问题：对数组的归约 . . . . . . . . . . . . . . . . . . . . . . . . . 47
v
vi 目录
2.4.1 采用随机选择的一个元素作中心元 . . . . . . . . . . . . . . . . 48
2.4.2 依据随机样本的统计量确定中心元 . . . . . . . . . . . . . . . . 50
2.4.3 选择“分组中位数的中位数”作为中心元 . . . . . . . . . . . . . . 52
2.5 整数乘法：对一对数组的归约 . . . . . . . . . . . . . . . . . . . . . . . 55
2.6 快速傅里叶变换：对数组的归约 . . . . . . . . . . . . . . . . . . . . . 62
2.7 矩阵乘法：对二维数组的归约 . . . . . . . . . . . . . . . . . . . . . . . 71
2.8 平面上最近点对寻找问题：对点集的归约 . . . . . . . . . . . . . . . . 73
第三章 动态规划算法 81
3.1 引言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.2 矩阵序列的链式相乘问题：对序列的归约 . . . . . . . . . . . . . . . . 82
3.2.1 算法设计：一个比较慢的初始版本 . . . . . . . . . . . . . . . . 83
3.2.2 算法设计：改进后的版本 . . . . . . . . . . . . . . . . . . . . . 87
3.2.3 算法运行过程示例 . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.2.4 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.2.5 一些讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.3 动态规划与多步决策过程 . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.4 0 − 1 背包问题：对集合的归约 . . . . . . . . . . . . . . . . . . . . . . 95
3.4.1 算法设计：一个比较慢的初始版本 . . . . . . . . . . . . . . . . 95
3.4.2 算法设计：改进后的版本 . . . . . . . . . . . . . . . . . . . . . 97
3.4.3 算法运行过程示例 . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.4.4 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 99
3.4.5 一些讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.5 RNA 二级结构预测：对字符串的归约 . . . . . . . . . . . . . . . . . . 101
3.5.1 算法设计与描述 . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.5.2 算法运行过程示例 . . . . . . . . . . . . . . . . . . . . . . . . . 104
3.5.3 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.6 隐马尔可夫模型的解码问题：对序列的归约 . . . . . . . . . . . . . . . 106
3.6.1 算法设计与描述 . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.6.2 算法运行过程示例 . . . . . . . . . . . . . . . . . . . . . . . . . 110
3.6.3 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 110
3.6.4 关于子问题定义的讨论 . . . . . . . . . . . . . . . . . . . . . . 111
目录 vii
3.7 字符串间的编辑距离：对一对字符串的归约 . . . . . . . . . . . . . . . 112
3.7.1 算法设计与描述 . . . . . . . . . . . . . . . . . . . . . . . . . . 115
3.7.2 算法运行过程示例 . . . . . . . . . . . . . . . . . . . . . . . . . 117
3.7.3 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 119
3.7.4 一些讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
3.8 字符串局部联配：对一对字符串的归约 . . . . . . . . . . . . . . . . . . 119
3.8.1 算法设计与描述 . . . . . . . . . . . . . . . . . . . . . . . . . . 121
3.8.2 算法运行过程实例 . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.8.3 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 125
3.8.4 一些讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
3.9 树上的顶点覆盖问题：对树的归约 . . . . . . . . . . . . . . . . . . . . 126
3.9.1 算法设计 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
3.9.2 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 127
3.9.3 算法设计：更“细”的子问题表述方式 . . . . . . . . . . . . . . . 128
3.10 有向无环图上的单源最短路径：对图的归约 . . . . . . . . . . . . . . . 129
3.10.1 算法设计与描述 . . . . . . . . . . . . . . . . . . . . . . . . . . 130
3.10.2 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 133
3.11 一般有向图上的单源最短路径：对图的归约 . . . . . . . . . . . . . . . 133
3.11.1 算法设计与描述 . . . . . . . . . . . . . . . . . . . . . . . . . . 134
3.11.2 算法运行过程示例 . . . . . . . . . . . . . . . . . . . . . . . . . 136
3.11.3 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 137
3.11.4 一些讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
3.12 应用动态规划技术求解整数规划问题 . . . . . . . . . . . . . . . . . . . 138
3.12.1 算法设计与描述 . . . . . . . . . . . . . . . . . . . . . . . . . . 139
3.12.2 算法运行过程示例 . . . . . . . . . . . . . . . . . . . . . . . . . 141
3.12.3 时间复杂度分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 141
3.12.4 一些讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
3.13 动态规划与马尔可夫决策过程 . . . . . . . . . . . . . . . . . . . . . . . 143
3.13.1 算法设计与描述 . . . . . . . . . . . . . . . . . . . . . . . . . . 144
3.13.2 运行过程示例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
3.13.3 一些讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
viii 目录
第四章 高级动态规划 157
4.1 引言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
4.2 降低空间复杂度：以“算”代“存” . . . . . . . . . . . . . . . . . . . . . . 158
4.2.1 计算最优决策项的分而治之策略 . . . . . . . . . . . . . . . . . 159
4.2.2 将最优决策项的计算融入最优解值的计算 . . . . . . . . . . . . 163
4.3 降低空间复杂度：以“存函数”代替“存值” . . . . . . . . . . . . . . . . . 165
4.4 降低时间复杂度：利用子问题最优解值的稀疏性 . . . . . . . . . . . . 170
4.4.1 利用稀疏性加速动态规划算法 . . . . . . . . . . . . . . . . . . . 170
4.4.2 只与边界点比较以进一步加速 . . . . . . . . . . . . . . . . . . . 173
4.4.3 一些讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
4.5 降低时间复杂度：基于最优解估计值的去冗余技术 . . . . . . . . . . . 177
4.5.1 计算两序列编辑距离的 Ficket 算法 . . . . . . . . . . . . . . . 177
4.5.2 改进版本：条带型动态规划算法 . . . . . . . . . . . . . . . . . 179
4.6 降低时间复杂度：利用单调性的动态规划 . . . . . . . . . . . . . . . . 180
4.7 降低时间复杂度：QI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
第五章 贪心算法 183
5.1 引言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
5.2 区间调度问题的两个版本：动态规划与贪心算法 . . . . . . . . . . . . 184
5.2.1 求解区间调度问题的动态规划算法 . . . . . . . . . . . . . . . . 184
5.2.2 区间调度问题的特殊情形及贪心求解算法 . . . . . . . . . . . . 186
5.2.3 关于贪心规则设计过程的一些讨论 . . . . . . . . . . . . . . . . 189
5.3 无负边有向图上的单源最短路径问题 . . . . . . . . . . . . . . . . . . . 190
5.3.1 Bellman-Ford 算法中的第一类冗余计算 . . . . . . . . . . . 191
5.3.2 改进的 Bellman-Ford 算法 . . . . . . . . . . . . . . . . . . . 193
5.3.3 Bellman-Ford 算法中的第二类冗余计算 . . . . . . . . . . . 193
5.3.4 进一步的改进：Dijkstra 贪心算法 . . . . . . . . . . . . . . . 194
5.3.5 一些讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

标签： 讲义 分析 设计 算法

实例下载地址

国科大 - 算法设计与分析 - 卜东波 - 讲义.pdf

不能下载？内容有错？ 点击这里报错 + 投诉 + 提问

好例子网口号：伸出你的我的手 — 分享！

相关软件

相关文章

网友评论

我要评论

发表评论

(您的评论需要经过审核才能显示)

查看所有0条评论>>

小贴士

感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。

  • 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
  • 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
  • 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
  • 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。

关于好例子网

本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明

;
报警