《算法導(dǎo)論(第4版)》閱讀筆記:p49-p58
《算法導(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)
浙公網(wǎng)安備 33010602011771號