有哪些算法惊艳到了你？

Arzie100 · 发表于 2021-7-22 08:57

首先映入我脑海里的是 John Carmack 的Quake引擎里的一段代码, 求一个数的平方根的倒数(注意是倒数,不是导数). John Carmack 是id software的创始人, 也是经典第一视角游戏 Doom 和 Quake 的作者. 他对自己的Quake游戏引擎进行开源, 极大地促进了整个3D游戏行业前进的步伐. 连比尔盖茨都将 Carmack 列为自己的崇拜对象!

一般能想到的办法是:
1. 调用系统库函数: sqrt, 然后再除1;
2. 二分法逼近 (之前Facebook的有道面试题即是);
3. 牛顿迭代法

而在Quake渲染引擎中, 有这么一段代码 (将其标号: #4 Quake InvSqrt 算法):
float InvSqrt (float x){
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i>>1);
x = *(float*)&i;
x = x*(1.5f - xhalf*x*x);
return x;
}
如果有兴趣的朋友自己去写一个程序去测试, 发现上述4中方法的运算效率:
#4 > #1 > #3 > #2.

借用一位朋友的照片:

看见Carmack代码里面的方法比起系统方法还快一倍以上, 而且实现方式短小且神奇. 其本质上也是使用了牛顿迭代法, 但是通过预先猜测的一个神奇数字 0x5f3759df, 来将迭代次数降到极限的一次 (另外通过整形数的移位来进一步加速). 这让我不由得想到苏联飞机米格29引擎的暴力美学. 详细解说看这个: Beyond3D - Origin of Quake3&#39;s Fast InvSqrt()

P.S. 为什么InvSqrt在Quake引擎中被重新实现?  这是因为3D变换过程中要涉及到大量的平方根翻转操作 (比如3D向量的normalization), 所以对于这个函数的优化对于3D引擎的效率非常关键. 这也直接促使nVIDIA在最新的GPU的指令集中自带&#34;nrm&#34;; 此命令来借用硬件加速直接完成3D向量的normalization操作.

类似的, Quake3里的开方函数源代码:
double sqrt( double x ) {
float y;
float delta;
float maxError;

if ( x <= 0 ) {
      return 0;
}

// initial guess
y = x / 2;

// refine
maxError = x * 0.001;

do {
      delta = ( y * y ) - x;
      y -= delta / ( 2 * y );
} while ( delta > maxError || delta < -maxError );

return y;
}同样也是短小精妙. 另外附带
Quake引擎架构分析: Quake Source Code Review
Quake3代码分析: Quake 3 Source Code Review: Architecture
Quake代码的GitHub页: id-Software/Quake · GitHub
附带我偶像John Carmack的一张照片 (祝Oculus在Facebook帝国的支持下欣欣向荣):

另外, 收到  @陈然答案的启发 (那个等概率选数问题我在Facebook的最后一面上刚好碰到, 因为之前面试根本没有准备过, 导致自己最后面试上绞尽脑汁...), 所以我说一个自己对Facebook一道面试题经过多年没事想想后的顿悟!!!

计算Fibonacci(斐波那契)数列的第n项: 这个之前在我的Facebook面试总结里面有写过, 可以递归也可以递推, 这样的复杂度是O(N), 也可以用矩阵相乘的算法, 这样可以O(LogN)的复杂度解决. 本来也就这样作罢, 但是最近看了&#34;星际穿越&#34;之后, 突然顿悟到这个Fibonacci和星际穿越有异曲同工之妙:
在一维世界中只能通过公式 F(n) = F(n-1) + F(n-2) 来计算. 这时, 线性的算法(O(N))是一维世界下的极限. 要如何加速呢?  类推到星际穿越中的话, 可行的方法就是升维, 从一维升到二维空间 (一维的F(n)升级到二维矩阵), 也就是说我们用升维将一维空间进行扭曲从而将距离缩短. 于是 [F(n), F(n-1)] = M^(n-1) [1, 1] ( M 是一个二维的常数矩阵). 这样我们便可以更快地从 [1, 1] 到达 [F(n), F(n-1)].  看! 多么像一个数学世界里面的时空穿越呀!

先就到这里, 想到更多有趣的, 再进行补充.

闲鱼技术01 · 发表于 2021-7-22 09:04

