如何正確地擼《演算法導論》？

01-08

大四，通信工程，做Linux c軟體開發，尚未去公司，（水平只有寫寫鏈表，進程線程式控制制的地步。）想在畢業前多學點東西，每天花費2小時看《演算法導論》目前看了三天，到第四章最大子數組這裡。我有點擔憂，因為能大致看懂數學推導和漸進記號,但是自我推導和證明很吃力。想只看偽代碼和設計思路，不知道只看偽代碼和設計思路會不會影響後面的內容看不看的懂？求擼完的大佬們分享一下學習方法唄！（為什麼我感覺網易公開課上的課沒有看書好？不看書完全聽不懂在講啥而且板書慘不忍睹...)

同意輪子哥的。看你的目的了。演算法導論是計算機系學生的演算法參考書，我曾經在初中就大概把裡面的偽代碼都敲過一遍了，一度自以為自己很懂，然而博士越念發現演算法導論裡面自己不懂的東西越多。

這本書的最大意義就在於它把一些很難的演算法分析用儘可能簡單的零基礎的入門選手能看懂（雖然是這麼說但是很多時候還是得翻參考文獻裡面的論文，很多書里的話看著好像懂其實事後看完全不得要領）的方法來講。這樣寫書看似簡單，但是其實非常非常難。所以從本質上而言，演算法導論是一本工具書。怎麼用一本工具書，那當然要看你本身要幹什麼了。

最常用的用處肯定是查定義和查參考文獻了。查定義自不必說，肯定比維基還要精確。另外演算法導論每一版都會把最近新的研究結果加入到文獻列表裡。但是用演算法導論學演算法反而有點難，畢竟學漢語你用本新華字典總不是最有效率的途徑（雖然沒這麼誇張）。

之前用了兩個多月擼完了演算法導論，每天3小時左右。把其中的偽代碼用Python實現了一遍，代碼在這裡https://github.com/gycg/Algorithm。偽代碼轉換成Python還是比較容易的，一行一行翻譯，寫完運行一下，不懂的地方改一改，試一試，有助於理解演算法思路。

其實演算法本身不難，第一遍可以只看偽代碼和演算法思路。如果想進一步理解的話，第三章那些標記法是非常重要的，就算要花費大量時間才能理解，也不要馬馬虎虎略過。因為以後的每一章，講完演算法就是這樣的分析，精通的話，很快就讀完了。你所說的證明和推導大概也都是在第三章介紹了，可以回過頭再認真看幾遍。

至於課後題，比較難，我只做了前幾章，如果要做完需要更多時間和精力。這可以通過之後做演算法題來彌補，可以去leetcode等網站找一些經典的演算法題做一做，加深理解。

這裡有一個Facebook的工程師寫的攻略，介紹了用演算法導論來應付面試應該讀哪些，略過哪些，英文的，可以作為參考：（剩下的可以收藏慢慢看，順便點個贊謝謝！）

Chapter 1

Interesting read, but you can skip it.

Chapter 2

2.1 Insertion
Sort - To be honest you should probably know all major sorting
algorithms, not just insertion sort. It"s just basic knowledge and you
never know when it can help.
2.2 Analysis of Algorithms - you can skip the small intro, but know the rest.
2.3 Designing
algorithms - contains merge sort and its analysis as well as an
overview of divide-and-conquer, very important stuff, so worth a read.

Chapter 3

All of it. You have to know big-O notation and time complexity analysis, period.

Chapter 4

4.1 Maximum
subarray problem - Can kind of be worth your time. There are better
solutions to this problem than divide and conquer but it"s good practice
and the flow of logic may help develop how you think.
4.2 Strassen"s
algorithm - I really love this algorithm and was astounded at how cool
it was the first time I saw it, but you can skip it for the interviews.
It won"t come up.
4.3 Substitution method - you won"t be using
this method in an interview, but you should know it since it"s a basic
tool for finding the time complexity of a recursive algorithm.
4.4 Recurrence tree method - same as 4.3
4.5 Master
method - essential knowledge. You should know it and practice with it
and be able to use it in 3 seconds. This is the method you would use in
an interview if analyzing a recursive algorithm that fits the form.
4.6 Proof
of the master theorem - you can probably skip this, though it"s good to
read at least once so that you understand what you"re doing with the
master method.

Chapter 5

I"ve never read this chapter, to
be honest, but what I know is that you need a basic grasp of
probability in interviews because there"s a good chance they may come
up. That said, as long as you know basic probability concepts and
practice on probability-related interview problems (there are such
problems with solution explanations in Elements of Programming Interviews,
the book I recommend for interview prep), you can probably skip this
chapter. From a cursory glance, it"s more math than algorithms.

