当前位置：首页 > ops >正文

《算法导论(第4版)》阅读笔记：p39-p48

ops 2025/8/27 14:35:12

《算法导论(第4版)》学习第 13 天，p39-p48 总结，总计 10 页。

一、技术总结

1. recurrence/recurrence equation

书里面 recurrence(递归式) 和 recurrence equation(递归方程) 指的是同一个东西。

二、英语总结(生词：2)

1. squint

(1)squint

vi. look askance(斜视)；look at things with eyes partly closed(眯着眼看)。

(2)示例

Since the difference between ⌈n/2⌉ and ⌊n/2⌋ is at most 1, which for large n is much smaller than the effect of dividing n by 2, we’ll squint a little and just call them both size n=2。

注：

1)⌈n/2⌉ is the ceiling of n/2 — it rounds up。

2)⌊n/2⌋ is the floor of n/2 — it rounds down。

在上面这个例子中"squint a little(斜视一点)"是一种比喻用法，意思是“ignore the small difference to simplify the situation”。

2. engaging

(1)engage: en-(“in”) + gage(“pledge，誓言，发誓”)

vt. attract and occupy the attention of(吸引)。

(2)engaging:

adj. charming and attractive(吸引人的，迷人的)。

(3)示例

In 1968, Knuth published the first of three volumes with the general title The Art of Computer Programming [259, 260, 261]. The first volume ushered in the modern study of computer algorithms with a focus on the analysis of running time. The full series remains an engaging and worthwhile reference for many of the topics presented here(《《算法导论(第4版)》》第 48 页)。

上面这句话的意思是：1968年，高德纳(Knuth)出版了《计算机程序设计艺术》(总共三卷)的第一卷。第一卷以算法运行时间分析为核心，开创了现代计算机算法研究的先河。对于本书涉及的诸多主题而言，《计算机程序设计艺术》仍是引人入胜且极具价值的参考资料。

关于英语的注解同步更新汇总到 https://github.com/codists/English-In-CS-Books 仓库。

三、其它

第 2 章(Getting Started)总结：介绍了两种排序算法——插入排序、归并排序，优点是是有图示，这真的有助理理解代码，每本算法书都应该保持这种做法。同时介绍了算法分析方法，和其它书没有太大区别。最后介绍了算法设计中的分而治之思想，个人觉得如果解决一个问题能想到用分而治之的思想其实只是前进了一小步，后面还有“算法实现”这一大步。