也许程序员们觉得没什么（?），但我觉得超级惊艳的一个算法，“ MosAIc，https://microsoft.github.io/art/
麻省理工学院的一组研究人员探索了全世界记录的无穷艺术品，开发了一种艺术识别算法“ MosAIc”来查找隐藏的连接。麻省理工学院计算机科学与人工智能实验室（CSAIL）的小组与Microsoft合作，对大都会艺术博物馆（阿姆斯特丹）和阿姆斯特丹国立博物馆的绘画和雕塑艺术进行分类和探索。
这在我看来颇有一种算法承担策展人角色的意味啊。
Mosaic项目的发起人Mark Hamilton的灵感来自于荷兰国立博物馆的一次展览。展览将伦勃朗和维拉斯开支的作品进行了比较。
&amp;amp;#39;多莉姐妹&amp;amp;#39;，欧洲人提供，照片（左）| 无题的中文中国石（右）
所以Mark开始思考通过AI可以增强同一个想法的可能方式，并开发了一种算法，该算法根据起始图像和该图像的特征（例如介质，颜色或文化特征），使人们能够从经过训练的生成对抗网络中找到新作品。
（这段是我从谷歌翻译里硬翻的，原文：an interactive tool giving people the ability to generate new art from trained generative adversarial networks. 技术层面的问题不太懂，请可视化机器学习大佬 @谢天凯解释一下）
弗朗西斯科·德·祖巴兰（Francisco dezurbarán）的“圣六翼天使the难”（左）| 扬·阿瑟林（Jan Asselijn）的“受威胁的天鹅”（右）
对于跨文化跨时代的作品对比一直是我个人特别喜欢的题目，我之前也在文章中把莫兰迪\隈研吾，印象派\浮世绘、《色戒》\巴尔蒂斯作为对象放在一起讨论，所以这个算法简直太戳我了。
举个例子，很多时候我被一幅作品吸引会是一种自己也无法名状的情感，但借助Mosaic，我能看到同样构图\色彩\题材的，来自不同文化之下的艺术品。
尤其是那些并没有被记在史书上或者未曾在拍卖场上大放光彩的艺术品，这个算法可以帮助我们探索艺术，并且发现真正有趣的事物。
&amp;amp;#39;balearica regulorum&amp;amp;#39;，各种图纸（左）| “ twee javaanse danseressen”，东南亚，未分类
红宝石怀表（左）和女士上衣（右）
“带角的头盔（khula khud）”，南亚，武器（左）| “科林的皇家鹿”英国，照片

参考资料：
MIT students build Mosaic to explore art across cultures at Microsoft Garage - Microsoft Garage

欢迎关注我的gz号：王介南，和你聊聊少女心艺术史。

HuldaGnodim · 发表于 2021-7-22 09:08

密码分析里的差分攻击算法。
Diffie-Hellman的公钥体系理论。如此的简单，却是如此的具有革命性的密码算法。

待续...

DomDomm · 发表于 2021-7-22 09:11

写一个看似很简单的算法，但第一次理解清楚他的原理以后，真的惊艳到了我：）
这篇文章首发在我的公众号【是不是很酷】：神一样的随机算法。公众号ID：isnt_it_cool
欢迎大家关注，和我一起，用技术的眼光看世界：）
<hr/>这篇文章，我们从一道经典面试题开始来探讨这个问题。这个面试题有很多形式，但其实背后的算法是一致的。
这个问题是：设计一个公平的洗牌算法

1.
看问题，洗牌，显然是一个随机算法了。随机算法还不简单？随机呗。把所有牌放到一个数组中，每次取两张牌交换位置，随机 k 次即可。
如果你的答案是这样，通常面试官会进一步问一下，k 应该取多少？100？1000？10000？
很显然，取一个固定的值不合理。如果数组中有 1000000 个元素，随机 100 次太少；如果数组中只有 10 个元素，随机 10000 次又太多。一个合理的选择是，随机次数和数组中元素大小相关。比如数组有多少个元素，我们就随机多少次。
这个答案已经好很多了。但其实，连这个问题的本质都没有触及到。此时，面试官一定会狡黠地一笑：这个算法公平吗？
我们再看问题：设计一个公平的洗牌算法。

2.
问题来了，对于一个洗牌算法来说，什么叫“公平”？这其实是这个问题的实质，我们必须定义清楚：什么叫公平。
一旦你开始思考这个问题，才触及到了这个问题的核心。在我看来，不管你能不能最终给出正确的算法，如果你的思路是在思考对于洗牌算法来说，什么是“公平”，我都觉得很优秀。
因为背出一个算法是简单的，但是这种探求问题本源的思考角度，绝不是一日之功。别人告诉你再多次“要定义清楚问题的实质”都没用。这是一种不断面对问题，不断解决问题，逐渐磨炼出来的能力，短时间内无法培训。
这也是我经常说的，面试不是标准化考试，不一定要求你给出正确答案。面试的关键，是看每个人思考问题的能力。
说回我们的洗牌算法，什么叫公平呢？一旦你开始思考这个问题，其实答案不难想到。洗牌的结果是所有元素的一个排列。一副牌如果有 n 个元素，最终排列的可能性一共有 n! 个。公平的洗牌算法，应该能等概率地给出这 n! 个结果中的任意一个。
如思考虑到这一点，我们就能设计出一个简单的暴力算法了：对于 n 个元素，生成所有的 n! 个排列，然后，随机抽一个。
这个算法绝对是公平的。但问题是，复杂度太高。复杂度是多少呢？O(n!)。因为，n 个元素一共有 n! 种排列，我们求出所有 n! 种排列，至少需要 n! 的时间。
有一些同学可能对 O(n!) 没有概念。我本科时就闹过笑话，正儿八经地表示 O(n!) 并不是什么大不了不起的复杂度。实际上，这是一个比指数级 O(2^n) 更高的复杂度。因为 2^n 是 n 个 2 相乘；而 n! 也是 n 个数字相乘，但除了 1，其他所有数字都是大于等于 2 的。当 n>=4 开始，n! 以极快的的速度超越 2^n。
O(2^n) 已经被称为指数爆炸了。O(n!) 不可想象。
所以，这个算法确实是公平的，但是，时间不可容忍。

