算法（第4版）

是本非常精妙的算法書，雖然dfa和nfa我始終沒看懂，第六章np=p等的抽象證明定理更像是在捶我的腦袋，這絕對是我水平不夠。總結下來算法真的是基礎中的基礎，我們平時習以爲常的開發中所用的數據結構、很多大型軟件和數據存儲工具，基本都有底層精妙的算法所支撐。而人類對於解決實際問題的更有效率的算法的追求仍在孜孜不倦的進行當中。這個過程堪稱波瀾壯闊又枯燥乏味，以前從未將算法深入到這個層面，也不知以後是否有機會去用他們去針對性的解決實際問題，突然覺得這些算法很美。[壞笑]

示例代碼主要使用Java語言實現，涵蓋了很多基礎且重要的算法，像排序、搜索、圖算法等，對每種算法的講解都細緻入微，包含原理、實現步驟、複雜度分析，可以作爲工具書，系統構建算法知識體系。 建議可以先看《大話數據結構》再看《算法》，這樣或許更易理解和吸收。

什麼叫態度，什麼叫好書，這就是最好的範例。 很基礎很強大，對於初學者的我來說一遍顯然是不夠的。算法應該何時開始看呢？C/C++-->數據結構-->算法，這是我認爲的順序，當然我是做底層的。c/c++是數據結構的基礎，數據結構看了鏈表隊列二叉樹等等後就是真正的算法，哦哦，還有更一步，當代算法：神經網絡，機器學習。這裏是基礎。 是我讀過的講的最清晰的算法書。

