算法（第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世界的一扇窗。值得一学再学