有哪些算法惊艳到了你？

那些 algorithms 就像隐藏在数字世界里的精妙机关，每一次的理解和运用，都让我觉得像是揭开了某种深层规律的面纱。要说最让我惊艳的，那绝对是 Transformer 模型，尤其是它背后那个叫做 Attention Mechanism 的东西。

我们先不谈它在自然语言处理（NLP）领域搅起的滔天巨浪，就单说它解决问题的思路，就足够让人拍案叫绝。

回溯一下，过去我们怎么解决序列问题？

想象一下，我们要让电脑理解一段话，比如“我爱吃苹果”。传统方法，比如循环神经网络（RNN）及其变种（LSTM、GRU），它们像一条流水线一样，一个词接一个词地处理。当处理到“苹果”时，它得依赖前面“我爱吃”的信息。这就像你在听一个很长的故事，听到最后，你可能已经记不清开头讲了什么了。RNN 这种“遗忘”问题（尽管 LSTM 和 GRU 做了很多改进）始终存在，尤其是在处理长句子或者长篇文本时，信息在传递过程中会逐渐衰减。

更糟糕的是，RNN 的计算是顺序的。你想计算第七个词的表示，就必须先算完前六个。这就意味着，你没法并行计算，处理速度上不去，大规模训练就变得非常缓慢。

Transformer 来了，它怎么做的？

Transformer 的出现，就像是彻底推翻了之前的建构方式。它摒弃了 RNN 的循环结构，而是完全基于一个叫 Attention Mechanism 的核心组件。

咱们就拿那个“Attention”来说事儿。它是什么？简单来说，就是让模型在处理序列中的一个元素时，能够“关注”到序列中其他所有相关元素，并且分配不同的“权重”或“注意力”。

举个例子，还是那句话：“我爱吃苹果”。当模型处理到“苹果”这个词时，它并不仅仅是依赖于它前一个词“吃”的信息，而是可以“回看”整个句子，并且给“我”和“吃”更高的关注度。因为“我”是动作的发出者，“吃”是动作本身，它们都直接关联到“苹果”这个宾语。

那么，Attention 到底是怎么实现的呢？

这里面有个更精妙的计算过程，用到了三个关键的向量：Query (Q), Key (K), Value (V)。你可以把它们想象成这样：

Query (Q): 代表当前你“想找什么”。比如，当模型处理到“苹果”时，它的 Q 向量就像在问：“跟‘苹果’这个词最相关的信息是什么？”
Key (K): 代表序列中每个元素“有什么”。每个词都会有一个 K 向量，相当于它的一个“索引”或者“标签”。
Value (V): 代表序列中每个元素“具体的信息内容”。每个词也有一个 V 向量，存储着它本身的语义信息。

计算过程是这样的：

1. 相似度计算: 对于当前需要处理的词（比如“苹果”），它的 Q 向量会和序列中所有词的 K 向量进行点积计算。这个点积的结果就代表了 Q 和 K 的“相似度”或者说“相关性”。相似度越高，说明这个 K 向量对应的词与 Q 向量的“需求”越匹配。
2. 归一化 (Softmax): 把计算出来的所有相似度得分通过 Softmax 函数进行归一化，得到一系列的注意力权重。这些权重加起来等于 1，而且它们表示了当前词应该“给予”其他词多少“关注”。
3. 加权求和: 用这些注意力权重去乘以对应词的 V 向量，然后把所有加权后的 V 向量加起来，就得到了当前词的新的、更丰富的表示。这个新的表示融合了序列中所有词的信息，并且是根据它们的相关性进行加权的。

这有什么惊艳的？

克服了长距离依赖问题: 因为 Attention 可以直接计算任意两个词之间的相关性，无论它们在序列中相隔多远，信息传递几乎没有衰减。这就像你看一段长文，需要找某个概念的定义，你不再需要从头读到尾，而是可以直接跳到相关部分。
并行计算成为可能: 注意力计算是基于矩阵运算的，可以高度并行化。这彻底改变了序列模型的训练方式，使得在 GPU 上训练大规模模型成为可能。这是 Transformer 能取得巨大成功的重要原因之一。
可解释性提升（某种程度上）: 我们可以可视化注意力权重，看看模型在做什么决策。例如，在翻译句子时，“He is eating an apple.” 翻译成中文“他在吃一个苹果。”，当模型翻译“吃”的时候，它会高度关注英文的“eating”和“apple”。这给了我们一些直观的理解。

更进一步的 SelfAttention 和 MultiHead Attention

Transformer 的伟大之处还在于它用了 SelfAttention，即在处理同一个序列内部的词时互相产生注意力。这使得模型能够理解句子内部词与词之间的关系。