3.
我们再换一个角度思考“公平”这个话题。其实，我们也可以认为，公平是指，对于生成的排列，每一个元素都能独立等概率地出现在每一个位置。或者反过来，每一个位置都能独立等概率地放置每个元素。
基于这个定义，我们就可以给出一个简单的算法了。说这个算法简单，是因为他的逻辑太容易了，就一个循环：
for(int i = n - 1; i >= 0 ; i -- )
swap(arr, arr[rand(0, i)]) // rand(0, i) 生成 [0, i] 之间的随机整数
这么简单的一个算法，可以保证上面我所说的，对于生成的排列，每一个元素都能独立等概率的出现在每一个位置。或者反过来，每一个位置都能独立等概率的放置每个元素。
大家可以先简单的理解一下这个循环在做什么。其实非常简单，i 从后向前，每次随机一个 [0...i] 之间的下标，然后将 arr 和这个随机的下标元素，也就是 arr[rand(0， i)] 交换位置。
大家注意，由于每次是随机一个 [0...i] 之间的下标，所以，在每一轮，是可以自己和自己交换的。

这个算法就是大名鼎鼎的 Knuth-Shuffle，即 Knuth 洗牌算法。
这个算法的原理，我们稍后再讲。先来看看 Knuth 何许人也？
中文名：高纳德。算法理论的创始人。我们现在所使用的各种算法复杂度分析的符号，就是他发明的。上世纪 60-70 年代计算机算法的黄金时期，近乎就是他一手主导的。他的成就实在太多，有时间单独发文介绍，但是，我觉得一篇文章是不够的，一本书还差不多。
大家最津津乐道的，就是他所写的《The Art of Computer Programming》，简称 TAOCP。这套书准备写七卷本，然后，到今天还没有写完，但已经被《科学美国人》评为可以媲美相对论的巨著。
微软是 IT 界老大的年代，比尔盖茨直接说，如果你看完了这套书的第一卷本，请直接给我发简历。

至于这套书为什么写的这么慢？因为老爷子写到一半，觉得当下的文字排版工具都太烂，于是转而发明出了现在Tex文字排版系统，这就是现在大名鼎鼎的 LaTeX 的雏形...
另外，老爷子可能觉得当下的编程语言都不能完美地表现自己的逻辑思想，还发明了一套抽象的逻辑语言，用于这套书中的逻辑表示...
下面这张照片是他年轻的时候。这张照片是我在斯坦福大学计算机学院的橱窗拍的。

下面的话和大家共勉：

A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better.

Donald E. Knuth 1978

所以，我从来都不认为自己只是一名工程师而已。我是艺术家：）

4.
是时候仔细的看一下，这个简单的算法，为什么能做到保证：对于生成的排列，每一个元素都能等概率的出现在每一个位置了。
其实，简单的吓人：）

在这里，我们模拟一下算法的执行过程，同时，对于每一步，计算一下概率值。
我们简单的只是用 5 个数字进行模拟。假设初始的时候，是按照 1，2，3，4，5 进行排列的。

那么，根据这个算法，首先会在这五个元素中选一个元素，和最后一个元素 5 交换位置。假设随机出了 2。

下面，我们计算 2 出现在最后一个位置的概率是多少？非常简单，因为是从 5 个元素中选的嘛，就是 1/5。实际上，根据这一步，任意一个元素出现在最后一个位置的概率，都是 1/5。

下面，根据这个算法，我们就已经不用管 2 了，而是在前面 4 个元素中，随机一个元素，放在倒数第二的位置。假设我们随机的是 3。3 和现在倒数第二个位置的元素 4 交换位置。

下面的计算非常重要。3 出现在这个位置的概率是多少？计算方式是这样的：

