算法設(shè)計(jì)與分析第2版

定　價(jià)：￥59.00

作　者：	黃宇著
出版社：	機(jī)械工業(yè)出版社
叢編項(xiàng)：	高等學(xué)校計(jì)算機(jī)專業(yè)系列教材
標(biāo)　簽：	暫缺

購(gòu)買這本書可以去

ISBN：	9787111657231	出版時(shí)間：	2020-07-01	包裝：	平裝
開本：	16開	頁(yè)數(shù)：	240	字?jǐn)?shù)：

內(nèi)容簡(jiǎn)介

　　本書是作者在多年從事算法設(shè)計(jì)與分析課程教學(xué)和研究的基礎(chǔ)上編寫而成，系統(tǒng)地介紹了算法設(shè)計(jì)與分析的理論、方法和技術(shù)。內(nèi)容圍繞兩條主線來(lái)組織。一條主線是介紹典范性的算法問題，如排序、選擇、圖遍歷等。另一條主線是介紹典范性的算法設(shè)計(jì)分析策略，如分治、貪心、動(dòng)態(tài)規(guī)劃等算法設(shè)計(jì)策略和對(duì)手分析、平攤分析等算法分析策略。本書中兩條主線交替進(jìn)行，每條主線又各自分為基本和進(jìn)階兩部分。

作者簡(jiǎn)介

　　黃宇，南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系教授，博士生導(dǎo)師，主要研究方向?yàn)榉植际剿惴ā⒎植际较到y(tǒng)和軟件方法學(xué)。曾主持兩項(xiàng)國(guó)家自然科學(xué)基金項(xiàng)目，并作為主要成員參與了國(guó)家973計(jì)劃、國(guó)家自然科學(xué)基金創(chuàng)新群體項(xiàng)目等多項(xiàng)國(guó)家重大科研項(xiàng)目。2014年獲得南京大學(xué)登峰人才支持計(jì)劃資助，2011年獲教育部技術(shù)發(fā)明獎(jiǎng)。所指導(dǎo)的博士論文榮獲2016年中國(guó)計(jì)算機(jī)學(xué)會(huì)博士學(xué)位論文獎(jiǎng)。已在IEEE Trans on Computers、IEEE Trans on Parallel and Distributed Systems、IEEE PerCom等重要國(guó)際期刊及會(huì)議上發(fā)表多篇論文。

圖書目錄

前言
教學(xué)建議
第一部分計(jì)算模型
第1 章抽象的算法設(shè)計(jì)與分析 2

11 RAM 模型的引入 2

111 計(jì)算的基本概念 2

112計(jì)算模型的基本概念 3
113RAM 模型 3

114計(jì)算模型的選擇：易用性與精確性 5
12 抽象算法設(shè)計(jì) 6

121 算法問題規(guī)約 6

122 算法正確性證明：數(shù)學(xué)歸納法 7

13 抽象算法分析 8

131 抽象算法的性能指標(biāo) 8
132 最壞情況時(shí)間復(fù)雜度分析 9

133 平均情況時(shí)間復(fù)雜度分析 10

14 習(xí)題 11
第2 章從算法的視角重新審視數(shù)學(xué)的概念 14
21 數(shù)學(xué)運(yùn)算背后的算法操作 14

211 取整 x 和 x 14
212 對(duì)數(shù)log n 14
213 階乘n! 15
214 常用級(jí)數(shù)求和f (i) 16
215 期望E[X] 18

22 函數(shù)的漸近增長(zhǎng)率 19

23 “分治遞歸”求解 21

231 替換法 21
232 分治遞歸與遞歸樹 21
233 Master 定理 22
24 習(xí)題 23
第二部分從蠻力到分治
第3 章蠻力算法設(shè)計(jì) 31

31 蠻力選擇與查找 31
32 蠻力排序 32
321選擇排序 32
322插入排序 33
33 習(xí)題 35
第4 章分治排序 37
41 快速排序 37
411插入排序的不足 37
412快速排序的改進(jìn) 38
413最壞情況時(shí)間復(fù)雜度分析 39

414基于遞歸方程的平均情況時(shí)間復(fù)雜度分析 40
415基于指標(biāo)隨機(jī)變量的平均情況時(shí)間復(fù)雜度分析 41
42 合并排序 43
43 基于比較的排序的下界 44
431決策樹的引入 45
432比較排序的最壞情況時(shí)間復(fù)雜度的下界 45
433比較排序的平均情況時(shí)間復(fù)雜度的下界 46
44 習(xí)題 48
第5 章線性時(shí)間選擇 50
51 期望線性時(shí)間選擇 50

511選擇算法設(shè)計(jì) 50
512選擇算法分析 51
52 最壞情況線性時(shí)間選擇 52
521選擇算法設(shè)計(jì) 52
522選擇算法分析 53
53 習(xí)題 54
第6 章對(duì)數(shù)時(shí)間查找 57
61 折半查找 57
611經(jīng)典折半查找 57
612查找峰值 58
613計(jì)算√N(yùn) 59

62 平衡二叉搜索樹 59
621二叉搜索樹及其平衡性 59

622紅黑樹的定義 60
623紅黑樹的平衡性 62
63 習(xí)題 62
第7 章分治算法設(shè)計(jì)要素 65
71 分治算法的關(guān)鍵特征 65
72 計(jì)算逆序?qū)Φ膫€(gè)數(shù) 66

721依托于合并排序的逆序?qū)τ?jì)數(shù) 66
722原地的逆序?qū)τ?jì)數(shù) 67
73 整數(shù)乘法 68
731簡(jiǎn)單分治 69
732更精細(xì)的分治