Chapter 6

6.1, 6.2, 6.3, 6.4, 6.5 - Heaps and heapsort. Check.

Chapter 7

7.1, 7.2, 7.3 - Quicksort
and its randomized version. Need-to-know concepts. I also recommend 7.4
(I was once asked in an interview to high-level-analyze a randomized
algorithm), though the probability you have to deal with something like
7.4 in an interview is pretty low, I"d guess.

Chapter 8

8.1 - Lower
bounds on sorting - Yes. Basic knowledge. May be asked in a Google
interview (though unlikely, I know of a case it happened in before).
8.2 - Counting sort - Need-to-know in detail. It comes up in disguised forms.
8.3 - Radix sort - Yup. It"s an easy algorithm anyway.
8.4 - Bucket sort - can skip.

Chapter 9

9.1 - Small section, worth a read.

9.2 - Selection in expected linear time - Very important,
as it"s not common knowledge like quicksort and yet it comes up often
in interviews. I had to code the entire thing in an interview once.
9.3 - Selection
in worst-case linear time - Can skip. Just know that it"s possible in
worst-case linear time, because that might help somewhat.

Chapter 10

10.1 - Stacks and queues - basic knowledge, definitely very important.
10.2 - Linked lists - same as 10.1
10.3 - Implementing pointers and objects - If you use C++ or Java, skip this. Otherwise I"m not sure.
10.4 - Representing rooted trees - Small section, worth a quick read.

Chapter 11

For
hashing, I"d say the implementation isn"t as important to know as, for
example, linked lists, but you should definitely have an idea about it
and most importantly know the (expected and worst-case) time
complexities of search/insert/delete etc. Also know that practically,
they"re very important data structures and, also practically, the
expected time complexity is what matters in the real world.
11.1 - Direct addressing - Just understand the idea.

11.2 - Hash tables - important.
11.3 - Hash
functions - it"s worth having an idea about them, but I wouldn"t go too
in-depth here. Just know a couple examples of good and bad hash
functions (and why they are good/bad).
11.4 - Open addressing - Worth having an idea about, but unlikely to come up.
11.5 - Perfect hashing - skip.

Chapter 12

12.1 - What is a binary search tree? - Yep.
12.2 - Querying a BST - Yep. All of it.
12.3 - Insertion/Deletion - Same as 12.2
12.4 - Randomly built BSTs - just know Theorem 12.4 (expected height of random BST is O(lgn)) and an idea of why it"s true.

Chapter 13

This one is easy. Know what a Red-Black tree is, and what its worst-case height/insert/delete/find are. Read 13.1 and 13.2,
and skip the rest. You will never be asked for RB-tree insert/delete
unless the interviewer is "doing it wrong", or if the interviewer wants
to see if you can re-derive the cases, in which case knowing them won"t
help much anyway (and I doubt this would happen anyway). Also know that
RB-trees are pretty space-efficient and some C++ STL containers are
built as RB-trees usually (e.g. map/set).

Chapter 14

Might be worth skimming 14.2 just
to know that you can augment data structures and why it might be
helpful. Otherwise do one or two simple problems on augmenting data
structures and you"re set here. I"d skip 14.1 and 14.3.

Chapter 15

DP! Must-know.
15.1 - Rod-cutting. Standard DP problem, must-know.
15.2 - Matrix-chain
multiplication - same as 15.1, though I don"t particularly like the way
this section is written (it"s rare for me to say that about CLRS).
15.3 - Elements
of DP - worth a read so that you understand DP properly, but I"d say
it"s less important than knowing what DP is (via the chapter
introduction) and practicing on it (via the problems in this book and in
interview preparation books).
15.4 - LCS - same as 15.1
15.5 - Optimal binary search trees - I"ve never read this section, so I can"t argue for its importance, but I did fine without it.

Chapter 16

You should definitely know what a greedy algorithm is, so read the introduction for this chapter.
16.1 - An activity selection problem - Haven"t read this in detail, but I"d say check it out, if not in-depth.
16.2 - Elements of the greedy strategy - same as 16.1
16.3 - Huffman
codes - I"d say read the problem and the algorithm, but that"s enough.
I"ve seen interview questions where the answer is Huffman coding (but
the question will come up in a "disguised form", so it won"t be
obvious.)
16.4 - Matroids and greedy methods - I"ve never read
this section, but I"ve done a lot of greedy problems during interview
prep and this stuff never came up, so I"d say this section is irrelevant
for the interview.
16.5 - Task-scheduling problem as a matroid - Same as 16.4.

