編輯推薦

l 內容詳細，涉及排序、哈希、動態規劃與近似算法、高斯消去法、圖論與綫性規劃、無約束優化、迭代法、插值與擬閤等。

l 重點講解算法的核心思想。

l 注重用算法解決實際問題，如相似性搜索、負載均衡等。

l 詳細講解算法涉及的數學理論及編程實現上的具體技巧。

l 避開瞭以應試為導嚮的灌輸式講解。

l 語言精練，無廢話；視點獨到，不復製。

內容簡介

《算法筆記》介紹瞭若乾常見算法，既包括排序、哈希等基礎算法，也包括無約束優化、插值與擬閤等數值計算方法。《算法筆記》在介紹算法的同時，結閤瞭作者自己對數學背景、應用場景的理解，便於讀者把握算法的核心思想。《算法筆記》盡可能地避開瞭以應試為導嚮的灌輸式講解，力求引起讀者的興趣並擴大其視野，例如在介紹哈希時，講解瞭如何將哈希的算法思想運用於相似性搜索、負載均衡等多個實際問題中；又如在介紹高斯消去法時，講解瞭相關的數學理論及編程實現上的具體技巧，並將其運用於對大規模稀疏綫性方程組的求解，等等。

《算法筆記》麵嚮有一定高等數學、編程語言基礎及對算法有初步瞭解的讀者，包括高等院校的學生、程序員、算法分析人員及設計人員等，旨在幫助讀者進一步學習算法，理解與算法相關的理論基礎和應用實例。

作者簡介

刁瑞，畢業於中國科學院數學與係統科學研究院，博士期間的研究方嚮為zui優化方法。曾獲2009年英特爾杯全國計算機多核程序設計大賽冠軍，以及2011年KDD Cup第2名等。

謝妍，畢業於中國科學院數學與係統科學研究院，博士期間的研究方嚮為並行有限元計算。曾在微軟互聯網工程院從事搜索研發相關工作。

目錄

第1 章 排序1

1.1 比較排序. 1

1.1.1 梳排序. 2

1.1.2 堆排序. 4

1.1.3 歸並排序 5

1.1.4 快速排序 8

1.1.5 內省排序 10

1.1.6 Timsort 11

1.2 非比較排序. 14

1.2.1 桶排序. 14

1.2.2 基數排序 15

1.3 總結 16

第2 章 哈希17

2.1 基本概念與實現.. 17

2.1.1 哈希函數 17

2.1.2 哈希錶. 19

2.2 哈希的應用. 20

2.2.1 相似性搜索.. 20

2.2.2 信息安全 23

2.2.3 比特幣. 25

2.2.4 負載均衡 26

第3 章 動態規劃與近似算法29

3.1 基本概念. 29

3.1.1 動態規劃 29

3.1.2 計算復雜性.. 30

3.2 字符串的編輯距離. 30

3.2.1 問題引入 31

3.2.2 動態規劃算法.. 33

3.2.3 滾動數組優化.. 35

3.2.4 上界限製 36

3.2.5 解的迴溯 37

3.2.6 分治算法 38

3.2.7 多個字符串的編輯距離. 41

3.3 子集和問題. 43

3.3.1 問題引入 43

3.3.2 子集和問題的動態規劃算法 43

3.3.3 最優化問題.. 44

3.3.4 滾動數組的技巧. 45

第4 章 高斯消去法59

4.1 問題引入. 59

4.2 矩陣編程基礎 60

4.3 三角方程組. 62

4.3.1 三角矩陣 62

4.3.2 三角矩陣的存儲. 63

4.3.3 三角方程組求解. 64

4.4 高斯消去法. 66

4.4.1 算法概述 66

4.4.2 高斯變換 68

4.4.3 LU 分解.. 69

4.4.4 Cholesky 分解.. 70

4.5 主元選擇. 71

4.5.1 列選主元 71

4.5.2 全選主元 73

4.5.3 主元與計算量.. 74

4.6 稀疏矩陣的編程基礎 75

4.6.1 稀疏嚮量 76

4.6.2 稀疏矩陣 79

4.7 稀疏LU 分解. 82

4.7.1 Markowitz 算法.. 82

4.7.2 最小度算法.. 83

第5 章 圖論與綫性規劃86

5.1 綫性規劃基礎 86

5.1.1 Fourier Motzkin 消去法. 89

5.1.2 基 91

5.1.3 單純形方法.. 93

5.1.4 對偶.. 95

5.2 全單模矩陣. 98

5.2.1 關聯矩陣 98

5.2.2 全單模矩陣.. 99

5.2.3 全單模矩陣與圖論 100

5.2.4 全單模矩陣與綫性規劃. 103

5.3 圖論中的經典問題. 104

5.3.1 單源最短路問題. 104

5.3.2 二分圖的最大匹配與最小覆蓋問題 106

5.3.3 最大流與最小割問題.. 108