其实很简单，因为 3 逃出了第一轮的筛选，概率是 4/5，但是 3 没有逃过这一轮的选择。在这一轮，一共有4个元素，所以 3 被选中的概率是 1/4。因此，最终，3 出现在这个倒数第二的位置，概率是 4/5 * 1/4 = 1/5。
还是 1/5 !
实际上，用这个方法计算，任意一个元素出现在这个倒数第二位置的概率，都是 1/5。

相信聪明的同学已经了解了。我们再进行下一步，在剩下的三个元素中随机一个元素，放在中间的位置。假设我们随机的是 1。

关键是：1 出现在这个位置的概率是多少？计算方式是这样的：

即 1 首先在第一轮没被选中，概率是 4/5，在第二轮又没被选中，概率是 3/4 ，但是在第三轮被选中了，概率是 1/3。乘在一起，4/5 * 3/4 * 1/3 = 1/5。
用这个方法计算，任意一个元素出现在中间位置的概率，都是 1/5。

这个过程继续，现在，我们只剩下两个元素了，在剩下的两个元素中，随机选一个，比如是4。将4放到第二个位置。

然后，4 出现在这个位置的概率是多少？4 首先在第一轮没被选中，概率是 4/5；在第二轮又没被选中，概率是 3/4；第三轮还没选中，概率是 2/3，但是在第四轮被选中了，概率是 1/2。乘在一起，4/5 * 3/4 * 2/3 * 1/2 = 1/5。
用这个方法计算，任意一个元素出现在第二个位置的概率，都是 1/5。

最后，就剩下元素5了。它只能在第一个位置呆着了。
那么 5 留在第一个位置的概率是多少？即在前 4 轮，5 都没有选中的概率是多少？
在第一轮没被选中，概率是 4/5；在第二轮又没被选中，概率是 3/4；第三轮还没选中，概率是 2/3，在第四轮依然没有被选中，概率是 1/2。乘在一起，4/5 * 3/4 * 2/3 * 1/2 = 1/5。
算法结束。

你看，在整个过程中，每一个元素出现在每一个位置的概率，都是 1/5 ！
所以，这个算法是公平的。
当然了，上面只是举例子。这个证明可以很容易地拓展到数组元素个数为 n 的任意数组。整个算法的复杂度是 O(n) 的。
通过这个过程，大家也可以看到，同样的思路，我们也完全可以从前向后依次决定每个位置的数字是谁。不过从前向后，代码会复杂一些，感兴趣的同学可以想一想为什么？自己实现一下试试看？
（因为生成 [0, i] 范围的随机数比生成 [i, n) 范围的随机数简单，直接对 i+1 求余就好了。）

怎么样，是不是很酷？

5.
这个算法除了洗牌，还能怎么用？
其实，在很多随机的地方，都能使用。比如，扫雷生成随机的盘面。我们可以把扫雷的二维盘面先逐行连接，看作是一维的。之后，把 k 颗雷依次放在开始的位置。

然后，我们运行一遍 Knuth 洗牌算法，就搞定啦：
是不是很酷？

这就是我喜欢算法的原因。在我眼里，算法从来不是枯燥的逻辑堆砌，而是神一样的逻辑创造。
尽管这个世界很复杂，但竟也如此的简洁，优雅。

大家加油！：）
<hr/>P.S.
没想到获得这么多赞。先谢谢大家啦。

补充几点：
1.
首先，知乎大佬太多了。非常抱歉，我写的这么啰嗦，耽误一些大佬时间了。

2.
很多人说，rand()函数就不均匀，所以这个算法不均匀。没错。但这里，我谈的是Knuth-Shuffle的逻辑，而不是具体的实现。如果你的rand()不均匀，当然这个shuffle也不均匀。谈论这个问题的时候，我们假想rand()是无偏的。
有些人很好心地在评论区提出了无偏的rand()实现思路，谢谢大家。把你认为无偏的rand()实现封装成代码里的rand()就好了。这个代码没有规定rand()的具体实现。rand()怎么实现也根本不是这篇文章的重点。

3.
很多人说，把这些元素扔进一个口袋，然后每次不放回随机取出一个元素，生成排列，就好了。完全没问题！其实这个算法的本质也正是这么做的。只不过原地完成，空间复杂度O(1)。可以用这个思路再理解一遍这个算法。我的这个文章确实过于强调计算概率了，忽略了这个直观理解。感谢提醒。
但是，上面的这个“把这些元素扔进一个口袋，然后每次不放回随机取出一个元素，生成排列”过程，如果用代码实现，其实是复杂的，试试看？
而 Knuth Shuffle 这样一个思路，可以如此巧妙地原地完成上面的过程，恰恰是这个算法惊艳我的地方。它竟然如此简单。
有意思的是，很多人说“这个问题哪里有这么复杂？”而整篇文章的关键就是：这个算法不复杂啊！只有两行。相反，大概率的，这些人想的思路，实现出来，其实是复杂的。最后优化来优化去，就会绕回到这个“简单“的算法上。（当然，如果是因为你水平太高，看我的文章写的啰嗦，请参考上面第1条。）
我怀疑很多人根本不是计算机专业的，竟然思考不到单纯的“扔进一个口袋，然后每次不放回随机取出一个元素”这样的思路实现出来有什么坑。当然，不排除我才疏学浅，恳请各位大佬把那个“哪有这么复杂，比这个算法还简单”的代码摆出来。
Talk is cheap, show me the code.

