了得網計算機/網絡_算法設計與分析第2版

內容簡介

本書是作者在多年從事算法設計與分析課程教學和研究的基礎上編寫而成，繫統地介紹了算法設計與分析的理論、方法和技術。內容圍繞兩條主線來組織。一條主線是介紹典範性的算法問題，如排序、選擇、圖遍歷等。另一條主線是介紹典範性的算法設計分析策略，如分治、貪心、動態規劃等算法設計策略和對手分析、平攤分析等算法分析策略。本書中兩條主線交替進行，每條主線又各自分為基本和進階兩部分。

作者簡介

黃宇，南京大學計算機科學與技術繫教授，博士生導師，主要研究方向為分布式算法、分布式繫統和軟件方法學。曾主持兩項國家自然科學基金項目，並作為主要成員參與了國家973計劃、國家自然科學基金創新群體項目等多項國家重大科研項目。2014年獲得南京大學登峰人纔支持計劃資助，2011年獲*技術發明獎。所指導的博士論文榮獲2016年中國計算機學會博士學位論文獎。已在IEEE Trans. on Computers、IEEE Trans. on Parallel and Distributed Systems、IEEE PerCom等重要國際期刊及會議上發表多篇論文。

前言
教學建議
部分計算模型
第1 章抽像的算法設計與分析........... 2

1.1 RAM 模型的引入................... 2

1.1.1 計算的基本概念................... 2

1.1.2計算模型的基本概念. . . . . . . .. .. . . . . 3
1.1.3RAM 模型........................ 3

1.1.4計算模型的選擇：易用性與精確性........................... 5
1.2 抽像算法設計...................... 6前言
教學建議
部分計算模型
第1 章抽像的算法設計與分析........... 2

1.1 RAM 模型的引入................... 2

1.1.1 計算的基本概念................... 2

1.1.2計算模型的基本概念. . . . . . . .. .. . . . . 3
1.1.3RAM 模型........................ 3

1.1.4計算模型的選擇：易用性與精確性........................... 5
1.2 抽像算法設計...................... 6

1.2.1 算法問題規約..................... 6

1.2.2 算法正確性證明：數學歸納法....... 7

1.3 抽像算法分析...................... 8

1.3.1 抽像算法的性能指標. . . . . . . .. .. . . . . 8
1.3.2 壞情況時間復雜度分析.......... 9

1.3.3 平均情況時間復雜度分析......... 10

1.4 習題. .. . . . . . . . .. .. .. .. . . . . . . . . . .. .. 11
第2 章從算法的視角重新審視數學的概念. . . . . . . . . . .. .. .. .. . . . . 14
2.1 數學運算背後的算法操作......... 14

2.1.1 取整. x . 和. x . . . . . . . . . . .. .. .. .. . 14
2.1.2 對數log n . . . . .. .. .. . . . . . . . . . .. .. . 14
2.1.3 階乘n!. . . . .. .. .. .. . . . . . . . . . .. .. . 15
2.1.4 常用級數求和.f (i). . . . . . .. .. .. .. 16
2.1.5 期望E[X] ....................... 18

2.2 函數的漸近增長率................ 19

2.3 “分治遞歸”求解................. 21

2.3.1 替換法. .. .. . . . . . . . . . .. .. .. .. . . . . 21
2.3.2 分治遞歸與遞歸樹.. . . . . . . . . . .. .. .21
2.3.3 Master 定理. .. .. .. . . . . . . . . . .. .. .. 22
2.4 習題. . . . . . . . .. .. .. . . . . . . . . . .. .. .. .. 23
第二部分從蠻力到分治
第3 章蠻力算法設計................... 31

