AlphaDev 发现新的排序算法，直接突破人类极限

[iamqk]

https://mp.weixin.qq.com/s/kHahnmVZP3qD_TGKrlXQ5Q

...
在一项新发表于《自然》杂志的研究中，DeepMind 团队介绍了一种新的人工智能（ AI ）系统——AlphaDev ，它通过使用深度强化学习，发现了更快的排序算法。这些全新的算法超越了现有的、最优的、由人类科学家在数十年时间里磨炼出的算法。
...
最终，AlphaDev 发现了新的、更快的排序算法。对于较短的序列，AlphaDev 的算法可以将速度提高 70%。但对于超过 25 万个项的序列，累积节省的时间只能提高 1.7%。
...

元芳，你怎么看？

[Wenbobobo]

https://www.zhihu.com/answer/3064456593
“ 这个 99% 没用, 即便是分治类型的排序算法, 这也不在分解的关键路径上.派发开销能不能赚回来都不知道, 反正他们给 LLVM 提的 pr 还搁置着, 效果存疑. ”
👀

[GPLer]

这个好像只是优化汇编，并没有发明新的排序算法。。。

[iamqk]

@Wenbobobo 没看那个回复的评论？

[iamqk]

<img alt="搞笑回复" src="http://picx.zhimg.com/80/v2-9ba345c1a7d0e811510083e92d28153c_1440w.webp?source=1940ef5c">

[shyrock]

知乎的回答说到了点上。
这不是有没有新算法的问题，而是能否颠覆信息论的问题。

在信息论的框架下，各种排序算法都有其适用的场景（有不同的最坏情况），并且在效率上都有一个共同的上限。
这种公众号文章，要么是揣着明白装糊涂骗流量，要么就是计算机民科。

[Chinsung]

现有的排序算法都是基于数据证明的，AI 除非发现新的数学，不然在时间复杂度上我个人觉得不会有什么太离谱的跨越

[Chinsung]

@Chinsung 数学证明

[lusi1990]

一眼假， 现在计算机的排序早就比人类快了

[leimao]

他这个优化的是排序算法 Master Theorem 递归公式里的常数项，也就是 sort_2, sort_3, sort_4 ，这种的，不影响长序列的 asymptotic complexity 。理论意义不如他们去年发现的 Matrix Multiplication 的有着更好 asymptotic complexity 的算法。

[leimao]

另外，我看网上有人直接问 ChatGPT 让它做同样的优化，ChatGPT 也能得到同样的优化方法。（不过不晓得他们玩的那个版本的 ChatGPT 有没有看过这个文献）

[leimao]

[Strassen Algorithm]( https://leimao.github.io/blog/Strassen-Algorithm/)曾被认为是 Matrix Multiplication 在 asymptotic complexity 理论上最优的算法，但是去年 DeepMind 的 RL 搜索出了一个更好的，那个其实更有意思。

[leimao]

https://leimao.github.io/blog/Strassen-Algorithm/

[leimao]

另外，**基于比较**的排序算法 asymptotic complexity 理论最优就是 O(NlogN)，这个是不可能被打破的。

[idealhs]

你那边的楞类鸡腺是不是有点低