《算法導論(第4版)》學習第 12 天，p32-p38 總結，總計 7 頁。

一、技術總結

1.analyzing algorithms

(1)running time(運行時間)

worst-case running time, average-case running time，best-case running-time。

2.order of growth/rate of growth

剛開始看到 order 的時候感覺很別扭，因為平時遇到的 order 的意思大多是：1.“順序(the arrangement of things according to a particular pattern)”; 2. "命令(command)"。

在 “order of growth”中， order 的意思是“層級，階級，等級，量級(rank, level, category, class)” ，理解了這個意思之后，反而覺得 order of growth(增長量級)更準確一些——“算法運行時間在哪個量級，有一種分類的思想在里面”，而 rate of growth(增長率)更通俗易懂一些——“僅僅體現了算法運行時間變化的快慢”。

f(n) = 4n**2 , g(n) = 2n + 2000

上面的 f(n) 和 g(n) 分別表示兩個算法的最差運行時間(worst-case running time)，因為隨著輸入 n 的變大，f(n) 變化更快，需要的時間更多，則可以說： f(n) has higher order of growth as it grows quadratically in terms of input size。

3.devide-and-conquer(分而治之)

4.merge sort(歸并排序)

原理就不贅述了。說一下自己的感受：以前自己總是看不懂，現在算是看懂了，包含兩個步驟——divide & merge。于自己而言，難點還是在于對遞歸的理解和運用。跳出遞歸函數、遞歸函數調用這兩各操作自己理解，但是除了這個兩個操作，遞歸函數里面該做什么，自己總是把握不好，很容易忘記。

二、英語總結(生詞：0)

無。

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

三、其它

今天沒有什么想說的。

四、參考資料

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

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