算法是計(jì)算機(jī)科學(xué)領(lǐng)域最重要的基石之一。算法是程序的靈魂，只有掌握了算法，才能輕松地駕馭程序開發(fā)。
算法詳解系列圖書共有4卷，本書是第1卷——算法基礎(chǔ)。本書共有6章，主要介紹了4個(gè)主題，它們分別是漸進(jìn)性分析和大O表示法、分治算法和主方法、隨機(jī)化算法以及排序和選擇。附錄A和附錄B簡單介紹了數(shù)據(jù)歸納法和離散概率的相關(guān)知識(shí)。本書的每一章均有小測(cè)驗(yàn)、章末習(xí)題和編程題，這為讀者的自我檢查以及進(jìn)一步學(xué)習(xí)提供了較多的便利。
本書為對(duì)算法感興趣的廣大讀者提供了豐富而實(shí)用的資料，能夠幫助讀者提升算法思維能力。本書適合計(jì)算機(jī)專業(yè)的高校教師和學(xué)生，想要培養(yǎng)和訓(xùn)練算法思維和計(jì)算思維的IT專業(yè)人士，以及在準(zhǔn)備面試的應(yīng)聘者和面試官閱讀參考。
算法詳解四部曲第一卷，詳解算法基礎(chǔ)，展現(xiàn)算法本質(zhì)
集斯坦福大學(xué)教授多年教學(xué)經(jīng)驗(yàn)，深入淺出，通俗易懂
算法是計(jì)算機(jī)科學(xué)的核心與靈魂。算法的應(yīng)用范圍極廣，網(wǎng)絡(luò)路由、計(jì)算基因組學(xué)、公鑰加密學(xué)和數(shù)據(jù)庫系統(tǒng)等的實(shí)現(xiàn)都需要算法。研究算法可以幫助我們成為更優(yōu)秀的程序員，可以讓我們具有更縝密的思維，并成功應(yīng)對(duì)各種場合的技術(shù)面試。
這是一本非常容易上手的算法入門圖書，它可作為程序員的學(xué)習(xí)用書，也適合想要學(xué)習(xí)算法和想提升算法思維能力的讀者閱讀。
本書主要包括以下內(nèi)容：
漸進(jìn)性分析；
大O表示法；
主方法；
快速分治算法；
隨機(jī)化算法；
排序算法；
選擇算法。
蒂姆·拉夫加登（Tim Roughgarden）是斯坦福大學(xué)計(jì)算機(jī)科學(xué)系的教授,也是該校管理科學(xué)和工程系的客座教授，他從2004年開始教授和研究算法。本書是他的《算法詳解》四部曲的第一卷，基于他從2012年開始定期舉行的在線算法課程編寫。
第 1章 緒論 1
1.1 為什么要學(xué)習(xí)算法 1
1.2 整數(shù)乘法 3
1.2.1 問題和解決方案 3
1.2.2 整數(shù)乘法問題 3
1.2.3 小學(xué)算法 4
1.2.4 操作數(shù)量的分析 5
1.2.5 還能做得更好嗎 5
1.3 Karatsuba乘法 6
1.3.1 一個(gè)具體的例子 6
1.3.2 一種遞歸算法 7
1.3.3 Karatsuba乘法 9
1.4 MergeSort算法 11
1.4.1 推動(dòng)力 11
1.4.2 排序 12
1.4.3 一個(gè)例子 13
1.4.4 偽碼 14
1.4.5 Merge子程序 15
1.5 MergeSort算法分析 16
1.5.1 Merge的運(yùn)行時(shí)間 17
1.5.2 MergeSort的運(yùn)行時(shí)間 18
1.5.3 定理1.2的證明 19
1.5.4 小測(cè)驗(yàn)1.1～1.2的答案 23
1.6 算法分析的指導(dǎo)原則 23
1.6.1 第 1個(gè)原則：最壞情況分析 24
1.6.2 第 2個(gè)原則：全局分析 25
1.6.3 第3個(gè)原則：漸進(jìn)性分析 26
1.6.4 什么是“快速”算法 27
1.7 本章要點(diǎn) 28
1.8 習(xí)題 29
挑戰(zhàn)題 31
編程題 31
第 2章 漸進(jìn)性表示法 32
2.1 要旨 32
2.1.1 推動(dòng)力 32
2.1.2 高級(jí)思維 33
2.1.3 4個(gè)例子 34
2.1.4 小測(cè)驗(yàn)2.1～2.4的答案 38
2.2 大O表示法 40
2.2.1 文本定義 40
2.2.2 圖形定義 40
2.2.3 數(shù)學(xué)定義 41
2.3 兩個(gè)基本例子 42
2.3.1 k階多項(xiàng)式是O(nk) 42
2.3.2 k階多項(xiàng)式不是O(nk-1) 43
2.4 大Ω和大 表示法 44
2.4.1 大Ω表示法 44
2.4.2 大 表示法 45
2.4.3 小O表示法 46
2.4.4 漸進(jìn)性表示法的來源 47
2.4.5 小測(cè)驗(yàn)2.5的答案 48
2.5 其他例子 48
2.5.1 在指數(shù)中添加一個(gè)常數(shù) 48
2.5.2 指數(shù)乘以一個(gè)常數(shù) 49
2.5.3 最大值vs.和 49
2.6 本章要點(diǎn) 50
2.7 習(xí)題 51
第3章 分治算法 53
3.1 分治法規(guī)范 53
3.2 以O(shè)(n log n)時(shí)間計(jì)數(shù)逆序?qū)?54
3.2.1 問題 54
3.2.2 一個(gè)例子 54
3.2.3 協(xié)同篩選 55
3.2.4 窮舉搜索法 55
3.2.5 分治法 56
3.2.6 高級(jí)算法 57
3.2.7 關(guān)鍵思路：站在MergeSort的肩膀上 57
3.2.8 重溫Merge 58
3.2.9 Merge和分離逆序?qū)?60
3.2.10 Merge_and_CountSplitInv 61
3.2.11 正確性 61
3.2.12 運(yùn)行時(shí)間 62
3.2.13 小測(cè)驗(yàn)3.1～3.2的答案 62
3.3 Strassen的矩陣相乘算法 63
3.3.1 矩陣相乘 63
3.3.2 例子（n = 2） 64
3.3.3 簡單算法 64
3.3.4 分治法 65
3.3.5 節(jié)省一個(gè)遞歸調(diào)用 67
3.3.6 細(xì)節(jié) 68
3.3.7 小測(cè)驗(yàn)3.3的答案 69
*3.4 O(n log n)時(shí)間的最近點(diǎn)對(duì)（Closest Pair）算法 70
3.4.1 問題 70
3.4.2 熱身：1D情況 71
3.4.3 預(yù)處理 71
3.4.4 一種分治方法 72
3.4.5 一個(gè)微妙的變化 74
3.4.6 ClosestSplitPair 74
3.4.7 正確性 76
3.4.8 輔助結(jié)論3.3（a）的證明 77
3.4.9 輔助結(jié)論3.3（b）的證明 78
3.4.10 小測(cè)驗(yàn)3.4的答案 80
3.5 本章要點(diǎn) 80
3.6 習(xí)題 81
挑戰(zhàn)題 81
編程題 82
第4章 主方法 83
4.1 重溫整數(shù)乘法 83
4.1.1 RecIntMult算法 84
4.1.2 Karatsuba算法 84
4.1.3 比較遞歸過程 85
4.2 形式聲明 86
4.2.1 標(biāo)準(zhǔn)遞歸過程 86
4.2.2 主方法的陳述和討論 87
4.3 6個(gè)例子 88
4.3.1 重溫MergeSort 89
4.3.2 二分搜索 89
4.3.3 整數(shù)乘法的遞歸算法 90
4.3.4 Karatsuba乘法 90
4.3.5 矩陣乘法 91
4.3.6 一個(gè)虛構(gòu)的遞歸過程 92
4.3.7 小測(cè)驗(yàn)4.2～4.3的答案 93
*4.4 主方法的證明 94
4.4.1 前言 94
4.4.2 重溫遞歸樹 95
4.4.3 單層所完成的工作 96
4.4.4 各層累計(jì) 97
4.4.5 正義與邪惡：需要考慮3種情況 98
4.4.6 預(yù)告運(yùn)行時(shí)間上界 99
4.4.7 最后的計(jì)算：第 一種情況 100
4.4.8 迂回之旅：幾何級(jí)數(shù) 101
4.4.9 最后的計(jì)算：第二種情況和第三種情況 102
4.4.10 小測(cè)驗(yàn)4.4～4.5的答案 103
4.5 本章要點(diǎn) 103
4.6 習(xí)題 104
第5章 快速排序（QuickSort） 107
5.1 概述 107
5.1.1 排序 108
5.1.2 根據(jù)基準(zhǔn)元素進(jìn)行劃分 108
5.1.3 高級(jí)描述 110
5.1.4 內(nèi)容前瞻 110
5.2 圍繞基準(zhǔn)元素進(jìn)行劃分 111
5.2.1 簡易方法 111
5.2.2 原地實(shí)現(xiàn)：高級(jí)計(jì)劃 112
5.2.3 例子 113
5.2.4 Partition子程序的偽碼 115
5.2.5 QuickSort的偽碼 117
5.3 良好的基準(zhǔn)元素的重要性 117
5.3.1 ChoosePivot的簡單實(shí)現(xiàn) 118
5.3.2 ChoosePivot的過度實(shí)現(xiàn) 118
5.3.3 小測(cè)驗(yàn)5.1～5.2的答案 119
5.4 隨機(jī)化的QuickSort 121
5.4.1 ChoosePivot的隨機(jī)化實(shí)現(xiàn) 121
5.4.2 隨機(jī)化QuickSort的運(yùn)行時(shí)間 122
5.4.3 直覺：隨機(jī)基準(zhǔn)元素為什么很好 123
*5.5 隨機(jī)化QuickSort的分析 124
5.5.1 預(yù)備工作 125
5.5.2 分解藍(lán)圖 126
5.5.3 應(yīng)用藍(lán)圖 128
5.5.4 計(jì)算比較的概率 130
5.5.5 最后的計(jì)算 132
5.5.6 小測(cè)驗(yàn)5.3的答案 133
*5.6 排序需要 (n log n)的比較 134
5.6.1 基于比較的排序算法 134
5.6.2 具有更強(qiáng)前提的更快速排序 135
5.6.3 定理5.5的證明 136
5.7 本章要點(diǎn) 138
5.8 習(xí)題 139
挑戰(zhàn)題 140
編程題 141
第6章 線性時(shí)間級(jí)的選擇 142
6.1 RSelect算法 143
6.1.1 選擇問題 143
6.1.2 簡化為排序 144
6.1.3 分治法 145
6.1.4 RSelect的偽碼 146
6.1.5 RSelect的運(yùn)行時(shí)間 147
6.1.6 小測(cè)驗(yàn)6.1～6.2的答案 149
*6.2 RSelect的分析 150
6.2.1 根據(jù)階段追蹤進(jìn)展 150
6.2.2 簡化為擲硬幣 151
6.2.3 綜合結(jié)論 153
*6.3 DSelect算法 154
6.3.1 基本思路：中位的中位元素 154
6.3.2 DSelect的偽碼 155
6.3.3 理解DSelect 156
6.3.4 DSelect的運(yùn)行時(shí)間 157
*6.4 DSelect的分析 159
6.4.1 遞歸調(diào)用之外所完成的工作 159
6.4.2 一個(gè)粗略的遞歸過程 159
6.4.3 30-70輔助結(jié)論 160
6.4.4 解析遞歸過程 163
6.4.5 先猜后驗(yàn)方法 164
6.5 本章要點(diǎn) 166
6.6 本章習(xí)題 166
挑戰(zhàn)題 167
編程題 168
附錄A 快速回顧數(shù)學(xué)歸納法 169
附錄B 快速回顧離散概率 173
書單推薦