3.1 蠻力選擇與查找. . . . . . .. .. .. . . . . . . . 31
3.2 蠻力排序.. . . . . . .. .. .. .. . . . . . . . . . .. 32
3.2.1選擇排序. . . .. .. .. .. . . . . . . . . . .. .. 32
3.2.2插入排序. . . .. .. .. .. . . . . . . . . . .. .. 33
3.3 習題. . . . . . . . .. .. .. . . . . . . . . . .. .. .. .. 35
第4 章分治排序.. .. .. .. . . . . . .. .. .. .. . . . 37
4.1 快速排序. . . . . . . .. .. .. .. . . . . . . . . . .. 37
4.1.1插入排序的不足. .. .. . . . . . . . . . .. .. 37
4.1.2快速排序的改進. .. .. . . . . . . . . . .. .. 38
4.1.3壞情況時間復雜度分析......... 39

4.1.4基於遞歸方程的平均情況時間復雜度分析. . . . . . .. .. .. . . . . . . . . . . 40
4.1.5基於指標隨機變量的平均情況時間復雜度分析. . . . . . .. .. .. . . . . . . . . . . 41
4.2 合並排序.. . . . . . .. .. .. .. . . . . . . . . . .. 43
4.3 基於比較的排序的下界. .. .. .. . . . . . 44
4.3.1決策樹的引入. . . . . . .. .. .. . . . . . . . . 45
4.3.2比較排序的壞情況時間復雜度的下界. . . . . .. .. .. .. . . . . . . . .. .. .. 45
4.3.3比較排序的平均情況時間復雜度的下界. . . . . .. .. .. .. . . . . . . . .. .. .. 46
4.4 習題. . . . . . . . .. .. .. . . . . . . . . . .. .. .. .. 48
第5 章線性時間選擇................... 50
5.1 期望線性時間選擇................ 50

5.1.1選擇算法設計. . . . . . .. .. .. . . . . . . . . 50
5.1.2選擇算法分析. . . . . . .. .. .. . . . . . . . . 51
5.2 壞情況線性時間選擇. .. .. .. . . . . . 52
5.2.1選擇算法設計. . . . . . .. .. .. . . . . . . . . 52
5.2.2選擇算法分析. .. . . . . . . . . . .. .. . . . . 53
5.3 習題. .. . . . . . . . .. .. .. .. . . . . . . . . . .. .. 54
第6 章對數時間查找................... 57
6.1 折半查找.. .. . . . . . . . .. .. .. .. . . . . . . . 57
6.1.1經典折半查找. .. . . . . . . . .. .. .. . . . . 57
6.1.2查找峰值. . . . . . . .. .. .. . . . . . . . . . .. 58
6.1.3計算√N ........................ 59

6.2 平衡二叉搜索樹. . . . . . . . .. .. .. . . . . . 59
6.2.1二叉搜索樹及其平衡性........... 59

6.2.2紅黑樹的定義. .. . . . . . . . . . .. .. . . . . 60
6.2.3紅黑樹的平衡性. .. .. .. .. . . . . . . . . . 62
6.3 習題. .. . . . . . . . .. .. .. .. . . . . . . . . . .. .. 62
第7 章分治算法設計要素. . . . . . . . . . .. .. .65
7.1 分治算法的關鍵特征. . . . . . . .. .. .. . 65
7.2 計算逆序對的個數................ 66

7.2.1依托於合並排序的逆序對計數.. .. . 66
7.2.2原地的逆序對計數.. .. . . . . . . . . . .. .67
7.3 整數乘法.. .. . . . . . . . .. .. .. .. . . . . . . . 68
7.3.1簡單分治. . . . . . . .. .. .. . . . . . . . . . .. 69
7.3.2更精細的分治.

前言

算法是計算的靈魂（spirit of computing），而算法設計與分析的基礎知識是計算機科學的基石。算法設計與分析的內容很豐富，可以從不同視角進行組織與闡述。一種視角是關注經典的算法問題，如排序、選擇、查找、圖遍歷等；另一種視角是關注經典的算法設計策略，如分治、貪心、動態規劃等。
根據這一“二維視角”，本書的核心內容分為四塊，如圖1 所示。從問題的視角看，主要有兩類問題。類為序相關的問題，包括基於比較的排序、選擇與查找；第二類為圖相關的問題，包括基本的圖遍歷問題以及小生成樹、短路徑等圖優化問題。從策略的視角看，主要有兩類策略。類為遍歷策略，包括線性表上的遍歷和圖上的遍歷；第二類為優化策略，在序相關的問題上主要體現為分治策略，在圖相關的問題上體現為貪心策略與動態規劃策略。

