有哪些算法惊艳到了你？

有哪些算法当你刚接触的时候，心里有“居然还可以这样算..”的想法？

期权匿名回答 · 2023-2-11 02:04:42

混乱的桌子更容易找到自己马上需要用的东西，这个其实是经典的LRU Cache算法，当你随意放置你的物品时，你事实上把最近常用的东西都放到了堆顶。如果你喜欢整理物品而不记住每一个物品的准确位置，那么你的效率要比随意乱放低一个次数，不过是找个理由大量浪费时间罢了。

1/6/2023
介于评论区争议比较大，这里确实有很多隐性假设：
桌子足够小，检索时间足够短，视力足够好，一眼定正。我个人感觉我的桌子上近期使用过的东西（都已经在堆顶）无论它们之间如何叠加我都能直接找到不需要翻来翻去，所以默认我对桌子上的东西硬编码了（所以我想强调的其实是least recent used的策略合理性，而不是搜索的速度性，因为在默认硬编码下任何组织算法都是O(1), 而LRU策略的高效体现在你最后会留哪些物品在桌子上，排序算法没有考虑桌面的特殊情况，对桌面不做任何假设，就像你的电脑的CPU直接插在硬盘上，没有寄存器，L1/L2和内存）。有些人说整理更容易找到不常用的东西，这个是很常见的错误，因为你找一次的大量时间浪费很容易被均摊到忽略不计，类似于可变数组尾部插入是O(1)，即使单次延长数组的复杂度是O(n)。另外对于大面积的储存管理，显然是排序分配之后树类算法更合适。

期权匿名回答 · 2023-2-11 02:05:29

蒙特卡洛！！
可以说这是工程师特别喜欢的，但是数学学者特别讨厌的东西，其实一开始让我用这么骚的办法呢，我是拒绝的……但是耐不住好用啊，比如算光线追踪就直接存一堆种子然后开始投射线，一帧不行我弄它个10000帧合并到一起，这结果不就有了么？CPU算不过来我把数据全堆GPU里算，看到论文那一大片积分公式，一点都不慌的，我反手预积分存一波像素甚至体素，你怎么说？反正结果算的很对啊。
这法子实在太暴力太好用了，以至于在后来做数学作业的时候还在游戏引擎的编辑器里写了一套基于GPGPU的蒙特卡洛计算器，遇到类似空间解析这种问题直接填数进去刷刷刷求出个值来，爽的就不谈了，作业整个就填个答案，教授问我咋回事，我就说我算出来了不行么？
后来呢？我这不是在重修么？？

期权匿名回答 · 2023-2-11 02:06:11

遗传算法，我知道，这是一大类算法，但这算法的思想着实让人感到「惊艳」。
非常朴素的随机迭代、通过Fitness函数筛选，模拟自然界的生物进化过程，就能解决很多问题。
北京的那个鸟巢体育馆的钢结构，就是用遗传算法迭代出来的，整体非常稳固。

日本的新一代高速列车车头用遗传算法设计，节约了30%的能量。

美国的 X-Band 卫星上的天线用演化算法设计，体积只有硬币大小。

社会学研究上，有用演化算法配合神经网络工作，也非常有趣。
遗传算法可能看起来很「暴力」，很「粗糙」，但是确实蕴含了很多的「可能性」，而且非常自然，非常容易理解，是非常美的算法。

期权匿名回答 · 2023-2-11 02:06:58

Reservoir Sampling(
Reservoir sampling )
这是我在今年求职过程中面试的时候被问到的，因为之前很少接触Streaming的算法，在听到这个题目的时候被惊呆了，根本不能理解：
给一个Streaming的Data，未知长度，要求在Streaming结束后返回N个Data，且是等概率的。
在听到这个问题的时候简直惊呆了。如果Streaming长度已知为L，当然对于每一个Data，我生成一个N/L的概率即可。但是长度未知，也即概率未知，怎么可能在Data来的时候判断要不要保留这个Data，还能保证是等概率的……百思不得其解。
事后一番研究，才发现了这类算法，算法之简单令人惊叹：
首先保留前N个Data，对于后面来的Data以N/i的概率选择是否保留，i为当前Data序号，保留的话在原来保留的N的Data中随机剔除一个。最后返回这N的即可。
证明也很容易，奇妙得地方在于在计算概率的时候，出现了很长的，可以前后上下不断约掉的分式。相互约去之后剩下的概率刚好是N/L，L为总长度。简直美妙极了！
显然这类算法也非常有用，因为在实际问题中会出现大量需要在Streaming的数据中进行Sample，为下一步处理数据做准备的情形。而这竟然有一个O(L)的算法，真是太惊艳了！

期权匿名回答 · 2023-2-11 02:07:21

Angluin&#39;s Learning Algorithm
假设用户心里想了一门正则语言，程序通过反复询问用户某个句子是否属于这门语言，经过有限步询问可以构造出这门语言对应的DFA

有哪些算法惊艳到了你？

5 个回复