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

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

1. O-notation, Ω-notation, and ?Θ-notation

(1)O-notation

O-notation describes an asymptotic upper bound.

(2)Ω-notation

Ω-notation describes an asymptotic lower bound.

(3)Θ-notation

Θ-notation describes asymptotically tight bounds.

二、英語總結(jié)(生詞：1)

1. beat

(1)beat: *bhau-("to strike")

vt. the root of beat is tied to the physical act of striking or hitting repeatedly. 1.to defeat or do bettern than(打敗，戰(zhàn)勝)。

(2)示例

Once the input size n becomes large enough, merge sort, with its O(nlogn) worst-case running time, beats insertion sort, whose worst-case running time is O(n^2)(《《算法導(dǎo)論(第4版)》》第 48 頁)。

以前總是不大理解 beat 的意思，大概是因為詞典上的例子不夠好，像上面這個例子，O(nlogn) 和 O(n^2) 一對比，馬上對 beat 有了一個形象的理解。

關(guān)于英語的注解同步更新匯總到 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

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