你知道哪些《算法导论》未记载的算法？

《算法导论》虽然是一本划时代的经典算法书籍，但难免有一些现代算法未在其中记载。你知道哪些这样的算法？你是怎么实现的？

zhihu用户 · 2019-5-18 03:48:28

就算是经典算法，大家也研究了60年了，算法导论里面一共就只有那么一些算法，冰山一角都算不算呀。
算法导论实质上是MIT本科生算法课的讲义，那门课的名字就叫Introduction to Algorithms，只是后来整理出书了。不是本科生第一门算法课的内容，大多数都是没有在这本书里介绍的。
要举例子的话，随便找国外一门研究生算法课，里面大多数算法应该都和本科的算法课不一样吧，否则就讲了两遍了。另外非经典组合算法也很少出现在这门课中，经典算法的并行和一些I/O优化也没有出现。

zhihu用户 · 2019-5-18 03:48:29

多了去了。。。
1 带并行/分布式的算法，Lynch阿姨的书，Herlihy和Shavit的《多处理器编程艺术》logical clock，vector clock，atomic snapshot，分布式锁，共识：paxos，raft（包括相应的multi版本），一致性hashlinearizable，seq-cst，memory order，consensus number，atomic register hierarchy，universal construction，锁：Dekker/Petterson/Lamport，链式锁，自选锁（和不同的step-back策略），睡眠锁/mutex（当然这个和调度器有关了，说到调度器又一堆方法/策略），fast-path，混合策略。并发：单链表，双链表，deque，stack，skip list，hashmap（若干算法），并发b-tree或其他平衡树。rcu/hazard pointer或gc算法（一堆）。
数据库应该还有一些mvcc，2PC/3pc，plan，算子下推，查询器优化之类的，我不了解就不多说了。
2 parsing有关的算法，《parsing techniques》挺厚的。
3 编译器里的算法，dominator tree相关的，ssa相关的，gvn/pre/scev等scalar优化，指针分析，数据流/控制流分析，图的2，3连通性，如何分解为不同的component，寄存器分配算法，instruction selection算法，loop transformation，poly-hydra compilation，presburg formulas。函数式的，cps变换，closure conversion，hygienic macro expansion用到的算法，类型推断算法Hindley-Milner，还有prolog，minikanren之类的系统里用到的算法。形式化方法（Coq/Isabella/tla+)之类的，abstract interpretation之类的我不了解不说了。
4 数值相关的算法，插值，迭代解矩阵，数值解线性/非线性偏微分，常微分方程，数值积分/微分，krylov子空间方法。
5 加密/解密/哈希算法一堆。
6 Nagel算法，delayed acknowledgement，
慢启动，拥塞控制，快重传，快恢复，tcp cubic，bbr之类的。
6 信号处理算算法吗？算的话那搞明白一堆离散/连续傅立叶/z/拉普拉斯/小波之类的变换才算初窥门庭吧。
7 ML/DL我就不说了。
8 什么马拉车，balanced size tree，树状数组，线段数，ac自动机，Morris transversal之类常见但算导里没有的oi/ACM算法就不说了。
9 introsort，rsync用的rolling hash。

zhihu用户 · 2019-5-18 03:48:30

CLRS并不是“算法百科”，其目的是教授本科生和研究生的算法课。另外的一些课，诸如OS, Compiler, Database, machine learning的算法都鲜有涉及。
PS. 介绍一本真-算法百科，1600刀，上面的算法都是按照alphabet order排序的，有很多CLRS没有的很高深的算法……

zhihu用户 · 2019-5-18 03:48:31

算法导论的英文是“introduction to algorithm”，也就是说算法的介绍，不是算法百科，要记录所有算法当然是不行的了
不过也正因为是基础介绍，很多章节讲的是原理和思路，比如贪心、dp之类的就不是算法，而是思想，在章节和习题中用算法当例子来讲这类，所以就算碰到一个其没有涉及到的某个算法，也能感觉是在算导的覆盖范围内了
具体到其中没有讲到的算法，随便找个方向就能拎出一堆，比如排序算法不止十几种，算导貌似只讲了其中几个代表性的

zhihu用户 · 2019-5-18 03:48:32

算导中的算法只是数学算法中的冰山一角，多数是运筹学最实用部分的算法，以及哈希和排序算法，这只是多个数学学科中把最实用的拿出来。实际上直接刷算导是相当有相当大的难度的。而算导我第一章就刷不下去。到了后来才找到问题所在：我没有足够的数学基础。
算导当中牵扯到的数学学科有数据结构基础、数论、图论、组合数学、计算几何、运筹学、一点点线代一点点概率一点点数值计算，还有一点复变、级数的数值计算，可以说一个算导是大筐什么都往里装。
因此可以说这本书不过是一本有关数学在计算机中可应用算法的冰山一角。一般本科生刷完第五部分已经算足够了，再往后，怕是本科的时间不太够用。不是做不到，而是不够用。从第六部分开始往后就开始直接牵扯大量的数学学科一般人怎么可能刷的动。
如果想要在某个方向刷算法，至少还有三四个方向可以让你尽情刷：
数论、计算几何、运筹学、数值分析。
其中运筹学最贴近计算机科学,当中的排队论、线性规划、动态规划等都符合现在很多工业软件和互联网软件的实用要求，计算几何最贴近几何化数据查询，比如地图、公交地铁线路、数据库组合查询等等，数值分析最贴近科学计算、机器学习、音视频和图像算法的要求。
这当中还没有列举任意一个机器学习算法。
要想顺利刷算导，在学一部分以上我所说的学科之前，可以说是相当困难的事情。
反正我第一部分就弃了，直接转《数据结构和算法分析》。
以上回答你也应该能意识到，算导只是冰山一角，在各种数学学科、管理规划型学科中还有大量的算法没有纳入其中，这只是一本多学科集中的一本介绍书而已。
这本书实际上你是不会学透的，牵扯大量学科，而每个学科的算法只是给你介绍一点点，而每个被牵扯到的学科背后都是无穷尽的参天大树，所以综上所述，算导是帮你打好基础以外，后面是长见识用的。所以劝入刷算导的，不如劝刷《数据结构》+ 任意一个感兴趣的方向：
比如
《数据结构》+ 《计算几何》，将来可以从底层开发数据库系统以及地图类系统的开发和研究；
《数据结构》+ 《编译原理》，将来从事编程语言设计和研究；
《数据结构》 + 《数值分析》，将来可以从事科学计算软件、工业计算软件、无线通讯系统的设计、音视频编码和图形图像算法方面的开发和研究；
《数据结构》+ 《运筹学》，操作系统底层开发或大型管理系统的设计；
《数据结构》+ 《机器学习》，将来从事机器学习方面的开发和研究；
《数据结构》+ 《数论》，将来从事密码学方向的研究
……
看到最后不就是大学里计算机专业分方向学习的一个做法吗？人的精力有限，也不要想一口吃个大的，细分做精找到适合自己的研究或者工程方向才最OK。

另外说一个我们小学时期就学过的一个初等数论算法，当然也包含在算导中：
欧几里得算法。

算法无处不在。

还有一门课是最推荐成为算导的先导课程：《离散数学》

设计算法？别想了。学算法是让你选择现有的算法在合适的场景中应用，以解决现有遇到的问题。设计算法那是聪明绝顶的人干的事。是的，要聪明绝顶。你想绝顶？

你知道哪些《算法导论》未记载的算法？

5 个回复

浏览过的版块