Chapter 17

Okay,
you should definitely know what amortized analysis is, but I"ve never
read it from the book and I feel it"s a sufficiently simple concept that
you can just Google it and check a few examples on what it is, or
understand it just by reading section 17.1. So:
17.1 - Aggregate analysis - read this, it explains the important stuff.

17.2, 17.3, 17.4 - Skip.

Chapter 18

You
should probably have an idea of what B-Trees (and B+ trees) are, I"ve
heard of cases where candidates were asked about them in a general sense
(high-level questions about what they are and why they"re awesome). But
other than that I"d skip this chapter.

Chapter 19

Fibonacci heaps - nope.

Chapter 20

van Emde Boas Trees - double, triple, and quadruple nope.

Chapter 21

Disjoint sets
Update:
I originally recommended skipping this section, but on reconsideration,
I"ve noticed that it"s actually more important than I originally
thought. Thus, I recommend reading sections 21.1 and 21.2, while skipping the rest.

Union-find
is somewhat important and I"ve seen at least one problem which uses it,
though that problem could also be solved using DFS and connected
components. That said, I also believe that it"s not strictly necessary
because one can probably, for interview purposes, come up with a similar
enough structure easily to solve a problem which requires union-find,
without knowing the material in this chapter. However, I believe it"s
worth a read so that if a problem comes up whose intended solution is a
union-find data structure, you don"t spend time in an interview coming
up with it, and rather know from before, which can be a good advantage.
Still, I"d probably rank it as less important than most of the other
material in this list, and even less than other material that"s not even
in CLRS (like tries, for example).
Okay, now graph algorithms. First read the introduction. Now, there"s a lot to know here, so hang on.

Chapter 22

22.1 - Representations of graphs - Yes.
22.2 - BFS - Yes. After you do that, solve this problem: ACM-ICPC Live Archive - Kermit the Frog. The whole "state-space search using BFS" thing is an important concept that might be used to solve several interview problems.
22.3 - DFS - Yes.
22.4 - Topological sort - Yes.
22.5 - Strongly connected components - much less likely to come up than the above 4, but still possible, so: Yes.

Chapter 23

Minimum
spanning trees - probably the least important graph algorithm, other
than max flow (I mean for interview purposes, of course). I"d still say
you should read it because it"s such a well-known problem, but
definitely give priority to the other things.
23.1 - Growing a MST - sort of, yes.
23.2 - Prim and Kruskal"s algorithms - sort of, yes.

Chapter 24

Shortest path algorithms are important, though maybe less so than BFS/DFS.
Read
the introduction. You should, in general, read all introductions
anyway, but this one"s important (and long), so it warranted a special
note.
24.1 Bellman-Ford - Know the algorithm and its proof of correctness.
24.2 Shortest paths in DAGs - definitely worth knowing, may come up, even more so than Bellman-Ford I"d say.
24.3 Dijkstra"s
algorithm - Yes. Of course. I"ve seen this come up multiple times (with
slight variations), and I"ve even seen A* come up.
24.4 Difference constraints and shortest paths - Skip.

Chapter 25

Read the intro as well.
25.1 - Matrix multiplication -I"d
say skip. It might be possible for this to come up (very very slim
chance that it does though), but the chances are so low in my view that
it"s probably not worth it. If you have some extra time, though, give it
a read.
25.2 - Floyd-Warshall - Yep, worth knowing the
algorithm and its time complexity and when it works (which is for all
weighted graphs, except ones with negative weight cycles). Its code is
something like 5 lines so there"s no reason not to know it. The analysis
might be a bit overkill though.
25.3 - Johnson"s algorithm - Skip.

Chapter 26

Maximum flow - I"ve never heard of this coming up in an interview and I can"t imagine why it would, so skip.

Chapters 27+

Most
of this stuff is never going to come up, so it"s easier for me to tell
you what to actually read than what not to read, so here are a few
selected topics from the Selected Topics in the book:
Chapter 31
Most
of what you should learn from this chapter you can learn from
practicing on interview problems from Elements of Programming Interviews
(and your time is better spent doing that), so I"d say skip it all
except Euclid"s algorithm for the GCD, under section 31.2.
Chapter 32
32.1 - Naive method - just read it quickly.
32.2 - Rabin-Karp
- I"d say you should know this, the rolling hash concept is very
important and can be useful in many string- or search-related interview
problems.

Appendices

A - Summations
Know the important summations for time complexity analysis.
C - Counting and Probability
Give C.4
a read if you don"t know the material, Bernoulli trials may come up in
problems (not explicitly, but you might use them, specifically for time
analysis of questions that involve probability/coin flips).

