算法设计技巧与分析].(沙特)阿苏外耶.清晰版
算法设计技巧与分析].(沙特)阿苏外耶.清晰版 非常经典的算法书，值得一看！本书拟用做算法设计和分析领域的教科书,它包含了可作为两学期算法课程的内容
第1章到第⑩0章提供∫大学三四年级算法课程的核心材料,有些内容可以跳过,如合并查
找算法的平摊分析、稠图情况下最短路径和最小生成树的线性时间算法。教师可能会发现
加上后面章节的一些材料,如冋溯、随机算法、近似算法或儿何扫描是有用的。余下的材料
可作为研究生的算法课程内容。
本书所要求的预备知识已经减到最少,仅需要离散数学和数据结构的基本知识
感谢 King fabd University of Petroleum& Minerals( KFUPM,皇家法哈德石油矿业大学)的
支持和对手稿准备提供的方便。本书的编写得到 KFUPM的项目 ics/algorithm./182的资助。我
还要感谢那些认真阅读手稿各部分并且提出许多有益建议的人,包括一些在KFUM学习算
法课程的本科生和研究生。特别感谢S. Alhassan,H. Almuallim和 s. Ghanta的有价值的评注。
M. H. alsuwaiyel
日录
第一部分基本概念和算法导引
第1章算法分析基本概念
1····‘·····"···········.4·‘··‘44·◆··“·4日;
1.2历史背景…
1.3二分搜索
1.4合并两个已排序的表…
22367
1.5选择排序…
6插入排序……
1.7自底向上合并排序
789
郾郾曲看d血
1.8时间复杂性…
1.9空间复杂性
■p■血自看b鲁自t看■画
19
1.10最优算法……
1.11如何估计算法运行时间
··■昏■看即看·■■·p■■画』晶·‘画4·●●
21
1.12最坏情况和平均情况的分析
26
1.13平摊分析……………………………………………29
1.14输入大小和问题实例
中◆●P
··.·‘····◆日·◆·甲日日·◆
1.15练习………
1.16参考注释
第2章数学预备知识………
2.1集合、关系和函数
2.2证明方法
4
2.3对数
44···‘;‘◆中◆◆·甲『·日日日日·日日日日日·吾.··4吾········‘b··“日日aa甲4甲·日····香+·◆日訃b
24底函数和顶函数…
45
25阶乘和二项式系数
q■●↓◆會■D■即4自4喜命·命■音,“▲命·幽
45
2.6鸽巢原理…………………
………48
27和式…
自a4·b日白甲q甲b日·日吾日.44·今·
48
28递推关系
音■■·自血●甲咖聊p●
29练习…
自■血
·即鲁自血■■■甲司聊4●
第3章数据结构
……………"……6
3.1引言
即即p■■《■■
3.2链表
··d合命日a·4·4b咱"·:··B日·日··4·····如·
…67
3.3图…
◆血◆辛●●●中看口
3.4树…………
3.5根树……
36二叉树
…………71
3.7练习
3.8参考注释
血D啁d●即■p山画●■
幽●卓●睁●
第4章堆和不相交集数据结构
■p司●
74
4.1引言
74
4.2堆
■◆鲁日鲁qq·鲁q旱·■·····●·●郾◆●會■看●↓自自●·●■■4●自喜·●d■自●p4“b“画●▲命b●血‘pp▲
了4
4.3不相交集数据结构…
4.4练习…………………………………………………………85
4.5参考注释………
第二部分基于递归的技术
●●自山命
争■■申昏■卾甲帽鲁■■罪晋自P會●·喜4●
第5章归纳法
5.1引言
∷9
5.2两个简单的例子
53基数排序
●看“■音自血自中●自自‘··昌申中●中··●··●
92
54整数幂
●·鲁·甲导···看·罪罪·中司·号q司普甲?甲q··督号q·冒管191鲁命
93
5.5多项式求值( Homer规则)
56生成排列
95
5.7寻找多数元素
·中·····4··4·4·q甲4··P:44··:44。·
58练习
…99
59参考注释
·····中····◆
101
第6章分治
6.1引言
自1白画p看血
q鲁晋◆··命。·自命也岸p·曾●专口即●4甲银D郾
102
6.2二分搜索
6.3合并排序
曾喜b▲pp中●··甲··单中·●●自4日即p●矿自甲甲p●画甲矿d·●号p●
………105
64分治范式
………………107
6.5寻找中项和第k小元家
单◆辛■■聊●喷自■自自早·即·甲甲■罪着■P■罪●。·罪·p《p◆罪●鲁自p_d■●鲁
命■
109
快速排序
■●●ep聊●p咖
■要◆●
67大整数乘法
■··音即●bpP●
l18
68矩阵乘法
日自自●●·中·●命山申导··中卓·自曾■
中罪晋鲁t曾『要·中要中即
……………119
6.9最近点对问题……
·121
6.10练习
■爭咖·■聊聊·■■即曾◆唱■阝『■Dq◆即鲁罪φ鲁自卾看DD甲聊qp"■b·卓p普着ρ
.124
6.11参考注释
自■备■晶●
128
第7章动态规划
129
7.1引言……
●喜·音音●■自。音·自●
…………129
72最长公共子序列问题
130
73矩阵链相乘
中。曾鲁即·。即◆曾
q甲■■噜
是4↓.44·合· I+.LeI·日b
…132
7.4动态规划范式
136
7,5所有点对的最短路径问题
●P·甲··●白
136
7.6背包问题
138
7.7练习
曾q唱甲1q甲·■pP■
日甲看
鲁1D■
7.8参考注释
144
第三部分最先割技术
bb《●自晋●看q《食西■曲·也自倡b画自电·日p__p◆
■自會■鲁·■自自血4···自“會■■■命↓申●4■
145
第8章贪心算法
146
8.1引言
146
8.2最短路径问题
…………………146
83最小耗费生成树( Kruskal算法)…
◆旱甲p命·『司·◆
151
84最小耗费生成树(Prim算法)
153
8.5文件压缩
看■号。
■幽◆p
◆·●φ◆p
157
8.6练习
pdD●·最
4p■··■●啁·血·血山血。
59
8.7参考注释
161
第9章图的遍历…
9.1引言……
●
…………162
92深度优先搜索
……162
9.3深度优先搜索的应用
看音·4t·●聊看D山·●画
a·●·:····
165
94广度优先搜索
曾會身會■■自自鲁◆自备
号■·看鲁■备聊甲申·
169
95广度优先搜索的应用
170
练习
D4·d司●t曲即
甲會◆·血咖
∴……170
97参考注释
172
第四部分问题的复杂性
■■口■口d郾鲁
省·自鲁自4
P·中·?
第10章NP完全问题
血“■■d幽画●啁啁
…………s………174
0.1引
174
10.2P类
·自命p●
身鲁省鲁·晶。■鲁看动电●
……………176
10.3NP
类
176
104NP完全问题
自自◆■·■■■b暑■■命罪唇■单●t●·4b●●
177
10.5c-NP类
n■·
182
10.6NI类……
嗶p·■◆會即郾■彰看自音·音■画
183
10.7四种类之间的关系
···D···合自■
184
10,8练习
10.9参考注释
■旷『·●聊●■伊唱哥b咖■t個■自音b画●幽
186
第11章计算复杂性引论
即●●·q
中甲···甲■■即甲鲁
曾鲁●■●
…187
I1.1引言……………
187
1l2计算檩型:图灵机
中↓·卡●自日音●
18
l1.3k带图灵机和时间复杂性……
…………………187
11.4离线图灵机和空间复杂性…
189
11.5带压缩和线性增速
191
116复杂性类之间的关系……
191
11.7归约
●●聊●命聊
118完全性
司申◆
198
11.9多项式时间层次…
203
11.10练习
……205
11.11参考注释
208
第12章下界
12.1引言
12.2平凡下界………
209
12.3决策树模型
■导鲁■
209
12.4代数决策树模型
甲■甲“号
211
12.5线性时间归约………
●自即
…∷213
126练习
·甲···甲·◆甲日÷··qp·甲·4·甲·甲··4···日···p44········4··;B·B日··"
鲁··鲁◆自自·自命b自申甲
214
12.7参考注释
216
第五部分克服困难性
争■卓司●甲鲁命
●。中●中番■
……217
第13章回溯法
曾會●·■●·;b■p司『『冒4會·■D國督4聊DPd●●d备
…………218
13.1引言
218
13.23着色问题
…218
1338皇后问题
■·晋個驴鲁晋·p鲁■●4鲁鲁
134—般回溯方法…
223
13.5分支限界法
曾掌■早鲁冒■罪■帽罩
……225
13.6练习…………
7
13.7参考注释………
…………228
第14章随机算法…
14.1引言
甲司申p申电。。甲自pq要p甲■■命甲pp看看p●哪
………………229
42 Las vegas和 Monte carlo算法
■·鲁◆●●自·◆··身罪●··自會自q會中·咖咖身t要◆口
229
14.3随机化快速排序…
14.4随机化的选择算法……………………………………………231
l4.5测试串的相等性…
232
14.6模式匹配…
234
14.7随机取样
咖争◆會會中着自甲
235
148素数性测试
4鲁●d
237
149练习
■罪◆q····日·甲罪■睿罪◆·;φ罪命日·婚;··p··4
24I
14.10参考注释
242
10
第15章近似算法
244
15.1引
中●日4·4●
244
152基本定义
244
15.3差界…
●●b●
“曲d口鲁■■
■·@·D如■
15.4相对性能界
2416
15.5多项式近似方案
■自血鲁·自
15.6完全多项式近似方案
D■■p口■鲁■■●
15.7练………
……………255
158参考注释
亠中P·.:··甲日吾·4。·.·晋Dd···+=‘
257
第六部分域指定问题的迭代改进
t看●
第16章网络流
●p口口■』二
…260
16.1.引言…
260
162预备知识
当b·当44··4q·号4
…………"…260
63Fo- Fulkerson方法…
262
16.4最大容量增值…
……………………………263
16.5最短路径增值
264
66 Dinic算法
16.7MM算法
···■b●·p◆◆备●●ψ
号·口●●食p·■—●
269
16.8练习…
270
16.9参考注释
↓●●●··备由
271
第17章匹配
■中鲁中會印甲
……272
17.1引言
………272
17.2预备知识
·日口鲁自·白■“晷··■·●●●『·旱·◆pb血◆
272
173网络流方法
b●d曲■■
274
174二分图的匈牙利树方法
4“4··4·4····4·········-◆·4·p。;日a甲“4‘、▲4
274
175一般图中的最大匹配
·●鲁看即
176二分图的O(n25)算法
17.7练习
■鲁·■■自命■■
284
178参考注释
■■●自·■■自ψ■·着严甲甲■看D●』。D■▲血A
286
第七部分计算几何技术
287
第18章几何扫描
……288
18.1引言……
88
18.2几何预备知识
289
18.3计算线段的交点
184凸包问题
…………………………………292
18.5计算点集的直径
6练习
18.7参考注释
第19章 Voronoj图解
自自◆自血自■自·自自自·命自
19.1引言
昏■自■音■■鲁者·■bp口‘▲■b4■备自■■晶■备·“▲血日“■··●●
192最近点 Voronoi图解
曾●■■■■■■鲁自《看画看曲■↓曲曲看山血
300
193 voronoi图解的应用
194最远点 Voronoi图解
号·冒·即■·聊看■●●自最看申●鲁4bb音。自●自郾
…306
19.5最远点 voronoi图解的应用
308
19.6练习
号唱甲即冒■■●
·昏聊會●;●·自●b着■■■
309
19.7参考注释
■■郾看p●
3l0
参考文献……
12
第一部分基本概念和算法导引
本书的这一部分研究算法设计和分析的基本工具与准备知识。
第1章是为本书其余部分做准备的。这一章将讨论一些简单算法的例子,这些算法用来
解决几乎在所有讦算机科学应用中都会遇到的基本问题,包括搜索、合并和排序。参考这些
示例算法,接着研究作为算法分析基础的数学知识,尤其对如何分析一个给定算法的运行时
间和所需空阊进行了详細研究。
第2章研究的是算法分析所需的最基本的数学背景知识,详细讲述了分析算法时最常遇
到的求和与递推关系。需要着重强调的是分治递推的解决方法,因为它是分析分治这一大类
算法的基础。这里不打算在本书中讨论一般递推式的解与生成函数的方法,要详细了解这部
分内容的读者,可以参考标准的离散数学书。
第3章回顾了一些在算法设计中经常使用的基本的数据结构。本章没有深入进行讨论
如要了解更加全面的知识,可以参考标准的数据结构书
第4章较详尽地讨论用来保持优先队列和不相交集的两种基本数据结构。在许多有效算
法中(特别是图的算法设计中),这两种数据结构(堆和不相交集数据结构)被用做构件模块
本书中,堆用来设计有效排序算法 HEAPSORT。在第8章中,堆还是解决单源最短路径问题、
最小生成树问题和为数据压縮寻找可变长编码问题的有效算法,堆也被用在分支限界法中
(在13.5节讨论)。8.3节的算法 KRUSKAL将用不相交集数据结构来寻找无向图中的最小生
成树。在有关文献中,这两种数据结构都被广泛用来设计更加复杂的算法。
资源下载地址和密码（百度云盘）：**** Hidden Message ***** 百度网盘信息回帖可见
本资源由Java自学网收集整理【www.javazx.com】 99999999999999999999999999 6666666666666666666666666666666 look!!!!!!!!!!!!!!!!!!!!!!!! 谢谢分享！！！ 算法设计技巧与分析].(沙特)阿苏外耶.清晰版 6666666666666666666666666666 算法设计技巧与分析] 算法设计技巧与分析].(沙特)阿苏外耶.清晰版 谢谢楼主分享，学习下~~~~