此筆記用于指導(dǎo)初學(xué)者閱讀坎穿。原文在此展父！返劲，出于便于交流的考慮，內(nèi)容重放在此栖茉。由于作業(yè)部落支持LaTex公式篮绿，所以，更加清晰衡载。更新也以作業(yè)部落的鏈接為主搔耕。《算法導(dǎo)論》到底有沒有用？有啥用痰娱？
寒假了弃榨，必須各自回家。女朋友對小明說梨睁，我會(huì)想你的鲸睛，怎么辦？小明說坡贺，沒事官辈，這個(gè)你拿著，想我就狠狠地看看：一本《算法導(dǎo)論》遍坟。女朋友接著問，哪你想我怎么辦愿伴？小明嘿嘿一笑說隔节，沒事，我還有一本！《算法導(dǎo)論》......
第一部分 基礎(chǔ)
第一章 算法
1涌哲、什么是算法胖缤？（An algorithm is thus a suquence of computational steps that transform the input into the output.）
大家還需要去找答案，注意要進(jìn)一步歸納總結(jié)阀圾。
術(shù)語：
computational problem（計(jì)算性問題）
decisional problem（判定性問題）
計(jì)算領(lǐng)域三大問題：什么是計(jì)算機(jī)？什么問題可計(jì)算（可解）狗唉？解某個(gè)問題需要多長時(shí)間初烘、消耗多少資源？
2、算法能解決什么問題肾筐？
書本給出了很多實(shí)例哆料，說明算法能解決很多很多問題，似乎要顯示說算法無所不能吗铐。其實(shí)我們必須關(guān)心东亦，什么問題算法不能解決。
擴(kuò)展：停機(jī)問題（什么是停機(jī)問題唬渗，有什么重大意義典阵？）
3、什么是數(shù)據(jù)結(jié)構(gòu)镊逝？
鏈表壮啊、隊(duì)列、棧撑蒜、堆歹啼，二叉樹等等，需要慢慢填空......
4座菠、難解問題
概念： P狸眼、NP、NPC浴滴，不理解可跳過拓萌，記住P是多項(xiàng)式時(shí)間內(nèi)可解的問題集合即可。
思考： 難題為什么是難巡莹？有什么已知的難題司志？
換一個(gè)角度思考： 什么是容易解的問題？
術(shù)語： reduction（規(guī)約）降宅，這不容易的骂远。主要用于對NPC的描述。
5腰根、算法的效率
用實(shí)際的運(yùn)算給出直觀的感受激才，讀者必須去感受。
比較：log(N)额嘿，sqrt(N)瘸恼，N，N^2册养，2^N 东帅，N!
6、算法以及其他技術(shù)的討論
討論內(nèi)容球拦，有很多很多“靠闭？”帐我，不是難點(diǎn)，但需要思考愧膀，對初學(xué)者拦键，這種思考往往是提高水平的正確路徑。
7檩淋、擴(kuò)展思考與檢索
為什么說算法是計(jì)算機(jī)科學(xué)的核心內(nèi)容芬为？算法的研究起源在哪里？什么時(shí)候開始人們認(rèn)為：算法奠定了計(jì)算機(jī)科學(xué)的基礎(chǔ)蟀悦？
第二章 算法起步
2.1媚朦、插入排序（以實(shí)例帶動(dòng)講解）
術(shù)語：Loop invariants（循環(huán)不變量？）
這是CLRS分析算法的一種重要技巧熬芜，要認(rèn)真理解為何引入這個(gè)概念莲镣，以后如何運(yùn)用這個(gè)概念。
偽代碼的表示法涎拉，簡單工作瑞侮！
2.2、算法分析模型
2.2.1 重點(diǎn)：RAM
注意：本書講解RAM以犧牲準(zhǔn)確性為代價(jià)獲得更通俗易懂的表達(dá)鼓拧，原始的RAM模型可沒這么簡單半火。但是我喜歡這種講解。
擴(kuò)展思考：除了RAM模型還有什么分析算法的模型季俩？
Additional Comments about RAM: 由于不少同學(xué)紛紛表示對RAM的不理解钮糖，我多說幾句。首先聲明酌住，不理解RAM模型并不會(huì)嚴(yán)重影響后續(xù)閱讀店归，所以你可以非常放心目前的“不理解”。但我依然建議大家看看多兩遍課本這并不冗長的兩頁說明講解酪我。以下是一些要點(diǎn)：
- RAM模型是用于分析算法的一種計(jì)算模型消痛；并非真實(shí)的計(jì)算機(jī)。
- 一種計(jì)算模型通常會(huì)包括：指令都哭、內(nèi)存秩伞、數(shù)據(jù)類型、指令調(diào)度等內(nèi)容欺矫。然而纱新，書本并不講解這些，反而是強(qiáng)調(diào)穆趴，不要濫用RAM模型脸爱。言外之意是，這些我就不多說了未妹，只要不按常規(guī)來阅羹，不亂出牌勺疼，基本就ok...... （體會(huì)教寂，2.2 第三段的這種含義）捏鱼。說白了，這里給出RAM模型但是并沒有具體解釋RAM模型酪耕！
- 數(shù)據(jù)類型导梆，只強(qiáng)調(diào)一點(diǎn)，大小為n的整數(shù)可以表達(dá)為c lg n比特迂烁。言外之意還是看尼，不要亂來即可。（2.2 第四段）
- 指令盟步、內(nèi)存層次結(jié)構(gòu)藏斩、單cpu、指令的串行執(zhí)行等等要求都非常常規(guī)却盘。（2.2 第五狰域、六段）
- 指出分析是困難的，但難點(diǎn)是在數(shù)學(xué)：組合數(shù)學(xué)黄橘、概率論兆览、代數(shù)等，跟RAM沒多大關(guān)系塞关。（2.2 第七段）
- 最后展望未來抬探，我們還有很多可以選擇的計(jì)算模型。
總而言之帆赢，準(zhǔn)確定義計(jì)算模型是復(fù)雜的小压，在保證計(jì)算模型不被濫用的情況下，我們可以犧牲準(zhǔn)確性而得到相應(yīng)的簡潔性與清晰性椰于。對于初入門的CSers怠益，剛學(xué)完C語言的同學(xué)，剛好你們不懂什么內(nèi)存層次廉羔、并發(fā)計(jì)算等（即所謂“濫用”之處）溉痢，所以，把RAM下的程序理解為一般的C語言程序則剛剛好憋他。畢竟你們想濫用模型也往往不知道如何濫用（這樣說真的不好嗎孩饼？）。
2.2.2 插入排序的效率分析
這里只是一個(gè)實(shí)例竹挡。
擴(kuò)展思考：冒泡排序的效率如何分析镀娶？是什么？與插入排序相比揪罕，哪個(gè)算法更好梯码？或者宝泵，各有什么優(yōu)勢劣勢？
2.2.3 Worst-case and average-case analysis（難點(diǎn)Ｐⅰ）
為何要區(qū)分兩種不同的效率分析儿奶？如何理解這兩個(gè)概念？我們更需要的是那種效率鳄抒？
例子：對整數(shù)x和y闯捎，求x^y需要多少時(shí)間？也許我們沒有準(zhǔn)確答案许溅，大概我們知道計(jì)算x的y次方要比計(jì)算x+y要耗更多的時(shí)間瓤鼻。然而，如果x = 2贤重，算2^y只需要進(jìn)行y次左移茬祷，并不比x + y慢。也就是說并蝗，在特定的情況下我們也許會(huì)有非常高效的算法祭犯，然而在一般情況下，算法需要執(zhí)行更多的時(shí)間借卧。因此我們需要平均復(fù)雜性來衡量這樣的一般情況盹憎。有時(shí)候我們對特定情形下的最短時(shí)間并不感興趣，因?yàn)槲覀儽容^保守铐刘，此時(shí)我們會(huì)問陪每，最多需要多少時(shí)間（上界）來完成這項(xiàng)工作。此時(shí)镰吵，我們考慮最懷情況下的復(fù)雜性檩禾。
2.3、算法設(shè)計(jì)
重點(diǎn)：分治法
實(shí)例：歸并排序疤祭，相信大家可以愉快地閱讀下去盼产，請注意Loop invariants的使用。
提示：遞歸樹是非常好的工具勺馆，用起來戏售！
2.4、習(xí)題（提示：該做題了２菽隆）
2.5灌灾、編程題
此題源自于某位同學(xué)的提問，課本建議“將插入排序與歸并排序結(jié)合使用悲柱，當(dāng)一組數(shù)的個(gè)數(shù)足夠小時(shí)锋喜，使用插入排序進(jìn)行處理，再進(jìn)行合并”。從而提高排序的效率嘿般。問題是如何判斷數(shù)組個(gè)數(shù)是多少才足夠小呢段标？我的建議是，編程測試炉奴。
1逼庞、設(shè)計(jì)實(shí)現(xiàn)插入排序與歸并排序結(jié)合使用的排序程序；
2盆佣、設(shè)置一個(gè)變量控制何時(shí)進(jìn)行插入排序往堡；
3、對1000k的隨機(jī)數(shù)組進(jìn)行排序共耍，測試顯示在不同的控制下排序的效率。
第三章 函數(shù)的增長
3.1吨瞎、Asymptotic notation（漸進(jìn)表示法）：Big O痹兜，Omiga，Theta
術(shù)語：上界颤诀、下界字旭、緊致界
簡單而言：最多做多少步？最少做多少步崖叫？最多做那么多步且最少也需要這么多步遗淳！
難點(diǎn)1：相關(guān)計(jì)算，多做題心傀！
難點(diǎn)2：惱人的常數(shù)c
同學(xué)提問屈暗，常數(shù)c到底是多少？怎么理解BigO等等表達(dá)中需要乘一個(gè)常數(shù)脂男？
回答：要理解這個(gè)惱人的c养叛，首先要明白漸進(jìn)式表達(dá)是一種松散的界，c可以理解為松散度系數(shù)宰翅。其次我們要理解這個(gè)c往往不影響我們的結(jié)論弃甥，盡管我們不知道它的真實(shí)大小。例子：考慮快速排序與歸并排序汁讼，都是O(n lg n)的復(fù)雜度淆攻。那么我們可以說它們分別低于c_1 n lg n
（記為f）和c_2 n lg n（記為g），其中c_1和c_2是兩個(gè)不同的常數(shù)嘿架，我們并不知道具體數(shù)值∑可海現(xiàn)在我們想比較這兩種排序的大小，因?yàn)槲覀兒軗?dān)心不同的常數(shù)項(xiàng)會(huì)對我們造成影響眶明，f/g = c_1/c_2艰毒，得到一個(gè)常數(shù)！盡管我們還是不知道f/g的大小搜囱，但是我們知道這兩個(gè)數(shù)值相比只差一個(gè)常數(shù)丑瞧，當(dāng)n增加得很大的時(shí)候柑土，常數(shù)不變，往往就顯得無關(guān)緊要了绊汹。值得注意的是稽屏，這里只是說，通常情況下c不影響西乖，并不是說常數(shù)永遠(yuǎn)不對算法復(fù)雜性有影響狐榔。
3.2、標(biāo)準(zhǔn)表達(dá)及常用函數(shù)
提示：有很多比較難的函數(shù)获雕，不一定要死記（能記住也是鼓勵(lì)的１∧濉），先知道届案，用到了再查庵楷。或者在以后以專題的形式重點(diǎn)攻克楣颠。比如：Stirling公式尽纽。
Side Comments：曾經(jīng)與某同學(xué)討論算法的學(xué)習(xí)，他說自己學(xué)得很慢童漩，碰到每一個(gè)難題都想去解決（不解決就不舒服斯基）弄贿，不解決就沒辦法看其他內(nèi)容。我不很同意這種做法矫膨，不懂應(yīng)該成為常態(tài)差凹！要先建立一種全局觀，并有整體的思路豆拨，允許存在以后解決的技術(shù)和理論難點(diǎn)直奋。拿這里來說，兩頁書的公式包含了很多的數(shù)學(xué)內(nèi)容施禾，就單單是一個(gè)Stirling公式脚线，我就沒有把握需要多少時(shí)間去把握它。如果糾結(jié)一個(gè)Stirling公式而不去看以下的內(nèi)容弥搞，有意義嗎邮绿？當(dāng)然，相信這位同學(xué)也不是在糾結(jié)Stirling公式攀例，只是舉一個(gè)例子船逮。
提示：除了理解和做題還有什么辦法？
3.3粤铭、測試
以下測試是在CLRS的作者Cormen的主頁上找到的挖胃，建議做一做：
第四章 Recurrences（遞歸式）
本章講解三種計(jì)算漸進(jìn)復(fù)雜性界的方法：替換法、遞歸樹法以及Master Theorem（主定理？酱鸭？）
4.1 最大子數(shù)組問題
暫略～
4.2 矩陣乘法
暫略～
4.3吗垮、替換法：猜一個(gè)結(jié)果、證明結(jié)論（歸納法證明）
技巧1：猜測結(jié)果減去一個(gè)低階子項(xiàng)使得證明得證凹髓；注意邊界條件烁登，可令n 大于某個(gè) n_0項(xiàng)，使得邊界條件成立蔚舀。
技巧2：換元法饵沧，例如，令 m = lg n 赌躺。適用于處理遞歸式中有sqr(n)的情形狼牺。
4.4、遞歸樹法
本質(zhì)上是通過構(gòu)造遞歸樹寿谴，得到一個(gè)正確的猜測锁右。還是要通過替換法進(jìn)行結(jié)論證明！
4.5讶泰、主定理：菜譜式定理，證明可以先跳過拂到。
目標(biāo)：給定 T(n) = aT(n/b) + f(n)痪署，a,b > 1，f(n)為正函數(shù)兄旬。求遞歸式的界狼犯。
直觀上（忽略某些細(xì)節(jié)而言），是通過比較n^{(log_b a)} 與 f(n)的大小進(jìn)行判斷:如果前者大领铐，則是\Theta(n^{(log_b a)})悯森；如果是后者大，答案則是\Theta(f(n))绪撵；如果一樣大瓢姻，則要乘上一個(gè)對數(shù)函數(shù)子項(xiàng)得到\Theta(n^{(log_b a)} lg n) = \Theta(f(n) lg n)。
思考：為何是比較n^{(log_b a)} 與 f(n)的大小呢音诈？
提示：n^{(log_b a)} 是不是等于 a^{(log_b n)} 幻碱？ a^{(log_b n)}在遞歸式中代表什么含義？
Comment1：這種方法并不是萬能的细溅，有很大的局限褥傍。其次，在運(yùn)用中不能忽略某些細(xì)節(jié)喇聊，比如恍风，大小的比較，在這里要求的是多項(xiàng)式大或者多項(xiàng)式小。
Comment2：第一次閱讀不要求證明并不能說明這里的證明就非常難朋贬。絕非如此凯楔，這個(gè)證明沒有使用到復(fù)雜的技巧，只要把握住“遞歸樹”的思路兄世，理解并不困難啼辣。不畏難的同學(xué)，在進(jìn)度跟得上的前提下御滩，可先行閱讀鸥拧。特別是在假設(shè)n=2^b下的證明，不難理解削解。
Comment3：有意思的是富弦，在應(yīng)用替換法、遞歸樹法氛驮、主定理方法做題的時(shí)候腕柜，同學(xué)們都會(huì)很自覺地根據(jù)自己的喜好進(jìn)行選用。實(shí)際上矫废，他們應(yīng)該是對這三種方法有自己的評(píng)判和選擇（能說是偏見嗎盏缤？），但是又不自覺地歸納總結(jié)出來蓖扑。比如唉铜，有同學(xué)認(rèn)為替換法很隨意，也難以猜對律杠，所以不使用潭流。又比如：有同學(xué)認(rèn)為Master Theorem只是套公式，是死記硬背柜去，沒什么意思灰嫉，也不選用。然后嗓奢，認(rèn)為遞歸樹法比較靠譜讼撒。其實(shí)，我認(rèn)為這樣的理解都頗為片面蔓罚。
首先椿肩，我提倡大家猜！要知道能建立一種直觀是非常重要的豺谈，不要忘記郑象，“猜”就是一種能力，在科研起步的早期茬末，使用“猜”的方法去培養(yǎng)直觀可又大收獲厂榛。其次盖矫，使用遞歸樹法不要忘記證明！遞歸樹只不過是幫助猜測的的一種方法击奶，結(jié)論必須得到證明辈双。第三，有菜譜為何不用柜砾？沒錯(cuò)湃望，是死記硬背，不要忘記痰驱，“記憶力”就是智商的一種证芭！而且，這套方法是前人經(jīng)過整理證明出來的有效方法担映，可直接使用废士，因?yàn)閾?dān)心自己不理解而不去使用算不算“因噎廢食”？
因此蝇完，在此我提倡官硝，做題的時(shí)候三種方法都使用起來。首先猜短蜕，猜對猜不對都要去猜一下氢架。其次，畫遞歸樹朋魔，能畫不能畫都去嘗試一下达箍。如果遞歸樹或者替換法能得到答案，最后用Master Theorem驗(yàn)證一下自己的答案铺厨。
當(dāng)然，這并非萬能方法硬纤。也許我們可以不斷積累技巧解滓，其中，“換元法”我還是建議大家多多練習(xí)筝家。
2016年3月注記：最近洼裤，15圖靈班對“主定理“的證明進(jìn)行了討論，也是本學(xué)期的第一次討論溪王。效果不錯(cuò)腮鞍，討論熱烈。討論過程表示莹菱，同學(xué)們基本上理解了該定理移国，也掌握了其中基本的證明技巧。相信道伟，繼續(xù)下去迹缀，這個(gè)討論班會(huì)有較大的收獲使碾。
4.6、做習(xí)題檢驗(yàn)這三種方法祝懂。本章強(qiáng)調(diào)練習(xí)票摇！
第五章 概率分析與隨機(jī)算法
建議在沒有概率論基礎(chǔ)時(shí)忽略。當(dāng)然砚蓬，這里要求的概率基礎(chǔ)也比較少矢门。建議掌握一些相關(guān)概念，比如灰蛙，什么是概率分析祟剔，什么是隨機(jī)算法。
期望大家走到這里的時(shí)候不要超過一周時(shí)間缕允！
補(bǔ)錄：
在實(shí)際的學(xué)習(xí)過程中峡扩，我還是堅(jiān)持要求學(xué)生們進(jìn)行了概率分析的學(xué)習(xí)皮假，困難是他們沒有上過概率課撮抓。因此，簡單地補(bǔ)了幾個(gè)概念：示性隨機(jī)變量依啰、期望值驾霜、期望的線性性案训。結(jié)果，此章的內(nèi)容可以順利完成粪糙。
這說明：在需要的時(shí)候?qū)δ承┲R(shí)點(diǎn)進(jìn)行補(bǔ)充并非不可能完成的任務(wù)强霎。反過來證明了那些在此卻步的同學(xué)并非能力不足，而是信心不足蓉冈。
第二部分 排序與序性統(tǒng)計(jì)
這一部分出了講排序等算法之外城舞，實(shí)際上也講了一種簡單數(shù)據(jù)結(jié)構(gòu)--數(shù)組和堆。
第六章 堆排序
6.1 堆
堆可以視為一種完全二叉樹寞酿，也可視為數(shù)組家夺。理解堆的關(guān)鍵不在堆本身，我寧愿大家先理解完全二叉樹伐弹。估計(jì)拉馋，作者此處假設(shè)讀者已經(jīng)掌握了一定的樹的知識(shí)。如果你在第一次閱讀碰到困難惨好，不妨停下來看看樹的概念煌茴，并畫一棵樹，然后體會(huì)日川、理解蔓腐、證明幾個(gè)關(guān)于樹的結(jié)論。
樹的概念：根逗鸣、節(jié)點(diǎn)合住、葉子绰精、左兒子、右兒子透葛、父節(jié)點(diǎn)笨使、樹的高度
關(guān)于樹的結(jié)論：n個(gè)元素的完全二叉樹的高度是floor(lg n)；高度為h的完全二叉樹的元素個(gè)數(shù)最多（最少）是多少僚害？n個(gè)元素的完全二叉樹，葉子的數(shù)目最多是多少靶草？這些結(jié)論通吃酪＃可以自己總結(jié)奕翔，然后用歸納法進(jìn)行證明浩蓉。
6.2、堆的操作與堆排序
有了樹的概念之后捻艳，堆的操作與堆排序都是容易理解的驾窟。
6.5 優(yōu)先隊(duì)列
第七章 快速排序
這一章可說的東西暫時(shí)不多认轨。相信大部分同學(xué)已經(jīng)知道并學(xué)習(xí)過這個(gè)算法嘁字。與之前學(xué)習(xí)稍有區(qū)別的是，這里是講兩個(gè)版本的快排算法：確定性算法與隨機(jī)化算法假栓。后者與前者只有微妙的區(qū)別霍掺，就是在選擇主元的時(shí)候是均勻隨機(jī)地選擇杆烁。
對隨機(jī)快排的思考：為什么需要這樣做兔魂？何時(shí)需要這樣做举娩？這樣做得到什么好處？
這一章的難點(diǎn)在QSort的效率分析遂唧。由于是概率分析吊奢，在沒有概率基礎(chǔ)的情況下页滚，暫時(shí)跳過裹驰。
排序算法的兩種重要屬性：in-place 和 stable。
QSort中的Partition方法比較幻林，這篇Blog的回答真是太專業(yè)了滋将。為什么Hoare的Partition算法更有優(yōu)勢反而不寫在正文，留做思考題呢父丰？
經(jīng)驗(yàn)教訓(xùn)：簡單的概率知識(shí)作為CLRS的先驗(yàn)知識(shí)還是非常有必要蛾扇。實(shí)際上镀首，所需要的概率知識(shí)也不是很多鼠次，應(yīng)該在第一學(xué)期就適當(dāng)?shù)刈屚瑢W(xué)們掌握腥寇。比如赦役，使用Pass等人的Discrete Mathematics的Lecture作為基礎(chǔ)就不錯(cuò)掂摔。
第八章 線性時(shí)間排序算法
1赢赊、排序算法的下界
利用判定樹模型證明所有使用元素對比的排序算法的復(fù)雜度下界是\Omega(n*log ~\ n)释移⌒惚蓿基本思路：判定樹是一棵二叉樹锋边，中間節(jié)點(diǎn)是元素之間的對比编曼，葉子是排好序后數(shù)組下標(biāo)的全排列（有點(diǎn)繞口）掐场。如果有n個(gè)元素熊户，則數(shù)組下標(biāo)的全排列有n!種可能嚷堡，即判定樹的葉子個(gè)數(shù)（記為l）至少有n!個(gè)。二叉樹的樹高為h串塑，它有多少葉子桩匪？把以上推理記為：n! <= l <= 2^h 傻昙。簡單計(jì)算得出結(jié)論屋匕。
難點(diǎn)在于判定樹模型借杰，為何可以把HeapSort蔗衡、QSort绞惦、MergeSort等等使用對比的排序算法的行為抽象為判斷樹济蝉？我暫時(shí)也沒有非常合理簡單的講解可以提供王滤，需要大家自己體會(huì)。其實(shí)我看書本也沒能解釋得很清楚第喳∏ィ總而言之扩淀，結(jié)論非常重要驻谆。
擴(kuò)展思考旺韭、練習(xí)： 如何比較HeapSort掏觉、QSort澳腹、MergeSort的優(yōu)劣酱塔？它們都有相同的復(fù)雜性羊娃，而且已經(jīng)達(dá)到最優(yōu)，說明它們的性能相同弥雹？最好用實(shí)踐來檢驗(yàn)剪勿，任何已知結(jié)論都不可靠方庭，需要驗(yàn)證械念。
2订讼、計(jì)數(shù)排序
這是一種具有線性復(fù)雜性的排序算法欺殿，當(dāng)然脖苏，有優(yōu)勢必然要付出一定的代價(jià)棍潘。
思考：這里的代價(jià)是什么呢亦歉？
基本思路：所有待排序的元素（或用于排序的關(guān)鍵字）都是某個(gè)范圍之內(nèi)的整數(shù)值肴楷。首先，輸入待排序的數(shù)組A砂客，統(tǒng)計(jì)其中某個(gè)數(shù)值出現(xiàn)的次數(shù)鞠值，存于C數(shù)組彤恶；從而得出小于或等于某個(gè)數(shù)值的數(shù)值的個(gè)數(shù)声离，還是存于C數(shù)組抵恋；最后弧关，根據(jù)C數(shù)組的統(tǒng)計(jì)世囊，將A數(shù)組中的元素放入數(shù)組B合適的位置中株憾，B即為輸出嗤瞎。這三個(gè)步驟都是線性時(shí)間的復(fù)雜度贝奇，加起來依然是線性復(fù)雜度掉瞳。
3陕习、基數(shù)排序
基本思路：首先该镣，把待排序元素的鍵值分成d個(gè)數(shù)位拌牲，每個(gè)digit有k個(gè)可能值塌忽。然后使用具有stability屬性（比如土居，使用計(jì)數(shù)排序）的排序算法，分別針對d個(gè)數(shù)位進(jìn)行排序棉圈。復(fù)雜性：Theta(d*(n+k))分瘾〉抡伲基數(shù)排序的快速依賴于它調(diào)用的計(jì)數(shù)排序上岗。
思考：線性時(shí)間的基數(shù)排序是不是擊敗了其他所有的排序算法肴掷？為何呆瞻？
4栋烤、桶排序
基本思路：對n個(gè)元素進(jìn)行排序明郭，均勻隨機(jī)地將這n個(gè)元素丟入n個(gè)桶之中薯定。每個(gè)桶都有一個(gè)編號(hào)n_i话侄，編號(hào)越小的桶里面的元素就越小。使用插入排序?qū)ν爸性剡M(jìn)行排序变丧。按桶編號(hào)順序輸出桶中元素痒蓬。
復(fù)雜性分析：里面用到了隨機(jī)變量攻晒、隨機(jī)變量的期望等概率論中內(nèi)容鲁捏。拋開這些不談给梅，能不能從直觀上看到某些東西呢破喻？把n個(gè)元素丟入桶中需要的時(shí)間是Theta(n)曹质，然后對n個(gè)桶中的元素排序羽德。每一個(gè)桶假設(shè)有n_i個(gè)元素宅静，那么就需要O(n_i^2)的時(shí)間（插入排序Ｒ碳小）磷账。拍腦瓜的時(shí)候來了逃糟，均勻隨機(jī)地在n個(gè)桶中放n個(gè)元素绰咽，平均（所謂期望無非就是平均）每個(gè)桶里面有多少個(gè)元素？如果你算對了矛辕，書上的那一堆嚇人的公式大概都是浮云了~
提示：桶排序使用了特定的數(shù)據(jù)結(jié)構(gòu)聊品，可在后續(xù)數(shù)據(jù)結(jié)構(gòu)的內(nèi)容學(xué)完之后再對桶排序進(jìn)行編程練習(xí)翻屈。
第九章 中值及序位統(tǒng)計(jì)
本章最難懂不是其算法伸眶，而是其標(biāo)題（吐槽＠逶簟）嘴秸。中文版直接將Statistics翻譯為統(tǒng)計(jì)學(xué)（“中位數(shù)和順序統(tǒng)計(jì)學(xué)”）讓人摸不著頭腦凭疮。實(shí)際上执解，本章只是考慮對n個(gè)元素求其最小值衰腌、最大值和中間值桶唐；一般化地尤泽，求n個(gè)元素的第i小的那個(gè)元素坯约，稱為Selection算法。
1卿拴、最大值與最小值
簡單思路： 按順序從第一個(gè)元素開始堕花，逐個(gè)元素對比缘挽，并保存下當(dāng)前最大（最泻韭）的元素位置摹蘑。Theta(n)的復(fù)雜性纹蝴。
疑問：這樣做是不是最好的做法（常用詞：optimal）呢？答案援奢，yes集漾！繼續(xù)提問：why具篇？
稍微難一點(diǎn)的問題：如何同時(shí)求最大值與最小值。
2埃疫、平均復(fù)雜性為線性時(shí)間的Selection算法
思路：使用QSort算法對數(shù)組進(jìn)行劃分的思路栓霜，是一種分治法销凑，使用了遞歸斗幼。
提示：放心跳過大量的概率復(fù)雜性分析茂洒。
3孟岛、最壞情況為線性時(shí)間的Selection算法
思路：
復(fù)雜性分析：
第二部分結(jié)束。個(gè)人認(rèn)為督勺，第二部分的內(nèi)容比第一部分稍容易渠羞，除了概率分析（剛好大家也可以跳過）之外，沒有什么理論難點(diǎn)智哀。所以次询，期望大家走到這里只是第二周學(xué)習(xí)的結(jié)束瓷叫。無論你認(rèn)為是快還是慢屯吊，都可以反思一下，為什么摹菠？也可以進(jìn)行討論盒卸。
第三部分 數(shù)據(jù)結(jié)構(gòu)
相信CLRS的作者會(huì)假定自己的學(xué)生（或者讀者）懂一點(diǎn)點(diǎn)數(shù)據(jù)結(jié)構(gòu)，但是要求掌握的并不多（也許這種要求之低可以低到以至于可以忽略）次氨。因此蔽介，在引入數(shù)據(jù)結(jié)構(gòu)的時(shí)候，作者強(qiáng)調(diào)了“動(dòng)態(tài)集合”的操作：檢索煮寡、插入虹蓄、刪除、最小值幸撕、最大值薇组、前驅(qū)成員、后繼成員等坐儿，完全是高度的抽象律胀。字典是本章主要考察的實(shí)現(xiàn)對象。
反思：在學(xué)習(xí)CLRS之前是否需要集合論及簡單的數(shù)據(jù)結(jié)構(gòu)知識(shí)貌矿？盡管不知道大家如何想累铅，實(shí)際上，如果CLRS是第一學(xué)期之后學(xué)習(xí)站叼，要滿足這兩種前驅(qū)知識(shí)的需求也并不難達(dá)到娃兽。
注意：本章強(qiáng)調(diào)實(shí)踐，使用C++及OO編程的技術(shù)做完本章習(xí)題尽楔，基本就覆蓋了普通Data Structures with C++ 的內(nèi)容投储。我在對比了William Ford的《Data Structures with C++》的目錄之后得出此結(jié)論第练。如果我的學(xué)生可以完成這些內(nèi)容的學(xué)習(xí)，就必須問一句：數(shù)據(jù)結(jié)構(gòu)還必須那樣教嗎玛荞？
第十章 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)
1娇掏、棧與隊(duì)列
應(yīng)該沒有什么難度，大家可以自學(xué)并實(shí)現(xiàn)相關(guān)算法勋眯。自覺利用OO編程婴梧，設(shè)計(jì)相關(guān)的Class定義。
2客蹋、鏈接表
唯一的難點(diǎn)在于：指針塞蹭！所以，還是認(rèn)為第一學(xué)期的課程必須包括指針編程的訓(xùn)練讶坯。
3番电、實(shí)現(xiàn)指針與對象
這一節(jié)講解如何在不提供指針與對象的程序語言中實(shí)現(xiàn)指針與對象。很奇怪的目的辆琅，是嗎漱办？因?yàn)槲覀儸F(xiàn)在大部分的語言都已經(jīng)實(shí)現(xiàn)了指針與對象。所以婉烟，看完這一章感覺不奇怪的話娩井，那么任務(wù)就完成了。不要忘記似袁，C/C++是使用其他程序語言實(shí)現(xiàn)的程序語言洞辣。我們往往對C語言中的指針運(yùn)算感到困惑，比如指針的++叔营、--運(yùn)算，指針的指針所宰，指針的指針的指針等等绒尊，掃除這些困惑的一種方法就是了解這種變量的實(shí)現(xiàn)方法！（注仔粥，問正確的問題婴谱，是你走出正確理解的重要一步。）
4躯泰、表達(dá)有根樹
這一節(jié)有兩個(gè)重要內(nèi)容：二叉樹與帶根樹的實(shí)現(xiàn)方法谭羔。需要講解的內(nèi)容不多，重點(diǎn)在于通過指針結(jié)構(gòu)實(shí)現(xiàn)樹及其各種遍歷麦向、查詢瘟裸。有根樹與二叉樹的區(qū)別僅僅在于前者的節(jié)點(diǎn)會(huì)有任意多個(gè)后代節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)都有一個(gè)指針指向自己的父親節(jié)點(diǎn)诵竭，也有一個(gè)指針指向自己的右邊兄弟節(jié)點(diǎn)话告。編程兼搏！
第11章 Hash表
Hash表是實(shí)現(xiàn)字典的有效數(shù)據(jù)結(jié)構(gòu)。Hash表也許會(huì)被翻譯為”哈希表“或者“散列表”沙郭，只是這種翻譯也許并不需要佛呻。直觀而言，字典病线，即通過關(guān)鍵詞檢索相對應(yīng)的數(shù)據(jù)項(xiàng)吓著。
1、直接尋址
使用關(guān)鍵詞（key）作為存儲(chǔ)的檢索號(hào)（對應(yīng)一個(gè)存儲(chǔ)位置：slot）送挑。高效簡單绑莺，前提是key的范圍足夠小。
2让虐、Hash表
與直接尋址相比紊撕，這里使用Hash函數(shù)將Key映射到一個(gè)存儲(chǔ)位置K。使用Hash函數(shù)的原因是Key的范圍很大赡突，但是真正使用到的Key只是一小部分对扶。比如，中國有13億人口惭缰，要存儲(chǔ)所有人的個(gè)人信息浪南。如果以姓名為Key，這也許是一個(gè)無窮大的范圍漱受，我們沒必要為每一個(gè)可能存在的姓名準(zhǔn)備一個(gè)存儲(chǔ)位置络凿。
因此，這里的關(guān)鍵是設(shè)計(jì)合理的Hash函數(shù)昂羡。我們要求Hash函數(shù)可高效實(shí)現(xiàn)絮记，并且盡可能避免碰撞（Collision）。所謂碰撞虐先，即存在兩個(gè)不同的key怨愤，k1和k2，使得h(k1) == h(k2)蛹批。首先撰洗，我們看Hash函數(shù)h的定義，一定要明確腐芍，碰撞存在差导！為什么？
當(dāng)碰撞發(fā)生之后猪勇，如何處理存在的沖突呢设褐？ Chaining！
3、Hash函數(shù)
解決上一節(jié)遺留問題络断，如何設(shè)計(jì)“好”的Hash函數(shù)裁替。
a. 什么是好的Hash函數(shù)？
b. 使用除法
c. 使用乘法
*** Universal Hashing 第一次閱讀跳過貌笨，然而開學(xué)后的學(xué)習(xí)中Universal Hashing依然是可以進(jìn)行的內(nèi)容弱判。目前看效果一般，主要是更深入的學(xué)習(xí)與研究沒辦法開展锥惋。另外就是此內(nèi)容在表述上不同的教材有一定的區(qū)別昌腰，也帶來一定的困難。不過膀跌，依然令人滿意遭商。以后可以以專題的形式再次學(xué)習(xí)。
4.開放尋址
不使用列表捅伤，在數(shù)組的基礎(chǔ)上直接實(shí)現(xiàn)碰撞發(fā)生的處理劫流。算法簡單，分析有點(diǎn)困難丛忆，還是要卡在隨機(jī)變量及期望祠汇！放過定理證明先。
*5熄诡、完全Hash (暫時(shí)跳過)
第12章 二叉搜索樹
1可很、 什么是二叉搜索樹 ？
二叉搜索樹是滿足以下特性的二叉樹：x是樹的節(jié)點(diǎn)凰浮，x的左子樹的所有非空節(jié)點(diǎn)的key都比x的key要小我抠，x的右子樹的所有非空節(jié)點(diǎn)的key都比x的key要大。
三種遍歷方式：前序袜茧、中序與后序菜拓。簡單而言，從根出發(fā)笛厦，有三種選擇：先訪問根節(jié)點(diǎn)再訪問子樹纳鼎；先訪問左子樹，訪問根節(jié)點(diǎn)递递，再訪問右子樹喷橙；先訪問子樹啥么，最后訪問根節(jié)點(diǎn)登舞。
2、二叉搜索樹的查詢悬荣、遍歷
容易菠秒！理解思路：樹是一種遞歸結(jié)構(gòu)，即樹的子孫節(jié)點(diǎn)都是一棵樹。因此践叠，首先通過遞歸的思路去理解是最合適的言缤。比如：簡單的中序遍歷來說，輸入：一棵樹的樹根禁灼。遍歷：遞歸遍歷樹根的左子樹管挟，訪問樹根節(jié)點(diǎn)，遞歸遍歷樹根的右子樹弄捕。
3僻孝、二叉搜索樹的插入與刪除
插入算法容易。刪除算法稍微復(fù)雜守谓。這里要注意穿铆，第三版在此處有非常大的改進(jìn)。我看的是第二版斋荞，情況分析是清晰的荞雏，但是偽代碼經(jīng)過了整合優(yōu)化，可讀性較差平酿。第三版的Delete算法描述清晰BigO(n)倍凤优。所以，無論多么著名的書染服，都可以質(zhì)疑别洪。
一個(gè)簡單的證明題，用于幫助理解刪除操作過程：刪除z節(jié)點(diǎn)柳刮，當(dāng)其左子樹與又子樹都不為Nil挖垛，找其successor y節(jié)點(diǎn)（Case 3） 。請證明秉颗，y的左子樹必為nil痢毒。
若干課外資料：
a、一份純C的BST教程蚕甥，作者聲稱非常不喜歡理論:-D哪替。
b、一份Python的BST教程菇怀，適當(dāng)?shù)臅r(shí)候可以學(xué)習(xí)一下Python凭舶。
*4、二叉搜索樹的隨機(jī)生成
給定一系列元素爱沟，以隨機(jī)的順序?qū)⑺鼈儾迦攵鏄渲兴Ｄ康模玫揭豢谩拜^矮”的樹呼伸。重點(diǎn)在概率分析身冀。
第13章 紅黑樹
本章的主要任務(wù)還是與樹的高度作斗爭，要得到矮的樹，關(guān)鍵是要樹平衡發(fā)展搂根。紅黑樹是一種特殊的二叉搜索樹珍促，每一個(gè)節(jié)點(diǎn)增加一個(gè)顏色屬性（紅節(jié)點(diǎn)或者黑節(jié)點(diǎn)），目的是建立平衡二叉樹剩愧，這是重點(diǎn)也是難點(diǎn)猪叙。
1、什么是紅黑樹
紅黑樹有五點(diǎn)屬性需要把握：每個(gè)節(jié)點(diǎn)不是紅就是黑仁卷；根節(jié)點(diǎn)是黑節(jié)點(diǎn)沐悦；所有的葉子都是黑；每一個(gè)紅節(jié)點(diǎn)的孩子都是黑節(jié)點(diǎn)五督；每一節(jié)點(diǎn)走到葉子的不同路徑包含相同個(gè)數(shù)的黑節(jié)點(diǎn)（保證黑高相同藏否，也就保證了樹高的平均）。
2充包、樹的旋轉(zhuǎn)
一種插入副签、刪除的輔助操作，用于保證紅黑樹的屬性基矮。容易～
3淆储、插入、刪除
與二叉樹的插入刪除主要有一點(diǎn)不同家浇，即插入本砰、刪除會(huì)導(dǎo)致紅黑樹屬性變化，因此必須修補(bǔ)钢悲，使得原有屬性得以保持点额。這里應(yīng)該算是一個(gè)難點(diǎn)，也許是除了數(shù)學(xué)概率分析之外莺琳，數(shù)據(jù)結(jié)構(gòu)當(dāng)中的第一個(gè)難點(diǎn)还棱。要克服這里的困難應(yīng)該如何做？建議在閱讀了基本內(nèi)容（先忽略大部分的算法）之后惭等，多用筆紙畫圖珍手，對不同實(shí)例進(jìn)行分析，比如辞做，在何種情況下插入節(jié)點(diǎn)會(huì)（或者不會(huì)）導(dǎo)致屬性改變琳要？首先要通過這種簡單的運(yùn)算得到直觀，再詳細(xì)閱讀課本印證自己的觀點(diǎn)秤茅。簡而言之稚补，作圖將會(huì)給你帶來理解上的幫助。
當(dāng)困難到來的時(shí)候嫂伞、考驗(yàn)到來的時(shí)候孔厉，離進(jìn)步就不遠(yuǎn)了。你只需要深呼吸帖努、沉一口氣撰豺，把它攻克下來！ 當(dāng)然也需要講一點(diǎn)學(xué)習(xí)技巧拼余。1污桦、手頭有筆紙，把5種RBT的屬性記下來作參考匙监。2凡橱、根據(jù)不同的實(shí)例不斷畫圖。3亭姥、跟著作者的思路稼钩，doubly-black node是一個(gè)關(guān)鍵。4达罗、對RBT不要著急編程坝撑，不要讓程序成為你理解的絆腳石。先理解粮揉，讓程序成為你加深理解的工具巡李。
問題：為何在RBTree中使用T.nil取代原來BSTree中的NIL？
回答：首先要注意到T.nil是object扶认，具備各種attributes侨拦；不同的是，NIL只是一個(gè)標(biāo)記辐宾。其次狱从，T.nil的作用很大，書本用了一個(gè)高度概況的字眼來描述：處理RBTree處理中的邊界條件叠纹。實(shí)際上矫夯，在詳細(xì)分析算法的時(shí)候，對RBTree進(jìn)行處理的幾種操作包括對葉子的操作吊洼，比如训貌，旋轉(zhuǎn)。這個(gè)時(shí)候葉子就不能僅僅是一個(gè)標(biāo)記冒窍，而是一個(gè)完整的對象递沪。這種情況很多，你如果沒有發(fā)現(xiàn)综液，說明你對算法的分析沒有覆蓋算法執(zhí)行的許多情形款慨。為什么要統(tǒng)一用一個(gè)T.nil？答案就簡單了谬莹，節(jié)省空間檩奠。這是一個(gè)好問題桩了。如果你沒有理解到這個(gè)問題的價(jià)值，說明你沒有真正理解T.nil的作用與意義埠戳。
- 其實(shí)代碼并沒有怎么重要井誉，但是，如果有一位同學(xué)寫了代碼整胃，還是參考一下吧： 16級(jí)某同學(xué)的代碼 颗圣。
第14章 數(shù)據(jù)結(jié)構(gòu)的擴(kuò)展
本節(jié)內(nèi)容試圖在“教科書式”數(shù)據(jù)結(jié)構(gòu)與“工程實(shí)踐中”的數(shù)據(jù)結(jié)構(gòu)之間搭建橋梁，通過實(shí)例展示在工程實(shí)踐中如果擴(kuò)展教科書數(shù)據(jù)結(jié)構(gòu)來完成特定的功能屁使、滿足相關(guān)的要求在岂。大部分的情況下，我們只需要“擴(kuò)展”教科書數(shù)據(jù)結(jié)構(gòu)蛮寂，而無需重新定義全新的數(shù)據(jù)結(jié)構(gòu)蔽午。那些張口就說“學(xué)校授課內(nèi)容很重要，但是......”“老師授課只注重理論酬蹋，缺乏實(shí)踐......”的人請閉嘴吧祠丝，至少你要明白什么是“工程實(shí)踐”再說話，明白教科書除嘹、老師怎么理解“工程實(shí)踐”再瞎說吧写半。
這一部分的內(nèi)容主要還是關(guān)于紅黑樹。
1尉咕、動(dòng)態(tài)序性統(tǒng)計(jì)
紅黑樹的一種應(yīng)用叠蝇，在節(jié)點(diǎn)中增加某些信息，用于講O(n)復(fù)雜度的序性統(tǒng)計(jì)下降到O(lg n)年缎』诖罚可作為第二節(jié)的引入。
2单芜、如何擴(kuò)展數(shù)據(jù)結(jié)構(gòu)
四個(gè)步驟蜕该，一個(gè)定理。
3洲鸠、區(qū)間樹
這一節(jié)是對第2節(jié)所提出方法的具體實(shí)例堂淡。
本部分難度不大，但考慮到本部分需要大量的編程扒腕，10天時(shí)間完成吧绢淀！搞完了就安心過春節(jié)了。
第四部分 高級(jí)算法設(shè)計(jì)與分析
高級(jí)瘾腰，到底高級(jí)在哪里皆的？Advanced，我寧愿理解為“更進(jìn)一步”的蹋盆。在此之前的算法設(shè)計(jì)與分析只有分治法费薄，到了這一章我們并不是拋棄分治法另起爐灶硝全，而是，進(jìn)一步楞抡，進(jìn)一步......伟众，一步一步地使得算法具有更好的效率。如果這么想拌倍，整個(gè)思路就很清晰了：動(dòng)態(tài)規(guī)劃這一章就是講當(dāng)大問題分解成子問題，如果重復(fù)的子問題不斷出現(xiàn)該如何解決噪径。貪心算法更進(jìn)一步柱恤，如果子問題的分割在特定問題的時(shí)候具有某種可利用的屬性，那么我們可以如何優(yōu)化算法找爱。因此梗顺，不要被“高級(jí)”嚇倒，也不要被“高級(jí)”誤導(dǎo)：這里的內(nèi)容不存在更高級(jí)別的抽象车摄，而且思路與之前的內(nèi)容聯(lián)系緊密寺谤，并非邏輯關(guān)聯(lián)性不強(qiáng)的飛躍。因此吮播，第一個(gè)問題必須改成：Where do you advance from变屁？
第15章 動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃只是一個(gè)名詞，完全無法體現(xiàn)其應(yīng)有的內(nèi)涵意狠。
這是16級(jí)某同學(xué)的筆記粟关。
第16章 貪心算法
第17章 平攤分析法
平攤分析的目的？
平攤分析的三種方法：累加平均环戈、記賬法闷板、勢能分析法。
理解的難度不大院塞。最大的收獲在講解習(xí)題拖吼、看視頻（競爭分析）求冷。
如何靈活使用？
以上內(nèi)容，從閱讀的角度这难，一個(gè)星期也許夠了，但是從做題的角度看沪蓬，我無法估計(jì)肋僧！建議盡可能快地完成本部分閱讀。然后進(jìn)入一個(gè)反饋循環(huán)鞠抑，再閱讀再討論饭聚，加強(qiáng)習(xí)題。
第五部分 高級(jí)數(shù)據(jù)結(jié)構(gòu)
第18章搁拙、B樹
平衡的搜索樹秒梳，主要用于磁盤檢索法绵。每個(gè)節(jié)點(diǎn)有多個(gè)鍵值，有多個(gè)孩子節(jié)點(diǎn)酪碘。我認(rèn)為需要提醒的兩點(diǎn)：插入只在葉子進(jìn)行朋譬；刪除可在任意節(jié)點(diǎn)進(jìn)行。葉子的定義與BST樹有重大區(qū)別兴垦。
第19章徙赢、Fibonacci堆
1、之前有Binary Heap的內(nèi)容探越，為何要提出Fibonacci Heap狡赐？有何優(yōu)勢？有何劣勢钦幔？具體操作怎么做枕屉？復(fù)雜性是多少？解決這些基本問題鲤氢。
2搀擂、這種Heap與Fibonacci數(shù)列有什么關(guān)系？這是難點(diǎn)卷玉。
第20章哨颂、van Emde Boas樹
發(fā)明者Peter van Emde Boas，荷蘭科學(xué)家相种。簡記為vEB樹咆蒿。
第21章、用于不相交集合的數(shù)據(jù)結(jié)構(gòu)
高級(jí)數(shù)據(jù)結(jié)構(gòu)之所有“高級(jí)”的原因是什么蚂子？ “進(jìn)一步”沃测，到底是如何進(jìn)一步的？思考食茎！
第六部分 圖算法
第七部分 高級(jí)專題
Appendix A. 本文助記符（統(tǒng)一借助LaTex的記號(hào)）
1蒂破、"^" 代表“帽子”，N^2表示N的平方别渔。
2附迷、“_"代表下標(biāo)，比如n_2表示n帶下標(biāo)2哎媚。
3喇伯、"\in" 表示集合的包含關(guān)系，比如拨与，A \in B表示A集合是B集合的子集稻据。
4、BigO买喧，Theta捻悯，Omiga匆赃，一個(gè)英國朋友，兩個(gè)希臘朋友:-D
5今缚、floor算柳、ceiling，分別代表下取整與上取整的那兩個(gè)符號(hào)姓言。
Appendix B. 相關(guān)網(wǎng)絡(luò)資源
0瞬项、CLRS的主頁
1、《算法導(dǎo)論》網(wǎng)易公開課
2何荚、作者之一Cormen的主頁
3囱淋、作者之一Rivest的主頁（大名鼎鼎的圖靈獎(jiǎng)得主啊Ｊ奁）
4绎橘、Khan Academy‘s algorithms tutorials
5胁孙、進(jìn)階閱讀：Readings in Algorithms唠倦，Stanford的一門課程，里面有比較前沿的papers列表涮较，還有我希望大家可以學(xué)習(xí)的FFT稠鼻。留給我自己看看。
6狂票、Algorithm Unlocked候齿，CLRS作者之一的Cormen的新作，據(jù)說比CLRS更淺顯易懂闺属。我看過目錄和部分章節(jié)慌盯，易懂也許是的，但是內(nèi)容就少了很多掂器，而且論述的順序與風(fēng)格充滿了作者的個(gè)人趣味亚皂。按作者的本意來說，Algorithm Unlocked只是一盤開胃菜国瓮，可以作為學(xué)習(xí)CLRS的輔助閱讀灭必。我看確實(shí)如此！然而我看不出有任何理由推薦我的學(xué)生去看這本書乃摹，因?yàn)閷Υ蟛糠值娜硕赃@真是很大一盤餐前小點(diǎn)禁漓，你很容易就找出很多很多理由拒絕進(jìn)行這樣的學(xué)習(xí)：哇啊是英語；哇啊真是太理論孵睬；哇啊我又不做科學(xué)家.....如果你真的下決心去吃它播歼，還不如立即開始CLRS。如果你不下決心掰读，去淺嘗則止荚恶，收獲也不會(huì)很多撩穿，那還不如不看。（2015年2月5日補(bǔ)記.）
7谒撼、Algorithms食寡，Papadimitriou等人2006年出版的一本算法書，我經(jīng)常翻看廓潜，還不錯(cuò)抵皱，篇幅小，簡潔辩蛋。有中文注釋版名為《算法概論》呻畸，推薦購買。這是一篇網(wǎng)絡(luò)評(píng)論悼院。
8伤为、Algorithm Design，Jon Kleinberg 等人2005年的著作据途，非常著名绞愚。不適合入門，有些高級(jí)且較新的內(nèi)容颖医。這里有Lecture Slides.（當(dāng)年大一就抱著它啃的哪位同學(xué)估計(jì)已經(jīng)放棄算法學(xué)習(xí)了吧......）
9位衩、http://codeforces.com/，競賽網(wǎng)站熔萧？據(jù)說有很多好的代碼糖驴。
10、MIT 6.006: Introduction to Algorithms. 2011