跳跃一下：
我突然觉得这是一个很好的面试题，下次面试用。
实现以下算法：一组数，每次不放回抽样，得到一个随机序列。白板编程。分析时间空间复杂度。
follow up：能否时间O(n)完成，能否空间O(1)完成。
不考概率，不考随机算法，完全考工程实现。

4.
原文说“每个元素能够等概率出现在每个位置”，确实不严谨，需要加入“独立”的条件，即“每个元素能够独立且等概率地出现在每个位置”。现已修改。感谢指正。

5.
文章中我说Knuth的英文名是高纳德，有误。应该是高德纳。为此我在公众号上发表了一篇新文章：不小心，较真儿了：高德纳和特朗普谢谢大家指正。

6.
对了，补充一下，我有两个学生，一个现在在网易游戏，一个现在在腾讯游戏，都表示在面试的时候遇到过这个问题（或者需要使用这个算法解决的问题）。
腾讯游戏的大佬当时没有答上来；
网易游戏的大佬见过这个算法，虽然没有理解为什么，但说出来了。
因为游戏领域对随机算法的应用较多。
当然了，网易游戏或者腾讯游戏这种小地方，是不会入知乎上很多大佬的法眼的，面试竟然问这种问题？简直了。
补充：一名硅谷 Google 大佬表示 Google 面试叶问这个问题。
<hr/>算法学习入门推荐《算法图解》：

科班同学或者深入学习，吐血推荐一定要通读《算法4》

这本书英文版都值得收藏！

玩儿竞赛的同学，把刘汝佳的书啃了，就稳了。
<a data-draft-node="block" data-draft-type="mcn-link-card" data-mcn-id="1258801174666121216">

最后，欢迎大家关注我的公众号【是不是很酷】（公众号id: isnt_it_cool）

mypro334 · 发表于 2021-7-22 09:17

新冠病毒的检测需要采样咽拭子，然后将其中含有的碱基对解螺旋、经过聚合酶链式反应（PCR）扩增后与相应的荧光探针结合，然后进行检测。
而制造能与病毒碱基序列结合的荧光探针，需要知道病毒的碱基序列。

在这个过程中，有一个算法发挥了巨大的作用。
如今的这个算法已经变得十分基础，也有更多的算法超越了它。
但是，它诞生的那一刻，必定闪耀着人类智慧的光芒。

我第一次见到这个算法时，经历了拒绝、疑惑、不解。
直到后来，一切全都化为了惊叹。

这个算法叫KMP算法。由于三个字母的原因，有人戏称为“看毛片”算法。但它和“毛片”真的没有一点关系。KMP实际是合力研究出该算法的三位大神的姓名首字母。是的，这个算法是当时三个大神共同努力的结果。
它实际是一个字符串匹配算法。

那它如何为基因测序做出贡献，又为什么让我拒绝、疑惑、不解，最后惊叹。我们一起来重新感受下。
<hr/>首先，我们先给出算法解决的问题，这是一个极为常见的字符串匹配问题。
存在一个字符串T，请找出其是否含有子串P，如果有，请给出P所在的位置。
假设字符串T的长度为m，字符串P的长度为n。
则见到这个问题后，有经验的程序员不出5秒就能知道其时间复杂度为O(m×n)。是的，这是很多人的第一反应。其推导如下。
字符串T我们常称为主串，而P则被称为模式串。在主串的任意一个位置，我们都要以此为起点和模式串依次对比。模式串长度为n，而主串中有m个位置，则复杂度为O（m×n）。
T: ABCFEDABCFTYGFHTABCDEFHMI
P: ABCDEFG<hr/>我听说有个算法能做到复杂度O(m+n)的时候，还没学这门课。听说那个算法叫KMP。
不可能，我内心是拒绝的。
怎么可能呢，O(m+n)意味着比较指针不能回撤，直觉告诉我这是不可能的。
我以O(m+n)为目标尝试了几下，没找到什么思路。
<hr/>然后我搜了一下各种资料。
竟然真的是……
KMP算法怎么做的？我全是疑惑！
<hr/>那时的我把算法找来，读了一遍。
给你，你先读一遍吧。
/**
* 求出一个字符数组的next数组
* @param t 字符数组
* @return next数组
*/
public static int[] getNextArray(char[] t) {
int[] next = new int[t.length];
next[0] = -1;
next[1] = 0;
int k;
for (int j = 2; j < t.length; j++) {
      k=next[j-1];
      while (k!=-1) {
         if (t[j - 1] == t[k]) {
            next[j] = k + 1;
            break;
         }
         else {
            k = next[k];
         }
         next[j] = 0;  //当k==-1而跳出循环时，next[j] = 0，否则next[j]会在break之前被赋值
      }
}
return next;
}