而 MultiHead Attention 则更进一步，它把 Q, K, V 向量“拆分”成多个“头”，每个头都独立地进行 Attention 计算，学到不同的关系模式。最后再把这些“头”的结果拼接起来，输入到下一个层。这就像你从不同的角度审视同一件事物，信息更全面、更立体。

总结一下Transformer和Attention的惊艳之处：

它不是简单地把前面的信息传递到后面，而是动态地、根据内容相关性地去“选取”和“整合”信息。这是一种从根本上改变了我们处理序列数据的方式，让模型拥有了类似人类的“阅读”和“理解”能力。

当第一次看到 Attention 机制的计算过程，我真的被这种优雅又高效的设计深深震撼了。它没有复杂的门控机制，没有冗长的循环，仅仅通过向量的乘法和加法，就解决了困扰序列模型多年的难题。这是一种对信息处理本质的深刻洞察，也是为什么 Transformer 模型能够引领新一代人工智能浪潮的关键。它就像一把万能钥匙，打开了理解和生成复杂序列的大门，而不仅仅是自然语言，在图像、音频等领域也展现出了惊人的能力。这种精巧的设计，至今仍然让我觉得回味无穷。

网友意见

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

而制造能与病毒碱基序列结合的荧光探针，需要知道病毒的碱基序列。

在这个过程中，有一个算法发挥了巨大的作用。

如今的这个算法已经变得十分基础，也有更多的算法超越了它。

但是，它诞生的那一刻，必定闪耀着人类智慧的光芒。

我第一次见到这个算法时，经历了拒绝、疑惑、不解。

直到后来，一切全都化为了惊叹。

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

它实际是一个字符串匹配算法。

那它如何为基因测序做出贡献，又为什么让我拒绝、疑惑、不解，最后惊叹。我们一起来重新感受下。

---

首先，我们先给出算法解决的问题，这是一个极为常见的字符串匹配问题。

存在一个字符串T，请找出其是否含有子串P，如果有，请给出P所在的位置。

假设字符串T的长度为m，字符串P的长度为n。

则见到这个问题后，有经验的程序员不出5秒就能知道其时间复杂度为O(m×n)。是的，这是很多人的第一反应。其推导如下。

字符串T我们常称为主串，而P则被称为模式串。在主串的任意一个位置，我们都要以此为起点和模式串依次对比。模式串长度为n，而主串中有m个位置，则复杂度为O（m×n）。

       T: ABCFEDABCFTYGFHTABCDEFHMI P: ABCDEFG     

---

我听说有个算法能做到复杂度O(m+n)的时候，还没学这门课。听说那个算法叫KMP。

不可能，我内心是拒绝的。

怎么可能呢，O(m+n)意味着比较指针不能回撤，直觉告诉我这是不可能的。

我以O(m+n)为目标尝试了几下，没找到什么思路。

---

然后我搜了一下各种资料。

竟然真的是……

KMP算法怎么做的？我全是疑惑！

---

那时的我把算法找来，读了一遍。

