《算法分析導論（第2版）》是2018年電子工業出版社出版圖書，作者是常青，左飛。
基本介紹
- 中文名：算法分析導論（第2版）
- 作者：常青，左飛
- 出版社：電子工業出版社
- 出版時間：2018年11月
- 頁數：424 頁
- 定價：128 元
- 開本：16 開
- ISBN：9787121353680
內容簡介,圖書目錄,
內容簡介
本書全面介紹了算法的數學分析所涉及的主要技術。涵蓋的內容來自經典的數學課題（包括離散 數學、初等實分析、組合數學），以及經典的計算機科學課題（包括算法和數據結構）。本書的重點是“平均情況”或“機率性”分析，書中也論述了“最差情況”或“複雜性”分析所需的基本數學工具。本書第1 版為行業代表性著作，第2 版不僅對書中圖片和代碼進行了更新，還補充了新章節。全書共9 章，第1 章是導論；第2～5 章介紹數學方法；第6～9 章介紹組合結構及其在算法分析中的套用。除每章包含的大量習題以及參考文獻外，本書特設配套免費學習網站，為讀者提供了很多關於算法分析的補充材料，包括課件和相關網站的連結，幫助讀者提高學習興趣，完成更深入的學習。
圖書目錄
第 1章算法分析 ............... 1
1.1 為什麼要做算法分析 ..........................................................1
1.2 算法理論 ..................3
1.3 算法分析概述 ..........8
1.4 平均情況分析 ........10
1.5 實例：快速排序算法的分析 ............................................12
1.6 漸近近似 ................ 18
1.7 分布 ........................ 20
1.8 隨機算法 ................ 22
參考文獻 ......................... 25
第 2章遞歸關係 ............. 28
2.1 基本性質 ................ 29
2.2 一階遞歸 ................ 33
2.3 一階非線性遞歸 ....35
2.4 高階遞歸 ................ 38
2.5 求解遞歸的方法 ....42
2.6 二分分治遞歸和二進制數 ................................................49
2.7 一般的分治遞歸 ....57
參考文獻 ......................... 62
第 3章母函式 .................. 64
3.1 普通型母函式 ........65
算法分析導論（第 2版）
3.2 指數型母函式 .........69
3.3 利用母函式求解遞歸 ........................................................72
3.4 母函式的展開 .........79
3.5 利用母函式進行變換 ........................................................82
3.6 關於母函式的函式方程 ....................................................84
3.7 利用 OGF求解三項中值 Quicksort遞歸.........................87
3.8 利用母函式計數 .....89
3.9 機率母函式 .............93
3.10 雙變數母函式 .......96
3.11特殊函式.............101
參考文獻........................107
第 4章漸近逼近 ........... 109
4.1 漸近逼近的概念 ...111
4.2 漸近展開式 ...........116
4.3 處理漸近展開式 ...123
4.4 有限和的漸近逼近 ..........................................................129
4.5 歐拉-麥克勞林求和 ........................................................131
4.6 二元漸近...............137
4.7 拉普拉斯方法 .......149
4.8 算法分析中的“正態”舉例 ..........................................152
4.9 算法分析中的“泊松”舉例 ..........................................155
參考文獻........................159
第 5章分析組合 ........... 161
5.1 正式的基礎 ...........162
5.2 無標記類的符號方法 ......................................................163
5.3 有標記類的符號方法 ......................................................169
5.4 參數的符號方法 ...177
5.5 母函式係數逼近 ...182
參考文獻........................188
第 6章樹........................ 189
6.1 二叉樹...................190
目錄 XV
6.2 森林和樹 .............. 192
6.3 樹和二叉樹的組合等價 ..................................................194
6.4 樹的性質 .............. 200
6.5 樹算法的例子 ......204
6.6 二叉搜尋樹 .......... 207
6.7 隨機 Catalan樹 .... 211
6.8 二叉搜尋樹中的路徑長度 .............................................. 216
6.9 隨機樹的附加參數 .........................................................219
6.10 高度 .................... 223
6.11樹屬性在平均情況下的結果總結 ................................229
6.12 拉格朗日反演 ....230
6.13 無序樹 ................ 233
6.14 標記樹 ................ 242
6.15 其他類型的樹 ....245
參考文獻 ....................... 253