從隨性稚氣的“到此一遊”到踏實走完旅程的“天地之悠”，密密麻麻的註解和筆記如雪泥鴻爪，書評是短暫的落腳印記，廣闊天地纔剛開始。儘管英文原著有不少的印刷錯誤，在此之上譯者又製造了成倍的錯漏，在我成才的路上埋下了豐富多彩的障礙：刺釘，蟒蛇，水坑，陷阱，惡龍（八十一難，折磨不休），但仍然無損原著的經典光輝，生花妙手。其內容之豐富，安排之巧妙，使我全書通讀三遍後才參悟一字一句的精妙，一遍掃讀跌跌撞撞，滿身傷痕；二遍掌握要領，統領全局；三遍理清所有細節，全方位無死角，豁然開朗。第四遍，第五遍，...，哪怕十年後的第十遍，仍將收穫匪淺，歷久常新。原著排本精美，白底與黑字之間間距恰當，代碼佈局有致，圖文並茂，並以紅灰二色與黑作配，紅灰黑三色不致繁亂亦不顯單調。然而本譯作排版堪稱醜陋，只剩黑色，圖和代碼都只是原書剪過來的貼圖，觀感極不友善。有鑑於此，讀者需與原著共讀爲宜，同時瀏覽英文原著的官方網站（包括新勘誤表），並搜索網上更廣泛的疑問和解答。從起初濃重的挫敗感到遊刃有餘的開朗，腳踏實地，一步一步歷盡艱辛，那些門檻一旦跨過，我就再也回不到“愚昧”的初態，通過努力換來的經驗和智慧不可撤回，現實中不會有韓國男主戲劇般的患癌車禍失憶（如果有請安排我一個年輕美貌的女主），也沒有生生世世屎尿屁一世又一世的輪迴（如果有生而爲貓賣萌不用學算法）。因緣皆由我起，與好書結緣皆因造化，專注當下，踏實生活，冥想前行，知行合一。 本書僅設六大章，基礎(Fundamentals)，排序(Sorting)，查找(Searching)，圖(Graphs)，字符串(Strings)，背景補充(Context)，目錄何等短小菲薄，而且看似老生常談，還能教出什麼新意嗎？對於我來說，只第1章就值回票價，鉅額回報。"Fundamentals"一詞舉足輕重，足以在其後面加三個歎號。每個領域的"Fundamentals"(基礎，基本原理)都是至關重要的。基礎學不好，頭皮撓到老，一理不明，則百竅不通。就好比數學宗師柯朗說，”所有的數學命題最終應歸結爲關於自然數的命題，這一點已變成了現代的指導規則... 我們把自然數及其兩種基本運算--法和乘法--當作已知概念接受下來”，粗略的說，自然數和加乘兩種運算就是數學的全部。現代數學的代數結構-羣，新詞說舊話，以結構的視角重新表述加法和乘法的交換律，結合律和分配律。用新定義考察原舊事物，我們的認知便得到昇華。回到《算法》，作者開篇即點明，“算法與使用的語言無關，即可用自然語言描述，又可用編程語言，是這種方法而非計算機程序本身描述瞭解決問題的步驟。”，這樣平平無奇的一句話，原本在我眼中可有可無，但研究哲學，數理邏輯，語言學和數學後則意義非凡，它直指符號的形(能指)和實(所指)的區別和統一，語言(符號)不是所談論的實體本身，但是實體必須要以符號形式顯露才能被人談論。任何一個領域的研究對象都是符號化了的對象，哲學的"存在與無限"，邏輯的"真假與證明"，寫作的"人物與故事"，科學的"時空和粒子"，數學的"自然數與加法運算"... 當我們談論3時，我們不是在談'3'這個符號，而是在談論'3'指稱的這個實體(不管承不承認它的客觀存在性)，然而我們不是(或不能)直接操作這個實體，而是藉着'3'這個符號在形式系統中的相對位置(即結構中的關係)來刻畫它是什麼的，單純一個"3"沒有實質，它必須放在語句中去顯示它與其它符號的關係，比如"2<3"，比如"3+1=4"。可是語句"3+1=4"也不過是五個不同字符形成的排列組合，在形式系統裏，我們得到的是形式上的結構關係，而不涉及語義。當我們用任何一種編程語言寫下一個算法時，這段代碼僅僅是符號排列組合形成的序列，它不是算法本身，但算法又必須以符號形式顯露才能被我們加以談論和操作，所以我們必然要選擇一門語言才能對它進行研究。第1章三個關鍵詞，基本模型(Basic Programming Model)，數據抽象(Data Abstraction)和算法分析(Analysis of Algorithms)：1. 作者隨意選了Java，因爲它有一定的普遍性和實用性，但對它嚴格地加以限制，形成簡潔的"基本編程模型"，因爲過多的關注特定語法會損害我們理解算法的本質，所謂語言是思維的容器。Java的"反射"和"註解"特性是算法無關的，隻字未提。"泛型"本是算法無關的，但它作爲一種靜態語言的補救手段，用來克服類型限制的缺陷，本書有必要提（動態語言完全沒有這個缺陷）。2."數據抽象"(Data Abstraction)不僅僅是算法的核心概念，是大規模軟件系統構造，乃至整個計算機科學的核心概念。"抽象"(Abstraction)作爲有效的複雜性隔離和控制手段，貫穿整個人類認知體系，它使得從低到高，從簡單到複雜，逐層構建概念系統成爲可能，"抽象"二字在現代數學、物理和邏輯上體現得淋漓盡致。數據抽象將軟件實體(模塊，類型，函數）分爲兩部分：外部行爲描述(API)和內部實現細節(算法+數據結構)，兩者同樣重要。爲了突出前者的重要性，我們甚至可以說API更重要，它是軟件構造的第一步，也是最重要的一步。作者一再強調，精良的API設計需要耗費大量的心血和智慧，粗心的API設計會帶來怎樣的嚴重後果。3."算法分析"大概是算法最能體現數學功底的一面，也是最讓大多數人恐懼頭痛的一面：一是它是數學的抽象的，二是講授者容易對化簡技巧含糊其辭，看上去隨心所欲。它的艱澀來自數列極限概念，它的目的是比較兩個函數f(x)和g(x)增長的快慢，以其中一個函數g(x)作爲另一個函數f(x)的度量標準，給後者劃定上下界，作爲度量單位的基本函數g(x)當然越簡單越好，多項式是最廣泛且簡單的，而且在x趨於無窮時，高階項起決定作用，可以只保留高階項，比如g(x)= 2x^3 + 100x^2 + 7x + 3，丟掉所有的低階項約等於2x^3，記作~2x^3，進一步忽略係數的話，記作同階Θ(x^3)，更粗糙的可以記作上界O(x^3)，O(x^4), O(x^5)....。如果f(x)不是多項式呢，比如x^3 + xlogx + x，篇幅有限，不在這一一展開。數學和科學是最講究確定性的，沒有說不清楚的地方，只有說不清楚的人。如果講授者學藝不精，就可能隨意捨棄某個項，或者丟掉某個係數，讓學生感覺無章法可依，產生迷惑厭惡的牴觸情緒，我當年就被數據結構老師的講解嚇得不輕。可貴的是，作者沒有采用最粗糙的上界符號大O，而是堅持採用最精確的"約等於"符號~。除非算法過於複雜無法(也不值得)計較準確係數時，作者才爽開用大O，留下一句“係數細節就交給頂級的算法專家吧”，你自己就是啊，哈哈哈，在適當之處作取捨，張弛有度，收放自如。況且作者並未在"算法分析"的開始就冰冷地擺出一系列漸近性符號~，O，o，Θ，θ，Ω，ω （你看像不像emoji符號，可愛的咧，數學家和物理家真的很愛希臘符號），而是引導我們作一個科學的觀察者，觀察數據-提出模型-驗證-修正，數據收集很容易的啦，手拿一個秒錶（像當年愛因斯坦測光速一樣），預備~開測！通過數據描成的座標曲線形狀，就能(技巧性地)找到對應函數式。這裏作者一舉解開了困擾我許久的兩個問題，一是如何從大數據中推出準確函數式的。他甚至直接告知，自然現象通常符合冪次法則T(N)=aN^b，我們只要通過數據求得參數a和b即可！在算法中，這個合理的模型是...，不劇透啦。我的天啊，這意味着即使我不知道算法的實現細節(不看代碼)，仍能夠“生套”這個公式，從它運行的時間數據中推出它的複雜度公式。二是算法複雜度不是精確表達式，它只是趨向無窮的漸近式，比如f(x)~2x^3，而不是f(x)=2x^3，我即使測量x=1到10000，也無法驗證漸進式的正確性啊。我能從代碼中用數學方法分析出f(x)~2x^3，但現實中又如何驗證它的正確性呢？作者不經意就提出了"倍率測試"，世間竟有如此聰明腦袋！謝謝你，讓算法分析不再是一個不可觸及的虛構獨角獸，它如同我手中的杯子一樣真實，I was blind but now I see！ 哇，才第一章，還有對象內存佈局呢，不知不覺，說了好多，餘下章節簡略帶過。由淺入深，作者列舉了6種經典的排序方法，不是簡單陳列代碼，而是把每一種都當作獨當一面的寶貴思維方式進行詳解，於是你學到的不是僵直呆板的6份代碼，而是6種通用的思維模式。這6種方式難度各異，選擇排序和插入排序最爲簡單直觀，歸併排序和快速排序最爲精巧，而堆排序所使用的優先隊列影響廣泛深遠(運用於後面章節的圖算法，和人工智能的搜索解算法)。儘管快速排序最爲短小輕巧性能頂尖，但因其非穩定性，並未被編程語言的常規排序方法採用，比如Java採用的是一種歸併排序與插入排序的混合算法-Tim排序。事事無絕對，方顯大智慧。同理，符號表(字典)的兩種普遍查找算法，散列表和紅黑樹並非一方獨佔優勢，散列表只用到線性同餘基本運算，超級容易實現，但無法保證最壞情況下的效率。紅黑樹以難懂聞名（不要企圖背代碼），所以作者特意地先從簡單的二叉樹切入，指出其缺點後順利過渡到平衡2-3樹，然後纔是同構的紅黑樹。紅黑樹不但在最壞情況下的效率得到保證，還支持更多的有序方法，所以被廣泛使用。同樣的，最小生成樹和圖的最短路徑算法，也採用循循善誘的講解方式。全書最虐心的是，將近大結局的，子字符串查找KPM算法和正則表達式查找算法。我當初被折磨得懷疑人生，懷疑自己的智商，三頁書硬是四天翻不過去，喫飯睡覺看電影止不住在想，後來累得不行先放下吧，某天清早刷牙恍然大悟！它們分別運用了確定性有窮狀態自動機(DFA)和非確定性有窮狀態自動機(NFA)，光念名字科技感十足，其實就是通用圖靈機的簡化與擴展。圖靈機的定義，我從書上和網絡看過不下百次。直到現在才明白，圖靈機作爲計算理論最基本的模型如何對應到現代編程語言。我最喜愛的語言之一LISP，則誘導我愛上另一個等價模型，λ演算 (Lambda 演算)。放心，書裏沒詳細提及它倆。但但但，作者尾聲留下"P=NP"世紀大難題呀，什麼P問題呀，NP問題呀，NP-完全問題呀。放心，我不會試圖解答，這一次我視而不見，我可以睡得很安穩也不想留燈，再見~ 最後幾句，遺憾本書未能成爲我心中的第四本神作，就內容的話9.5分，就原著的話8.5分，就譯著的話7分。譯著各色各樣種類繁多的巨量錯漏到底縮短了我多少個有生之年實在無從估算。另一個不大不小的原因是它採用了Java作爲編程語言。算法教程要麼選擇精煉的僞代碼，免去時代侷限性的同時也失掉實用性，要麼選擇一門具體的編程語言，獲得使用便捷性的同時也帶來了時效侷限性。不要誤會，Java在我心中無疑是優秀且佔據特別位置的。但它難免會（可能已經在）衰落。Java會落幕，但使用它的人不會，畢竟它只是一門工具而已。能用Java的人自然可以輕易轉向Python。Python會衰落嗎？當然。但這一次，恐怕要等上百年了，我猜。它如僞代碼般書寫輕便，隨心捕捉你的每一瞬靈感，簡短如數學公式般寫在餐巾紙上，或是附送在郵件中仿效當年數學家和物理學家的書信來往。它又能隨時隨地運行，驗證你的每一個設想，無需工業級的集成開發環境(IDE)，即寫即跑。無論小打小鬧，還是大展宏圖，它都隨時聽候。百年後呢，大家將會用上神之語言-LISP，開玩笑啦~ 當我涉獵各種編程語言，我看到演進的脈絡，和它們身上獨有的特性和使命，我喜愛各種語言，它們都是人類的智慧結晶。接觸過C語言的人會驚歎它的緊湊性，它只有兩個核心概念，函數和結構體，分別代表程序抽象和數據抽象，餘下的就看創作人的功力了，就如圍棋的黑與白一樣簡潔又蘊含無窮變化，沒有象棋的繁雜規則限制走向。在LISP中，同樣只有代表數據和程序的黑與白，一生二，二生無窮（資深的創作人會把程序歸一爲數據），簡潔優雅，威力無窮。但不同的是，LISP坐在人的這端，C語言坐在機器的那端；LISP追求簡潔舒適的表達，C語言追求卓越的機器性能。C語言有許多面向機器的指令，比如位運算，更不用說i++和++i啦，它適用於替代彙編語言（非單片機嵌入式系統）。同樣的高效，彙編只提供了call和ret兩條棧操作指令來模擬函數的調用，而C語言直接提供了函數級別的定義和調用。不過軟件系統和現實物理系統一樣都是有狀態的，我們稱其爲對象系統，比如銀行賬號account，一樣的10元存錢操作save(10)會返回不同的總數目，也就是存錢操作的結果不但取決於參數，還取決於賬號當前狀態。然而C語言的函數是無狀態的，全取決於參數，這就不得不將隱藏的狀態顯式地也作爲參數傳遞，調用層次多了容易造成混亂。哇又說了好多，簡單快進。於是面向對象的C語言：C++登場了，伴隨着內存管理的缺陷。於是Java登場了，不但自動回收廢棄內存，而且取消了函數指針帶來的隱患，而且通過JVM成爲半解釋性語言(先靜態編譯爲字節碼，然後JVM將字節碼動態解釋爲機器指令運行)，正如它的廣告語“一次編譯，處處運行”。伴隨着突破靜態類型限制的渴求，動態語言Python登場了... 這段粗糙的編程語言簡述無疑是以偏概全，有失分寸的，請自行甄別，再會~ P.S. 閉上書的第一天，書中的內容依舊在我腦中肆意反覆彈跳碰撞，火花四射。或許我該就此停止翻看，靜置它一個月，平復不寧的心神。我聽見DFA的腳步聲由近及遠在迴盪，我看見NFA的敲門手勢懸在半空溫度漸涼，停止思維，一切皆是虛妄。

Divide-and-Conquer、Probabilistic Analysis and Randomized Algorithms、Heapsort、Quicksort、Sorting in Linear Time、Medians and Order Statistics、Elementary Data Structures、Hash Tables、Binary Search Trees、Red-Black Trees、Augmenting Data Structures、Dynamic Programming、Greedy Algorithms、Amortized Analysis、B-Trees、Fibonacci Heaps、van Emde Boas Trees、Data Structures for Disjoint Sets、Elementary Graph Algorithms、Minimum Spanning Trees、Single-Source Shortest Paths、All-Pairs Shortest Paths、Maximum Flow、Multithreaded Algorithms、Matrix Operations、Linear Programming、Polynomials and the FFT、Number-Theoretic Algorithms、String Matching、Computational Geometry、NP-Completeness、Approximation Algorithms。

買過紙質版，全都仔細的讀過一遍，可謂是算法的經典之作。從複雜度分析，union-find 各種排序算法。 查找，二分搜索，二叉樹，23樹，紅黑樹，哈希表，都提到了。 再到圖，圖的表示，圖的算法，深搜廣搜，最小生成樹，最短路徑。 最後是字符串，匹配，正則，查找，壓縮都介紹到了。 但是在書裏沒有具體介紹動態規劃，也許是一個小小的缺憾。不過在算法導論裏面提到了，可以參考這裏的。 整體來講，這本書是特別值得細讀的一本經典之作。 不過這種代碼的，用手機看，排版有很大問題。

這本書還是很多年我讀研究生時讀的書，但感覺後來的純算法書也都源自這裏啦，當時都用JAVA去執行pseudocode，現在可以用Python 再執行，當作練習吧。

買過紙質版！API設計非常巧妙！因此各種數據結構操作邏輯都相對簡單，但是這種API必定是千錘百煉出來的，真正自己設計數據結構操作邏輯API時候很難抽象到恰到好處。當然書中也給出部分可以照抄的模板API。總的來說，相比於其他，這本算法書講的非常好！

整體內容很精妙，承前啓後一步步推進內容講解，給出了很多代碼可以研究，理論命題和證明內容也還在可理解的範疇內，值得一讀。 也買了紙質版挺厚一直沒怎麼看，這次快速過了一遍，部分深入講解的內容一知半解，綜合搞搞其他資料和刷題促進理解，有空再來讀第二遍 [捂臉]

幾個精簡的Data structure加上一些#%$^*@的步驟就把不可能完成的問題咔咔幾分鐘解決了。我想這就是爲什麼一個王者工程師能抵得過幾十個普通同行的理由。 所有複雜到不行的算法都是建立在這些基礎DS，sort, graph的基礎上。對於咱這世界有了更多的理解。模塊化，引用的漂亮之處是讓我們不用明白怎麼造它但是可以用它。世界上哪兒不是這樣呢？ 果然經典，一開始看目錄覺得內容好像不多。真讀完才覺得這幾個話題能延伸出這麼多高效的算法。900頁只是順着歷史打開了CS世界的一扇窗。值得一學再學