/**
* 对主串s和模式串t进行KMP模式匹配
* @param s 主串
* @param t 模式串
* @return 若匹配成功，返回t在s中的位置（第一个相同字符对应的位置），若匹配失败，返回-1
*/
public static int kmpMatch(String s, String t){
char[] s_arr = s.toCharArray();
char[] t_arr = t.toCharArray();
int[] next = getNextArray(t_arr);
int i = 0, j = 0;
while (i<s_arr.length && j<t_arr.length){
      if(j == -1 || s_arr==t_arr[j]){
         i++;
         j++;
      }
      else
         j = next[j];
}
if(j == t_arr.length)
      return i-j;
else
      return -1;
}卧槽，没读懂。
这算法牛逼啊！我不解。
这个不解就一直闷在我的心头。
<hr/>直到后来，我坐在图书馆，啃透了KMP算法。
（现在网上很多视频教程，讲得很好，十分钟看完就能懂，比自己啃快多了）
牛！真牛！
主要是思路牛。
下面我给出一个KMP算法的实现动画，大家关注一下最上面的比较指针，真的没有任何回撤操作。

KMP算法动画演示
https://www.zhihu.com/video/1237840447395414016

<hr/>等你真正理解了它，发现它并没有太复杂，主要是利用了模式串中的相关性。甚至，会有更优的算法被提出。但是KMP算法由D.E.Knuth、J.H.Morris、V.R.Pratt发表于1977。在那个年代，相信KMP算法诞生时，一定闪耀着光芒。

那KMP算法为什么会和基因扯上关系呢？
平时，我们的文本，也就几百上万的字符。即使是做大数据分析（我以前在某度厂做过大数据分析），接触到的字符串也不过几十万、上百万个。当然，在这个尺度下，O（m×n）算法和O（m+n）的性能差别已经是极为巨大的。
然而，人类的基因序列，就是腺嘌呤（A）、鸟嘌呤（G）、胞嘧啶（C）、胸腺嘧啶（T）组成的那些ATCGCTACG……等朴实无华的序列串，有30亿个（即30亿对碱基对）。
基因片段的拼接需要不断在上亿的序列（碱基对）中找一个目标序列，O（m×n）算法和O（m+n）的性能差别有万倍、百万倍，甚至更多。
只用暴力匹配的方式，难以完成。
而KMP算法将O（m×n）降到了O（m+n）。只需要读取一遍目标串和模式串，就能给出结果！

在KMP算法诞生的1977年，那时人类才发现DNA的双螺旋结构不过20年，再过大约15年后人类基因组计划才会开始。
当然，在KMP算法诞生后人类基因组计划开始前的15年中，字符串匹配算法可能又会有进步，并且字符串匹配算法也并不最适合基因测序（具体原因参见下方 @奶油煎蛋红烧肉的评论）。是新的算法（例如OLC、de Bruijn Graph等算法）用在了基因组计划中。但KMP算法在匹配方面的研究已经打好了基础，它已经提前为人类基因组计划扫除了部分算法上的障碍。
之后，也正因为基因测序技术的发展，人类能迅速锁定出新冠病毒的序列，然后研发测试试剂。帮我们开展测试，推动人类抵御这场突如其来的病毒。
所以，在这场全世界抗击疫情的斗争中，有算法的身影。低调、朴实，但也无可替代。

如今的它，低调，朴实，甚至让人觉着习以为常。
但我知道，它曾经闪耀着人类智慧的光芒；而今，也依旧令人惊艳和伟大。
<hr/>欢迎关注我，我会偶尔解答软件架构和编程方面的问题。

BlaXuan · 发表于 2021-7-22 09:22

既然是哪些，那我就多说几个。

首先是KMP和与之相关的AC自动机（Aho-Corasick automaton，刚接触以为是自动AC机），其思想和效率真的很惊艳。

然后是快速傅里叶变换（FFT），可以以 $nlog_{2}n$ 的复杂度计算n次多项式乘法。

其次是扩展欧几里得算法，数论题最常用算法了，求乘法逆元、解一次不定方程超级好用，而且代码很短很好记。

再次是快速幂取模算法，理解之后代码很好写，而且效率很高。k阶矩阵的n次方复杂度仅为 $k^{3}log_{2}n$ （不用strassen法加速的情况）。