圖1 二維視角下的核心內容算法是計算的靈魂（spirit of computing），而算法設計與分析的基礎知識是計算機科學的基石。算法設計與分析的內容很豐富，可以從不同視角進行組織與闡述。一種視角是關注經典的算法問題，如排序、選擇、查找、圖遍歷等；另一種視角是關注經典的算法設計策略，如分治、貪心、動態規劃等。
根據這一“二維視角”，本書的核心內容分為四塊，如圖1 所示。從問題的視角看，主要有兩類問題。類為序相關的問題，包括基於比較的排序、選擇與查找；第二類為圖相關的問題，包括基本的圖遍歷問題以及小生成樹、短路徑等圖優化問題。從策略的視角看，主要有兩類策略。類為遍歷策略，包括線性表上的遍歷和圖上的遍歷；第二類為優化策略，在序相關的問題上主要體現為分治策略，在圖相關的問題上體現為貪心策略與動態規劃策略。

圖1 二維視角下的核心內容
上述核心內容是算法設計與分析中基礎的知識與典型的技術。以此為基礎，本書進一步討論更深入的算法設計與分析技術。一類是圍繞經典數據結構的算法設計與分析，另一類是進階的算法分析策略。此外，本書集中討論抽像的—— 與機器、實現語言無關的—— 算法設計與分析。為此，在主體內容之前，本書首先講解計算模型的基礎知識，它是後續抽像的算法設計與分析的基礎。本書的後介紹計算復雜性的基礎知識，試圖讓讀者在了解各類算法問題、學習各種算法設計與分析技術之後，對算法問題的難度有一個總體的認識。本書內容的總體結構如圖2所示。
本書的內容是作者在多年授課的過程中逐漸積澱而成的，因而它不是對算法設計與分析知識的一個百科全書式的覆蓋，而是對一些重點內容更專注的討論。本書的內容和組織方式是面向一個學期的授課而設計的。在授課形式方面，我們將課程分為主課與輔課兩種形式。主課主要圍繞典型的問題、經典的算法展開，而輔課則主要圍繞算法策略展開。若干次的主課講授形成一個階段，每一個階段結束後，通過一次輔課從策略的視角回顧近階段的一組算法，同時補充新的素材對相應的策略進行進一步的討論。

圖2 本書內容總體結構
在知識講授之外，實踐也是算法設計與分析課程的重要組成部分。算法課程的實踐分為兩類。一類是傳統的習題。本書習題大體按照這樣的順序給出：首先是緊扣書本知識的習題，例如一些簡單定理的證明、緊扣算法細節的一些問題等；其次是應用題，它需要讀者對一個具有一定現實意義的問題進行建模，並用書中的算法知識來解決問題。另一類是編程實現題。本書的應用題大都可以用於算法編程實現的訓練。在實際授課中，我們挑選了部分應用題作為編程實現題，並基於開源的OnlineJudge 平臺進行自動評測，取得了良好的效果。
本書的素材主要源自南京大學計算機繫本科生“算法設計與分析”課程的授課內容。其中一部分素材來源於共同授課的其他老師，包括前期負責講授主課並指導輔課教學的陳道蓄老師，以及後期共同分班講授這門課程的錢柱中、張勝、徐經緯老師。還有一部分素材來源於經典的算法教科書和國外大學的授課教師在其課程網站上發布的課程材料。另外，還要感謝“算法設計與分析”課程早期的兩位助教魏恆峰和楊怡玲，他們對大量的課程資料進行了整理與提煉。後要感謝上過這門課的學生，他們創造性的提問與解題時所犯的錯誤為本書提供了寶貴的素材。

商品搜索

商品分类

【醫學】

【各大出版社】