算法筆記 算法笔记

本書介紹了若乾常見算法，既包括排序、哈希等基礎算法，也包括無約束優化、插值與擬合等數值計算方法。本書在介紹算法的同時，結合了作者自己對數學背景、應用場景的理解，便於讀者把握算法的核心思想。本書盡可能地避開了以應試為導向的灌輸式講解，力求引起讀者的興趣並擴大其視野，例如在介紹哈希時，講解瞭如何將哈希的算法思想運用於相似性搜索、負載均衡等多個實際問題中；又如在介紹高斯消去法時，講解了相關的數學理論及編程實現上的具體技巧，並將其運用於對大規模稀疏線性方程組的求解，等等。本書面向有一定高等數學、編程語言基礎及對算法有初步瞭解的讀者，包括高等院校的學生、程序員、算法分析人員及設計人員等，旨在幫助讀者進一步學習算法，理解與算法相關的理論基礎和應用實例。

刁瑞，畢業於中國科學院數學與系統科學研究院，博士期間的研究方向為最優化方法。曾獲2009年英特爾杯全國計算機多核程序設計大賽第1名，以及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