最后再推荐一个好用但不完全严谨的算法：Miller-Rabin素数测试算法。非常快而且错误率很低啊！

自适应辛普森公式，对三点辛普森公式递归调用的积分算法，代码不到20行，解决所有一维定积分问题。

旋转卡壳算法可以在O（N）时间内求多边形直径。
-----------------------------------------------------------------------------上边是正经回答，下边是抖机灵

快速排序算法也是非常好用的，#include<stdlib.h>然后调库是比赛中所有要排序的地方的处理方法，快速排序算法让我惊艳的地方是我去省图书馆看见两个志愿者需要把还回来的一堆书按顺序入架，管理员大妈给他们教的时候说：“你先在这堆书里拉出一本来，把比它号小的扔到一边，比它大的扔到另一边，然后剩下两堆继续这样整，这样排的快！”这是我见识过最惊艳的算法使用，没有之一！

RhinoFreak · 发表于 2021-7-22 09:31

补充：
感谢 @马宇峰的提醒，为了表达更准确，我把之前的“推荐算法”改为“基于用户的协同过滤算法”

1.基于用户的协同过滤算法：使用余弦函数来找到，比如某一商品的选择方面，和你匹配的用户，从而根据这个用户的选择来给你进行推荐商品

2. 蒙特卡洛算法，神一般的统计模拟方法。第一次接触的时候，就看到了那个估计圆周率的经典例子，圆周率竟然可以通过落入嵌入某个正方形中的1／4圆范围内的点的概率估算出来，顿时觉得脑洞大开

引用维基百科里面的一段话来描述就是：

蒙特卡洛方法可用于近似计算圆周率：让计算机每次随机生成两个0到1之间的数，看以这两个实数为横纵坐标的点是否在单位圆内。生成一系列随机点，统计单位圆内的点数与总点数，（圆面积和正方形面积之比为PI:4，PI为圆周率），当随机点取得越多时，其结果越接近于圆周率（然而准确度仍有争议：即使取10的9次方个随机点时，其结果也仅在前4位与圆周率吻合）。

下图来自维基百科：

APSchmidt · 发表于 2021-7-22 09:32

中文无词典分词。不需要词典，给我语料就能给你分词。是不是听起来就碉堡了！！！
http://www.matrix67.com/blog/archives/5044

zifa2003293 · 发表于 2021-7-22 09:35

挺多人看到地精排序，各种怼说复杂度怎么怎么样，不过如此等等，可问题不是 有哪些算法当你刚接触的时候，心里有“居然还可以这样算..”的想法？这个么
这跟时间复杂度、空间复杂度有什么关系。
再补充一个：
问题：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

答案：使用异或

具体可看笔者的文章：
一道让你拍案叫绝的算法题原答案：
我来个简单的：地精排序。
我前几天收集奇葩排序系列时，就感觉地精排序真是太有趣了！！！

Gnome 排序（地精排序），起初由 Hamid Sarbazi-Azad 于 2000 年提出，并被称为 stupid 排序，后来被 Dick Grune 描述并命名为 “地精排序” 。

地精排序和插入排序类似，除了移动一个元素到最终的位置，是通过交换一系列的元素实现，就像冒泡排序一样。概念上十分简单，不需要嵌套循环。时间复杂度为O(n2)，但是如果初始数列基本有序，时间复杂度将降为O(n)。实际上 Gnome 算法可以和插入排序算法一样快。平均运行时间为O(n^2)。
将无序数列：6，2，4，1，5，使用地精排序使其从小到大排序。
通过设计标识 i = 0 ，然后从头开始判断，什么时候 ( i < 4 ) 不成立,什么时候排序结束。
这里的核心点就是 如何控制 i 的值。
第一轮操作「i = 0」

先让 i 自增 1 ，达到值为 1 才开始比较：
交换前 [ 6 2 4 1 ] 『 i = 0 』
交换后 [ 6 2 4 1 ] 『 i = 1 』
第二轮操作「i = 1」

比较 6 和 2 ，发生交换，只要发生交换 i 就减 1 。
交换前 [ 6 2 4 1 ]『 i = 1 』
交换后 [ 2 6 4 1 ]『 i = 0 』
第三轮操作「i = 0」

i 变成 0 了，啥也不干，自增变成 1 再说。
交换前 [ 2 6 4 1 ]『 i = 0 』
交换后 [ 2 6 4 1 ]『 i = 1 』
第四轮操作「i = 1」

比较 2 和 6 ，不交换，只要不要换就自增 1。
交换前 [ 2 6 4 1 ]『 i = 1 』
交换后 [ 2 6 4 1 ]『 i = 2 』
第五轮操作「i = 2」

