Hello 算法

靳宇栋（@krahets）

前华为高级算法工程师，上海交通大学硕士，西安交通大学本科，专注于3D重建与渲染、3D生成算法的研究。曾在VEX机器人世界锦标赛拔得头筹、全球人工智能创新大赛一等奖。喜欢在开源社区分享知识，作品的GitHub Star超60,000，订阅人数超460,000。

序

前言

第 1章 初識算法 1

1.1 算法無處不在 1

1.2 算法是什麽 5

1.2.1 算法定義 5

1.2.2 數據結構定義 5

1.2.3 數據結構與算法的關系 5

1.3 小結 7

第 2章 復雜度分析 9

2.1 算法效率評估 9

2.1.1 實際測試 9

2.1.2 理論估算 10

2.2 迭代與遞歸 10

2.2.1 迭代 11

2.2.2 遞歸 13

2.2.3 兩者對比 18

2.3 時間復雜度 19

2.3.1 統計時間增長趨勢 20

2.3.2 函數漸近上界 21

2.3.3 推算方法 22

2.3.4 常見類型 23

2.3.5 最差、最佳、平均時間復雜度 30

2.4 空間復雜度 32

2.4.1 算法相關空間 32

2.4.2 推算方法 33

2.4.3 常見類型 34

2.4.4 權衡時間與空間 38

2.5 小結 39

第3章 數據結構 42

3.1 數據結構分類 42

3.1.1 邏輯結構：線性與非線性 42

3.1.2 物理結構：連續與分散 43

3.2 基本數據類型 45

3.3 數字編碼* 46

3.3.1 原碼、反碼和補碼 46

3.3.2 浮點數編碼 49

3.4 字符編碼* 50

3.4.1 ASCII字符集 50

3.4.2 GBK字符集 51

3.4.3 Unicode字符集 51

3.4.4 UTF-8編碼 53

3.4.5 編程語言的字符編碼 54

3.5 小結 55

第4章 數組與鏈表 58

4.1 數組 58

4.1.1 數組常用操作 58

4.1.2 數組的優點與局限性 62

4.1.3 數組典型應用 63

4.2 鏈表 63

4.2.1 鏈表常用操作 64

4.2.2 數組與鏈表對比 67

4.2.3 常見鏈表類型 67

4.2.4 鏈表典型應用 68

4.3 列表 69

4.3.1 列表常用操作 69

4.3.2 列表實現 71

4.4 內存與緩存* 73

4.4.1 電腦存儲設備 73

4.4.2 數據結構的內存效率 75

4.4.3 數據結構的緩存效率 75

4.5 小結 76

第5章 棧與隊列 81

5.1 棧 81

5.1.1 棧的常用操作 81

5.1.2 棧的實現 82

5.1.3 兩種實現對比 86

5.1.4 棧的典型應用 87

5.2 隊列 87

5.2.1 隊列常用操作 88

5.2.2 隊列實現 89

5.2.3 隊列典型應用 94

5.3 雙向隊列 95

5.3.1 雙向隊列常用操作 95

5.3.2 雙向隊列實現* 96

5.3.3 雙向隊列應用 104

5.4 小結 104

第6章 哈希表 107

6.1 哈希表 107

6.1.1 哈希表常用操作 108

6.1.2 哈希表簡單實現 109

6.1.3 哈希沖突與擴容 111

6.2 哈希沖突 113

6.2.1 鏈式地址 113

6.2.2 開放尋址 116

6.2.3 編程語言的選擇 120

6.3 哈希算法 120

6.3.1 哈希算法的目標 121

6.3.2 哈希算法的設計 122

6.3.3 常見哈希算法 124

6.3.4 數據結構的哈希值 124

6.4 小結 125

第7章 樹 129

7.1 二叉樹 129

7.1.1 二叉樹常見術語 129

7.1.2 二叉樹基本操作 131

7.1.3 常見二叉樹類型 132

7.1.4 二叉樹的退化 134

7.2 二叉樹遍歷 135

7.2.1 層序遍歷 135

7.2.2 前序、中序、後序遍歷 136

7.3 二叉樹數組表示 138

7.3.1 表示完美二叉樹 138

7.3.2 表示任意二叉樹 139

7.3.3 優點與局限性 142

7.4 二叉搜索樹 142

7.4.1 二叉搜索樹的操作 143

7.4.2 二叉搜索樹的效率 151

7.4.3 二叉搜索樹常見應用 151

7.5 AVL樹* 152

7.5.1 AVL樹常見術語 153

7.5.2 AVL樹旋轉 154

7.5.3 AVL樹常用操作 160

7.5.4 AVL樹典型應用 161

7.6 小結 162

第8章 堆 165

8.1 堆 165

8.1.1 堆的常用操作 166

8.1.2 堆的實現 167

8.1.3 堆的常見應用 177

