《算法導(dǎo)論(第4版)》學(xué)習(xí)第 13 天，p39-p48 總結(jié)，總計 10 頁。

一、技術(shù)總結(jié)

1. recurrence/recurrence equation

書里面 recurrence(遞歸式) 和 recurrence equation(遞歸方程) 指的是同一個東西。

二、英語總結(jié)(生詞：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，誓言，發(fā)誓")

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(《《算法導(dǎo)論(第4版)》》第 48 頁)。

上面這句話的意思是：1968年，高德納(Knuth)出版了《計算機(jī)程序設(shè)計藝術(shù)》(總共三卷)的第一卷。第一卷以算法運行時間分析為核心，開創(chuàng)了現(xiàn)代計算機(jī)算法研究的先河。對于本書涉及的諸多主題而言，《計算機(jī)程序設(shè)計藝術(shù)》仍是引人入勝且極具價值的參考資料。

關(guān)于英語的注解同步更新匯總到 https://github.com/codists/English-In-CS-Books 倉庫。

三、其它

第 2 章(Getting Started)總結(jié)：介紹了兩種排序算法——插入排序、歸并排序，優(yōu)點是是有圖示，這真的有助理理解代碼，每本算法書都應(yīng)該保持這種做法。同時介紹了算法分析方法，和其它書沒有太大區(qū)別。最后介紹了算法設(shè)計中的分而治之思想，個人覺得如果解決一個問題能想到用分而治之的思想其實只是前進(jìn)了一小步，后面還有“算法實現(xiàn)”這一大步。

四、參考資料

1. 編程

(1) Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，Clifford Stein，https://book.douban.com/subject/35591269/

2. 英語

(1) Etymology Dictionary：https://www.etymonline.com

(2) Cambridge Dictionary：https://dictionary.cambridge.org

歡迎搜索及關(guān)注：編程人(a_codists)