比较 6 和 4 ，发生交换，只要发生交换 i 就减 1 。
交换前 [ 2 6 4 1 ]『 i = 2 』
交换后 [ 2 4 6 1 ]『 i = 1 』
第六轮操作「i = 1」

比较 2 和 4 ，不交换，只要不要换就自增 1 。
交换前 [ 2 4 6 1 ]『 i = 1 』
交换后 [ 2 4 6 1 ]『 i = 2 』
第七轮操作「i = 2」

比较 4 和 6 ，不交换，只要不要换就自增 1 。
交换前 [ 2 4 6 1 ]『 i = 2 』
交换后 [ 2 4 6 1 ]『 i = 3 』
第八轮操作「i = 3」

比较 6 和 1 ，发生交换，只要发生交换 i 就减 1 。
交换前 [ 2 4 6 1 ]『 i = 3 』
交换后 [ 2 4 1 6 ]『 i = 2 』
第九轮操作「i = 2」

比较 4 和 1 ，发生交换，只要发生交换 i 就减 1 。
交换前 [ 2 4 1 6 ]『 i = 2 』
交换后 [ 2 1 4 6 ]『 i = 1 』
第十轮操作「i = 1」

比较 2 和 1 ，发生交换，只要发生交换 i 就减 1 。
交换前 [ 2 1 4 6 ]『 i = 1 』
交换后 [ 1 2 4 6 ]『 i = 0 』
第十一轮操作「i = 0」

啥也不干，先让 i 自增1，达到值为 1 才开始真正的比较。
『 i = 1 』时，比较 1 和 2 ，不交换，只要不交换就自增 1 。
『 i = 2 』时，比较 2 和 4 ，不交换，只要不交换就自增 1 。
『 i = 3 』时，比较 4 和 6 ，不交换，只要不交换就自增 1 。
『 i = 4 』时，表达式（ i < n ) 不成立，排序结束。
顺序输出为 [ 1 2 4 6 ]。

我还做了猴子排序和睡眠排序的动画呢：）这些奇葩的排序算法，你没见过动画吧？
2019年04月27日补充
----------------------------------------------------------------------------------------------
我将那几个有意思的经典互联网公司的面试题目都详细的分析了一遍，每个题目都写了比较详细的分析过程，大部分文章都配了动画，目前还在持续更新中。。。
配了动画是为了加强理解，并且希望等你面试的时候没有思路，通过动画能联想起来！（觉得有帮助的，记得点个赞关注走一波，谢谢大家）
-------------------------------------------------------------------------------

1. 给你一个长度为 n 的数组，其中只有一个数字出现了奇数次，其他均出现偶数次，问如何使用优秀的时空复杂度快速找到这个数字。
一道让你拍案叫绝的算法题2. 假设有 100 层的高楼，给你两个完全一样的鸡蛋。请你设计一种方法，能够试出来从第几层楼开始往下扔鸡蛋，鸡蛋会碎。  请问最坏情况下，至少需要试验多少次才能知道从第几层楼开始往下扔鸡蛋，鸡蛋会碎。

一道腾讯面试题：厉害了我的杯3. 请设计一个 LRU 算法。
看动画轻松理解「链表」实现「LRU缓存淘汰算法」4.什么是动态规划？ 30 张图片动画详细分析！
看动画轻松理解「递归」与「动态规划」

当然，大佬们都说过，学算法之前起码得了解数据结构呀！
你是否当程序员这么多年，还只是能手写出个冒泡排序的代码？
别怕！
我也将程序员常见常用的那些数据结构都配了大量的图片和动画进行讲解，相信你看了一定能有所收获！
比如我做了十大经典排序动画，你看着动画应该能理解吧。
1. 冒泡排序
1.1 算法步骤

1.2 动画演示

2. 选择排序

2.1 算法步骤

2.2 动画演示

3. 插入排序

3.1 算法步骤

3.2 动画演示

4. 希尔排序

4.1 算法步骤

4.2 动画演示

5. 归并排序

5.1 算法步骤

5.2 动画演示

6. 快速排序

6.1 算法步骤

6.2 动画演示

7. 堆排序

7.1 算法步骤

7.2 动画演示

8. 计数排序

8.1 算法步骤

8.2 动画演示

9. 桶排序

9.1 算法步骤

9.2 动画演示

10. 基数排序

10.1 算法步骤

10.2 动画演示

不仅是这些，像上面栈、队列、堆、二叉树、图等各种结构，我都配了大量的图片和动画进行讲解。你看完肯定有收获！
看动画轻松理解「堆」冰与火之歌：「时间」与「空间」复杂度

Baste · 发表于 2021-7-22 09:44

AdaBoost haar Cascade 人脸检测算法，cvpr十年最佳论文

		自动登录	找回密码
密码			立即注册

有哪些算法惊艳到了你？

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源