最近一直在刷CLRS，發現自己的演算法能力有了很大進步，相比之前主要是對演算法思想的理解更深入了一些。下面是自己的幾點看法

CLRS著重於設計思想，學它之前應該需要有一定的數據結構與演算法基礎，否則看起來應該會很吃力。
書的第一部分比較重要，後面的很多演算法證明推導，複雜度計算是基於前面介紹的一些定理，例如循環不變式證明，主方法等。
再往後看的時候，應該明確自己的目標。如果為了複習加深入理解一些演算法，那麼在讀的時候就可以選擇性跳過一些證明，側重於看演算法部分，反之亦然。
在刷的時候可以常備一本輔助用書結合來看，例如那本《演算法》。CLRS對於某些問題講解的很棒，例如動態規劃，貪心演算法等，但也有一些講的不那麼明白，例如紅黑樹就略顯複雜，這時可以參考輔助用書。
書的最後一部分其實可以當作工具書來用了，了解一下即可，需要的時候再深入學習。
課後習題應該還是蠻重要的，但如果全做完需要的時間太多，我也只是選擇著來做。解題答案可以參考https://sites.google.com/site/algorithmssolution/。

關於公開課，本來課就是配合書的，書才是重點，而且算導的題很精華，不做效果出不來。

算導是為理論研究打基礎的，教一些基礎的演算法，更重要的是讓你學會怎麼去分析和表達演算法以及怎麼從數學上證明演算法的效率和正確性。

如果不是僅僅是用到某些演算法不用擼這本書，如果需要時常設計新演算法或有興趣，可擼。擼的方法就是讀書做題，然後可以配合oj題一起做。認認真真做完題，對好答案，確認掌握了再前進。算導不需要嚴格按順序讀，內容基本是相互獨立的，當然後面的會難些。

PS:6小時4章，題主估計沒做題而且略過了不少。不看證明推導，不做題，那就捨本逐末了，光要學演算法不接觸理論不妨另選書籍(程序設計競賽，面試的書)。或者也可以先略讀，之後重讀。

算導的內容分為幾方面，而且有可能穿插在一起，所以個人認為比較的做法是每次讀的時候挑重點看，大概下面幾方面吧：

1 複雜度理論，主要集中在前面幾章，雖然很理論但是一定要看懂，因為很多定義和定理後面用得上

2 數據結構介紹，這個可以找本數據結構書輔助看，有些書的數據結構的內容比算導通俗點，但是算導更嚴謹，所以最後還是得過來看懂（但是有些內容當理論看看即可，比如散列表大小的一些設計只是理論研究，實際中的HashTable用的是更實用的辦法）

3 設計思想，比如貪心，DP之類，這個可以集中看

4 演算法的複雜度證明什麼的，一開始不懂就先不要深入細節，後面水平上來了再補

5 亂七八糟的演算法雜燴和理論介紹，比如字元串相關演算法，fft，P和NP等，這種感興趣可以看，或者當成是參考書，用到時候查也行，其實可以查其他更詳細的書籍資料

6 習題，有一些重要的結論在習題里

7 思考題，裡面介紹了一些理論比較簡單（正文懶得寫）的東西，但是這些東西在實踐中反而可能很實用（跳錶，Treap之類）

這書並不適合所有人。我看這書的時候，發現很多地方的證明過程並沒有用數學進行形式證明而是用文字講道理，導致會產生很多歧義。後來我換了普林斯頓老爺爺的紅書就好多了。

因為紅書壓根就不證明。

那要看你的目的是什麼。如果是為了寫出更好的程序，那你完全不需要知道其中的道理，在保證能夠把偽代碼抄進你喜歡的語言的前提下，把什麼演算法適用於什麼條件都背下來就行了。如果你的目的是為了以後搞科研發明新演算法，當我沒說。

看一本書之前，應該先看看前言之類的，一般都會說這本書適合什麼樣的人。個人覺得，演算法導論並不適合每一個人。

不要因為別人說書好，就跟風去看。書確實是好書，但你要適合看才行。

《演算法導論》不適用於新手入門學演算法，講得太細節，很容易失去對整體的把握，而且也會對自己造成極大的挫敗感。我覺得一本好的教材最要的不是帶給你多少詳細的知識，而是能帶給你繼續探索的興趣和慾望。這種字典一樣的書我是看了就懵逼，如果是大神，當我沒說

別盲目崇拜算導，覺得想找工作就靠刷它。- 刷它還不如刷leetcode. 其實你看任何一本演算法，比如演算法之美什麼的，都比算導更省力氣。