8.2 建堆操作 177

8.2.1 借助入堆操作實現 177

8.2.2 通過遍歷堆化實現 178

8.2.3 復雜度分析 178

8.3 Top-k問題 180

8.3.1 方法一：遍歷選擇 180

8.3.2 方法二：排序 180

8.3.3 方法三：堆 181

8.4 小結 182

第9章 圖 184

9.1 圖 184

9.1.1 圖的常見類型與術語 185

9.1.2 圖的表示 186

9.1.3 圖的常見應用 188

9.2 圖的基礎操作 188

9.2.1 基於鄰接矩陣的實現 188

9.2.2 基於鄰接表的實現 192

9.2.3 效率對比 196

9.3 圖的遍歷 196

9.3.1 廣度優先遍歷 196

9.3.2 深度優先遍歷 198

9.4 小結 200

第 10章 搜索 203

10.1 二分查找 203

10.1.1 區間表示方法 207

10.1.2 優點與局限性 208

10.2 二分查找插入點 209

10.2.1 無重復元素的情況 209

10.2.2 存在重復元素的情況 210

10.3 二分查找邊界 212

10.3.1 查找左邊界 212

10.3.2 查找右邊界 212

10.4 哈希優化策略 214

10.4.1 線性查找：以時間換空間 214

10.4.2 哈希查找：以空間換時間 215

10.5 重識搜索算法 217

10.5.1 暴力搜索 217

10.5.2 自適應搜索 218

10.5.3 搜索方法選取 218

10.6 小結 220

第 11章 排序 222

11.1 排序算法 222

11.1.1 評價維度 222

11.1.2 理想排序算法 223

11.2 選擇排序 224

11.3 冒泡排序 229

11.3.1 算法流程 231

11.3.2 效率優化 232

11.3.3 算法特性 233

11.4 插入排序 233

11.4.1 算法流程 234

11.4.2 算法特性 235

11.4.3 插入排序的優勢 235

11.5 快速排序 235

11.5.1 算法流程 239

11.5.2 算法特性 240

11.5.3 快速排序為什麽快 240

11.5.4 基準數優化 241

11.5.5 尾遞歸優化 242

11.6 歸並排序 242

11.6.1 算法流程 243

11.6.2 算法特性 248

11.6.3 鏈表排序 248

11.7 堆排序 249

11.7.1 算法流程 249

11.7.2 算法特性 250

11.8 桶排序 250

11.8.1 算法流程 251

11.8.2 算法特性 252

11.8.3 如何實現平均分配 252

11.9 計數排序 253

11.9.1 簡單實現 254

11.9.2 完整實現 255

11.9.3 算法特性 256

11.9.4 局限性 256

11.10 基數排序 257

11.10.1 算法流程 257

11.10.2 算法特性 259

11.11 小結 259

第 12章 分治 263

12.1 分治算法 263

12.1.1 如何判斷分治問題 264

12.1.2 通過分治提升效率 264

12.1.3 分治常見應用 266

12.2 分治搜索策略 267

12.3 構建二叉樹問題 269

12.4 漢諾塔問題 273

12.5 小結 280

第 13章 回溯 282

13.1 回溯算法 282

13.1.1 嘗試與回退 283

13.1.2 剪枝 288

13.1.3 框架代碼 289

13.1.4 常用術語 291

13.1.5 優點與局限性 291

13.1.6 回溯典型例題 292

13.2 全排列問題 292

13.2.1 無相等元素的情況 293

13.2.2 考慮相等元素的情況 295

13.3 子集和問題 298

13.3.1 無重復元素的情況 298

13.3.2 考慮重復元素的情況 302

13.4 n 皇後問題 304

13.5 小結 308

第 14章 動態規劃 310

14.1 初探動態規劃 310

14.1.1 方法一：暴力搜索 311

14.1.2 方法二：記憶化搜索 313

14.1.3 方法三：動態規劃 314

14.1.4 空間優化 316

14.2 動態規劃問題特性 316

14.2.1 最優子結構 316

14.2.2 無後效性 319

14.3 動態規劃解題思路 321

14.3.1 問題判斷 321

14.3.2 問題求解步驟 322

14.4 0-1 背包問題 332

14.5 完全背包問題 343

14.5.1 完全背包問題 344

14.5.2 零錢兌換問題 I348

14.5.3 零錢兌換問題II 350

14.6 編輯距離問題 352

14.7 小結 356

第 15章 貪心 359

15.1 貪心算法 359

15.1.1 貪心算法的優點與局限性 360

15.1.2 貪心算法特性 361

15.1.3 貪心算法解題步驟 362

15.1.4 貪心算法典型例題 363

15.2 分數背包問題 363

15.3 最大容量問題 366

15.4 最大切分乘積問題 373

15.5 小結 377

附錄A 術語表 379