《算法导论第3版》阅读笔记

算法导论的英文全称是 Introduction to Algorithms，作者是Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein。该书被广泛认为是计算机科学领域的经典教材之一，涵盖了算法设计和分析的基本概念和技术。

这本书简称 CLRS，是 Cormen, Leiserson, Rivest, Stein 四人的名字首字母缩写。

第1章 算法在计算中的作用

略

第2章 算法的基础

介绍了插入排序。

介绍了算法分析方法，算法分析要考虑输入规模，运行时间，最坏情况和平均情况的运行时间，运行时间的增量量级。

然后对插入排序进行了算法分析。

2.2节的练习提到了选择排序算法。

接着介绍了分治法和基于分治法的归并排序，归并排序中使用了递归，这里给出了递归方程/递归式的概念。

2.3节的练习和思考题提到了二分查找算法和冒泡排序算法。

思考题2-3节介绍了霍纳规则。

霍纳规则

霍纳规则（Horner's Rule）是一种高效求解多项式值的算法。它通过将多项式重写为嵌套的形式，减少了乘法和加法的次数，从而提高了计算效率。

具体来说，给定一个多项式：

\[P(x) = \sum_{k=0}^n a_kx^k\]

利用霍纳规则，可以将其重写为：

\[P(x) = \sum_{k=0}^n a_kx^k = a_0 + x(a_1 + x(a_2 + ... + x(a_{n-1} + xa_n)...))\]

这种重写形式使得我们可以通过一次遍历来计算多项式的值，而不需要进行很多次重复的幂运算操作。

霍纳规则的伪代码实现

y = 0
for i from n to 0:
    y = a[i] + x * y