而且演算法其實你要明白的是原理，弄明白原理然後自己換幾種語言實現一下，而算導講原理卻恰恰一點也不生動有趣，非常令人捉雞。

所以更懶的辦法是隨便去跟個名校演算法公開課，都學過一遍以後來算導看看有什麼缺漏卻有意思的演算法，抽籤實現幾個自己不熟練的，做幾道自己覺得難的思考題。

學習嘛，貓有貓路，狗有狗道。

說一下我的看法，不喜勿噴！

首先呢，《演算法導論》是本好書，但是看這本書，是需要一些基礎的。

要是想學演算法的話，可以先去看看嚴蔚敏老師的那本數據結構與演算法，

《清華大學計算機系列教材：數據結構（C語言版）》(嚴蔚敏，吳偉民)【摘要書評試讀】- 京東圖書

這本書，就比較難了，要是能把這本書搞定，我們可以再去看《演算法導論》。

當然了，要是你已經搞定了嚴蔚敏老師的那本數據結構與演算法，就忽略上面我說的。

歡迎關注我的微信公眾號：小期科技，一起探究C/C++。

PS：目前本人在北京做軟體測試工作，想了解軟體測試的話，也可以聯繫我，不要多想，我只是給自己拉粉。

第一次更新！

學習，是需要循序漸進的。現在看《演算法導論》，很明顯，就是想學習演算法。但是，最基本的演算法你都掌握了嗎？常用的查詢和排序演算法，你都能寫出來嗎？

對於一個初學者，無論他是看演算法導論，還是看一本普通的書，他所能接受的知識都差不多，為何這麼說？因為知識是一個系統的工程，沒有前期的基礎，很難掌握後期的複雜知識。

第二次更新！

關於初學者選教材，說一下我的看法，僅供參考。

不管是學習C語言、C++，還是學習數據結構什麼的，對於初學者，尤其是自學的同學，在選教材時，我們可以先不選那些「高大上」的教材，什麼是「高大上」的教材？舉個例子，初學者學習數據結構與演算法，上來就看演算法導論，理想是好的，但是能不能實現就是另一回事兒了，那麼複雜的書，我相信初學者是很難看懂的。

那麼我們應該怎麼選教材呢？個人建議，我們可以參考大學的教學思路，也就是說，大學用什麼書講課，我們用什麼書入門。

為什麼這麼說呢？這是因為大學的教學思路是針對大多數人的「智力」水平的，看大學的教材，我們很容易入門。

以上為個人建議，僅供參考！

個人提個小意見，找類似的幾本書，同一內容橫向對比讀一下，或許會有不同的效果出現。

基於一個有價值的應用場景深入的去想解決方法。比如如何用演算法設計公交車線路，如何設計知乎回答排名演算法，如何預測房價……

以演算法書為參考書來尋求解決方案，理解演算法本質原理。不要硬啃，記住答案沒用。

如何我告訴你，這個問題解決方案值一百萬，你什麼演算法都學得會。

強擼，別找借口嫌痛苦

很簡單每年翻一次思考一次。

關注了這個問題下一些大神的回答。

從計算機新人的角度來講，上了一門主要講這本書的課，跟了2/5，這本書的數學部分沒有想像中的那麼難，做為數學渣滓沒有明顯閱讀障礙，有些證明看的很有爽感，中文英文可以一塊兒看，平時看中文，遇到看不明白的地方看原版，配合習題效果更佳。

然而據說看了對找工作並沒有什麼卵用，而且巨花時間，於是決定退課擼題及看普林老爺爺的紅寶書。

《演算法導論》是演算法經典書，很多人都推薦算導，我也覺得學演算法必看，但是它對很多初學者而言不大適合入門，入門書需要圖解多，簡單易懂的，推薦先看《趣學演算法》入門，圖解多，有源碼直接運行，快速理解實踐演算法，然後再看算導就簡單多了。

同通信大二，我們在學演算法導論。老師說這本書的重點是證明，還有理解並構造循環不變式，剛入門也不知道對不對。

ps:電子類的外國教材還是看英文原版好。

你覺得痛苦的話，一定前面的題目沒有好好做，題目有本章總結的作用。嫌煩不想寫的話，答案至少是要看一下的。github是有很多clrs的答案的。

這是一本有門檻的書！

我校演算法入門課的教材就是演算法導論。感覺上課和作業都是大部分時間都花在了證明上。一些沒有基礎的轉專業同學也搞定了這門課。可能是有壓力才有動力。

以及感覺中文版有的地方翻譯得有點奇怪，建議看英文的。