《算法导论》读书笔记（总纲）

「爱情、让人受尽委屈。」 2022-10-22 13:53 238阅读 0赞

# 《算法导论》读书笔记（总纲） #

> 介绍：
> 
> \[PDF、视频、代码、笔记记录\]
> 
> [简书：算法导论][Link 1]

算法（algorithm）简单来说就是定义良好的计算机过程，它取一个或一组值作为输入，并产生出一个或一组值作为输出。即算法就是一系列的计算步骤，用来将输入数据转换成输出数据。

书中有一句话非常好：  
　　Having a solid base of algorithm knowledge and technique is one characteristic that separates the truly skilled programmers from the novices.

是否具有扎实的算法知识和技术基础，是区分真正熟练的程序员与新手的一项重要特征。  
　　![在这里插入图片描述][resize_m_lfit_w_962_pic_center]

### 第一部分（Part I） 基础（Foundations） ###

第1章 计算中算法的角色（The Role of Algorithms in Computing）  
第2章 开始（Getting Started）  
第3章 函数的增长率（Growth of Functions）  
第4章 递归（Recurrences）  
第5章 概率分析与随机化算法（Probabilistic Analysis and Randomized Algorithms）

### 第二部分（Part II） 排序与顺序统计量（Sorting and Order Statistics） ###

第6章 堆排序（Heapsort）  
第7章 快速排序（Quicksort）  
第8章 线性时间中的排序（Sorting in Linear Time）  
第9章 中值与顺序统计（Medians and Order Statistics）

### 第三部分（Part III） 数据结构（Data Structures） ###

第10章 基本的数据结构（Elementary Data Structures）  
第11章 散列表（Hash Tables）  
第12章 二叉查找树（Binary Search Trees）  
第13章 红-黑树（Red-Black Trees）  
第14章 扩充的数据结构（Augmenting Data Structures）

### 第四部分（Part IV） 高级设计与分析技术（Advanced Design and Analysis Techniques） ###

第15章 动态规划（Dynamic Programming）  
第16章 贪婪算法（Greedy Algorithms）  
第17章 分摊分析（Amortized Analysis）

### 第五部分（Part V） 高级的数据结构（Advanced Data Structures） ###

第18章 B-树（B-Trees）  
第19章 二项式堆（Binomial Heaps）  
第20章 斐波纳契堆（Fibonacci Heaps）  
第21章 不相交集的数据结构（Data Structures for Disjoint Sets）

### 第六部分（Part VI） 图算法（Graph Algorithms） ###

第22章 基本的图算法（Elementary Graph Algorithms）  
第23章 最小生成树（Minimum Spanning Trees）  
第24章 单源最短路径（Single-Source Shortest Paths）  
第25章 全对的最短路径（All-Pairs Shortest Paths）  
第26章 最大流（Maximum Flow）

### 第七部分（Part VII） 算法问题选编（Selected Topics） ###

第27章 排序网络（Sorting Networks）  
第28章 矩阵运算（Matrix Operations）  
第29章 线性规划（Linear Programming）  
第30章 多项式与快速傅里叶变换（Polynomials and the FFT）  
第31章 数论算法（Number-Theoretic Algorithms）  
第32章 字符串匹配（String Matching）  
第33章 计算几何学（Computational Geometry）  
第34章 NP-完备性（NP-Completeness）  
第35章 近似算法（Approximation Algorithms）

### 第八部分（Part VIII） 附录：数学基础知识（Mathematical Background） ###

附录A 求和（Summations）  
附录B 集合等离散数学内容（Sets, Etc.）  
附录C 计数与概率（Counting and Probability）  
附录D 矩阵（Matrix）

[Link 1]: https://www.jianshu.com/p/9e8af45a99d6
[resize_m_lfit_w_962_pic_center]: /images/20221022/6870e4c9a981490fadb6b9250a764570.png