5.4 延伸閱讀. 109

5.4.1 逐步綫性規劃.. 109

5.4.2 半正定規劃.. 111

第6 章 無約束優化113

6.1 單峰函數的最值.. 114

6.1.1 三分法. 115

6.1.2 對分法. 115

6.1.3 黃金分割法.. 116

6.1.4 小結.. 117

6.2 無導數優化方法.. 118

6.2.1 模式搜索法.. 118

6.2.2 坐標下降法.. 119

6.2.3 代理模型法.. 120

6.3 導數優化方法 121

6.3.1 綫搜索. 122

6.3.2 梯度下降法.. 123

6.3.3 共軛梯度法.. 124

6.3.4 牛頓法. 127

6.3.5 擬牛頓法 128

6.4 最小二乘. 132

6.4.1 綫性最小二乘.. 133

6.4.2 非綫性最小二乘. 133

第7 章 迭代法136

7.1 綫性方程組的迭代法 136

7.1.1 一階定常格式迭代法.. 136

7.1.2 Krylov 子空間算法 142

7.1.3 無約束優化方法. 147

7.2 非綫性方程組的迭代法 147

7.2.1 不動點迭代.. 148

7.2.2 Newton-Raphson 迭代. 149

7.2.3 無約束優化方法. 152

第8 章 插值與擬閤153

8.1 插值 153

8.1.1 常見的插值算法. 154

8.1.2 插值的應用.. 158

8.2 擬閤 163

8.2.1 常見的擬閤算法. 164

8.2.2 擬閤的應用.. 166

參考文獻169

前言/序言

本書取名“算法筆記”，主要源自作者在中國科學院讀書期間學習算法時的體會，可以作為現有算法教科書的補充。本書討論瞭計算機算法相關的若乾話題，在介紹算法的同時結閤瞭作者自己對數學背景、應用場景的理解，便於讀者把握算法的核心思想。閱讀本書需要有一定的數學基礎和算法基礎。

許多經典的算法教科書都詳盡地介紹瞭算法的各個知識點，但在覆蓋麵廣的同時難免會忽略許多細節問題。例如，哪些算法真正值得運用到實際問題中，算法有哪些變種值得我們瞭解，算法背後有哪些數學理論支撐，等等。

本書共包括8 章。各章中除瞭講解基本知識，還迴答瞭許多相關的有趣問題。

l 排序：排序算法有很多種，在比較流行的編程語言中都有提供排序算法的庫函數，直接調用這些庫函數會非常簡單。但它們所使用的算法為何有效，這些算法與一些經典的排序算法又有什麼區彆？

l 哈希：在講解哈希算法時一般主要介紹哈希函數的作用及哈希錶的不同實現方法。但將哈希函數運用於不同的問題時，最為巧妙的地方在於哈希函數的設計。對於不同領域的問題，哈希函數都有哪些有趣的形式？

l 動態規劃與近似算法：通常這兩類算法並不會放在一起去探討。在麵對不同復雜性的問題時，它們會有怎樣的互補作用？

l 高斯消去法：算法的基本過程是很簡單的，但在實際使用中遠遠沒有那麼簡單。如何保持計算的穩定性？如何解決稀疏矩陣的計算效率問題？

l 圖論與綫性規劃：圖論中的許多問題都可以用綫性規劃去解決。圖論中的一些經典結論實質上也可以用綫性規劃的相關定理去解釋。綫性規劃作為一個更一般的工具，如何用於處理圖論問題？

l 無約束優化：無約束優化主要用於求解函數的最大值或最小值的問題。常用的這些方法為何有效？它們之間的差彆在哪裏？

l 迭代法：常見的迭代算法都有哪些？它們為什麼有效？

l 插值與擬閤：插值與擬閤的思想是什麼？有什麼異同？如何運用於圖像處理？

讀者可以發現，本書不僅指齣瞭哪些算法可以解決問題，還指齣瞭哪些算法可以更好地解決問題。這有助於我們對算法的深入理解。

由於作者水平有限，書中難免有錯誤和不足之處，歡迎讀者批評和指正。

刁瑞、謝妍

2016 年7 月

不錯，講解很到位，互聯網架構中需要的幾個中間件項目深度剖析

換貨已經收到，包裝完好。大略看瞭一下書籍內容，從實例入手，值得一讀。

書上為什麼沒有包書的塑料包裝，其他書都有！

很不錯，贊(/≧▽≦/)

慢慢啃吧，一時半會看不完

寫的還算不錯，整天把握住瞭，能學到東西。

開始看瞭，還不錯！！

618買的，很實惠，400-300，400-280，優惠很大，就是400-300的券不好搶。趁機會拿之前喜歡的書。快遞速度超快。

寶貝今天收到瞭，與圖片描述一緻，價格實惠，質量還不錯，值得擁有，挺滿意這次購物，下次還會再光顧的。