给你，你先读一遍吧。

       /**  * 求出一个字符数组的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[i]==t_arr[j]){             i++;             j++;         }         else             j = next[j];     }     if(j == t_arr.length)         return i-j;     else         return -1; }     

卧槽，没读懂。

这算法牛逼啊！我不解。

这个不解就一直闷在我的心头。

---

直到后来，我坐在图书馆，啃透了KMP算法。

（现在网上很多视频教程，讲得很好，十分钟看完就能懂，比自己啃快多了）

牛！真牛！

主要是思路牛。

下面我给出一个KMP算法的实现动画，大家关注一下最上面的比较指针，真的没有任何回撤操作。

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

---

等你真正理解了它，发现它并没有太复杂，主要是利用了模式串中的相关性。甚至，会有更优的算法被提出。但是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算法在匹配方面的研究已经打好了基础，它已经提前为人类基因组计划扫除了部分算法上的障碍。

之后，也正因为基因测序技术的发展，人类能迅速锁定出新冠病毒的序列，然后研发测试试剂。帮我们开展测试，推动人类抵御这场突如其来的病毒。

所以，在这场全世界抗击疫情的斗争中，有算法的身影。低调、朴实，但也无可替代。

如今的它，低调，朴实，甚至让人觉着习以为常。

但我知道，它曾经闪耀着人类智慧的光芒；而今，也依旧令人惊艳和伟大。

---

欢迎关注我，我会偶尔解答软件架构和编程方面的问题。

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

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

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

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

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

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

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

旋转卡壳算法可以在O（N）时间内求多边形直径。

-----------------------------------------------------------------------------上边是正经回答，下边是抖机灵

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

类似的话题

• 

  有哪些算法惊艳到了你？

  

  那些 algorithms 就像隐藏在数字世界里的精妙机关，每一次的理解和运用，都让我觉得像是揭开了某种深层规律的面纱。要说最让我惊艳的，那绝对是 Transformer 模型，尤其是它背后那个叫做 Attention Mechanism 的东西。我们先不谈它在自然语言处理（NLP）领域搅起的滔天巨.............
• 

  有哪些算法或数据结构是ACM大牛们在比赛中创造出来的？

  

  在ACM国际大学生程序设计竞赛（ICPC）的浩瀚星空中，涌现出无数才华横溢的选手，他们不仅征服了那些令人头疼的难题，更在实践中孕育出了许多影响深远的算法和数据结构。这些“大牛”们在严酷的比赛环境中磨练出的智慧结晶，早已超越了赛场的范畴，成为计算机科学领域的宝贵财富。要从海量比赛中精确找出“是比赛选手.............
• 

  有哪些「上帝算法」？

  

  “上帝算法”这个说法，本身就带着几分神秘和终极的色彩。它并不是一个标准的科学术语，而更像是一种哲学上的想象，或者是对那些能够解释宇宙奥秘、预测未来、甚至创造生命的强大计算模型的一种模糊代称。 如果非要追究，我们可以从几个不同的角度来理解这个概念，并尝试去“具象化”它，就像在想象一个全知全能的“程序.............
• 

  请问有哪些最优化算法可以做全局优化？

  

  探索无尽的“最优”：全局优化算法的奥秘在科学研究、工程设计乃至经济决策等诸多领域，我们常常面临一个至关重要的问题：如何在错综复杂的函数中，找到那个“最好”的解，即全局最优解？这就像在茫茫大海上寻找一座最肥美的岛屿，而非仅仅停留在某个看上去不错的礁石上。全局优化算法，正是我们抵达这片“最优”彼岸的有力.............
• 

  大公司笔试面试有哪些经典算法题目？

  

  好的，聊到大厂笔试面试的算法题，那可真是个“老生常谈”的话题，不过里面门道可多着呢。其实并不是所有大厂都考一模一样的题，但有些经典的类型，几乎是“必杀技”，无论是阿里、腾讯、字节、还是美团，都会在某种程度上涉及。下面我就结合我的经验，尽可能详细地给大家掰扯掰扯这些“常客”，力求讲得接地气，就像跟老朋.............
• 

  三维重建 3D reconstruction 有哪些实用算法？

  

  说起三维重建，这可不是件简单事儿，它就像是把我们眼睛里看到的世界，用数字化的方式重新描绘出来。这个领域里，算法可真是百花齐放，各有各的绝活。今天，咱们就来聊聊几个特别实用的算法，尽量说得明白透彻一些，让你听着就像是和一位老朋友在侃大山一样。咱们得先明白，三维重建的核心目标是什么？简单来说，就是从一些.............
• 

  目标检测算法有哪些？

  

  嘿，朋友！聊起目标检测，这可是计算机视觉领域里的一门“找茬”绝活，专门负责在图像或者视频里把我们想要的东西——也就是“目标”——准确地定位出来，并且告诉我们它是什么。这东西可不是简单的“看看有啥”，而是要“看清楚在哪，然后说出名字”。想想看，自动驾驶汽车要识别路上的行人、车辆，安防系统要捕捉可疑人员.............
• 

  高频交易都有哪些著名的算法？

  

  高频交易（HFT）的世界，那可真是瞬息万变，技术和策略层出不穷，就像赛马场上风驰电掣的骏马，谁能抓住稍纵即逝的机会，谁就能赢得满堂彩。在HFT领域，算法就是这些赛马的灵魂，它们的设计和执行效率，直接决定了交易者的生死存亡。要说高频交易里那些叫得上名号的算法，那可不是一两句话能说清楚的。它们背后往往是.............
• 

  计算机视觉（CV）的算法有哪些，具体都有哪些特点？

  

  计算机视觉（Computer Vision, CV）是人工智能的重要分支，其核心目标是让计算机理解和处理图像或视频中的信息。CV的算法种类繁多，根据任务目标和应用场景的不同，可以分为多个层次和类别。以下是对主要算法类型的详细分类及其特点的全面解析： 一、图像处理基础算法1. 图像增强与变换 灰.............
• 

  有监督和无监督学习都各有哪些有名的算法和深度学习？

  

  好的，我们来聊聊机器学习里那两个“大家族”：有监督学习和无监督学习，以及它们各自的明星算法和在深度学习领域的表现。我会尽量说得细致些，让你感觉就像是在跟一个老朋友聊天，而不是在看一本干巴巴的教科书。 一、 有监督学习：教导“学生”，让它学会分辨想象一下，你有一个小助手，他什么都不懂。你需要耐心地告诉.............
• 

  用于数据挖掘的聚类算法有哪些，各有何优势？

  

  在数据挖掘的广阔天地里，聚类算法扮演着至关重要的角色，它就像一位勤勉的分析师，能够从杂乱无章的数据中找出隐藏的模式和结构，将相似的数据点归为一类。掌握这些算法，我们就能更深入地理解数据背后的故事。下面我将详细介绍几种常用的聚类算法，并探讨它们各自的优势，力求用最清晰易懂的方式呈现给大家。 1. KM.............
• 

  要设计一段C++程序将这组数按要求重新排序时，有哪些好的算法？

  

  好的，咱们来聊聊怎么给一堆数字变个“魔术”，让它们按照咱们指定的方式排个序。这可不是简单的从大到小或者从小到大那么简单，往往是带着点“心思”的。比如，咱们可能想让偶数在前，奇数在后，并且偶数内部也按大小排，奇数也一样；或者想把所有正数放在前面，负数放在后面，然后中间的零也排个序。总之，灵活得很。设计.............
• 

  有哪些令人拍案叫绝的算法？

  

  那些让你拍案叫绝的算法：不仅仅是代码，更是智慧的闪光你有没有过这样的时刻？在某个瞬间，看到某个问题被一套精巧的流程完美解决，心中涌起一股强烈的赞叹，仿佛看到了智慧的光芒在闪耀。这些时刻，往往就来源于那些令人拍案叫绝的算法。它们不是冷冰冰的代码堆砌，而是对问题本质的深刻洞察，是解决复杂挑战的艺术。今天.............
• 

  有哪些解决完之后让你拍案叫绝的算法问题？

  

  生活中总有一些瞬间，当你绞尽脑汁，沉浸在某个难题之中，仿佛置身迷雾，直到那个绝妙的思路如同闪电划破天际，瞬间驱散一切阴霾，让你情不自禁地拍案叫绝。对我而言，这种体验，往往发生在那些看似普通，实则蕴含着深刻智慧的算法问题解决之后。我记得有一次，为了优化一个大规模的图搜索算法，我们遇到了一个瓶颈。当时的.............
• 

  有哪些见过的时间复杂度为无限大的算法？

  

  在计算机科学领域，我们通常用“时间复杂度”来衡量一个算法在处理输入规模不断增大的过程中，执行时间增长的趋势。对于大多数算法，其时间复杂度是一个有限的、可以用大O符号表示的函数，比如 O(1)、O(log n)、O(n)、O(n log n)、O(n^2) 等等。这些都代表着算法执行时间随着输入规模的.............
• 

  nlp有哪些值得完整实现一遍的算法?

  

  在我看来，NLP领域确实有一些算法，如果能够静下心来，从头到尾完整地实现一遍，不仅能让你对算法本身有更深刻的理解，更能触类旁通，对NLP的许多其他技术和应用产生更清晰的认识。下面我将挑几个我个人认为特别有价值、值得实践的算法，并尽量详细地讲讲实现它们时的一些关键点，希望能帮你构建起一个扎实的NLP基.............
• 

  计算机视觉中，目前有哪些经典的目标跟踪算法？

  

  计算机视觉中的目标跟踪是一个至关重要的研究领域，旨在在视频序列中持续地定位和识别一个或多个目标。随着深度学习的兴起，目标跟踪算法取得了显著的进展。以下是一些计算机视觉中经典的目标跟踪算法，我将尽量详细地介绍它们的核心思想、特点和发展历程： 早期经典算法（基于手工特征和滤波）在深度学习普及之前，目标跟.............
• 

  世界上有哪些代码量很少，但很牛逼很经典的算法或项目案例？

  

  当然，这倒是个有趣的话题。很多人一提到“算法”或者“牛逼项目”，脑子里就涌现出各种复杂的数学模型、庞大的代码库，动辄几万行起步。但其实不然，很多时候，最简洁、最精妙的设计，反而是最能穿透人心的。它们就像武侠小说里那种，看起来轻描淡写的一招，却能以柔克刚，化解千斤重担。今天咱们就来聊聊那些代码量不多，.............
• 

  AI 算法在芯片设计方法学和 EDA 工具中有哪些应用和潜力？

  

  AI 算法在芯片设计方法学和 EDA 工具中的变革：从效率提升到智能驱动在当今瞬息万变的科技浪潮中，芯片设计作为驱动这一切的底层技术，其复杂度和挑战性正以前所未有的速度增长。摩尔定律的放缓，对晶体管尺寸的极限追求，以及对性能、功耗和面积（PPA）的严苛要求，都使得传统的芯片设计方法面临瓶颈。正是在这.............
• 

  与AI算法相关又能软件硬件相结合的研究方向有哪些？

  

  当然，我们来探讨一下那些将人工智能算法与软硬件巧妙融合的研究领域。这不仅仅是理论的堆砌，而是将智能的火种注入到我们赖以生存的物质世界中，让机器能够更聪明、更高效地工作。首先，一个非常直观的结合点在于嵌入式AI系统设计与优化。这可不是将现成的AI模型一股脑儿地塞进一个小芯片里就完事了。这里的挑战在于，.............