有哪些算法惊艳到了你？
有哪些算法当你刚接触的时候，心里有“居然还可以这样算..”的想法？ 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)的算法，真是太惊艳了！ Angluin's Learning Algorithm
假设用户心里想了一门正则语言，程序通过反复询问用户某个句子是否属于这门语言，经过有限步询问可以构造出这门语言对应的DFA 蒙特卡洛！！
可以说这是工程师特别喜欢的，但是数学学者特别讨厌的东西，其实一开始让我用这么骚的办法呢，我是拒绝的……但是耐不住好用啊，比如算光线追踪就直接存一堆种子然后开始投射线，一帧不行我弄它个10000帧合并到一起，这结果不就有了么？CPU算不过来我把数据全堆GPU里算，看到论文那一大片积分公式，一点都不慌的，我反手预积分存一波像素甚至体素，你怎么说？反正结果算的很对啊。
这法子实在太暴力太好用了，以至于在后来做数学作业的时候还在游戏引擎的编辑器里写了一套基于GPGPU的蒙特卡洛计算器，遇到类似空间解析这种问题直接填数进去刷刷刷求出个值来，爽的就不谈了，作业整个就填个答案，教授问我咋回事，我就说我算出来了不行么？
后来呢？我这不是在重修么？？
遗传算法，我知道，这是一大类算法，但这算法的思想着实让人感到「惊艳」。
非常朴素的随机迭代、通过Fitness函数筛选，模拟自然界的生物进化过程，就能解决很多问题。
北京的那个鸟巢体育馆的钢结构，就是用遗传算法迭代出来的，整体非常稳固。
日本的新一代高速列车车头用遗传算法设计，节约了30%的能量。
美国的 X-Band 卫星上的天线用演化算法设计，体积只有硬币大小。
社会学研究上，有用演化算法配合神经网络工作，也非常有趣。
遗传算法可能看起来很「暴力」，很「粗糙」，但是确实蕴含了很多的「可能性」，而且非常自然，非常容易理解，是非常美的算法。 RSA 非对称加密！
下面这三个小伙子，因为确保了恋爱中的小芳和小明互通情话的绝对安全，而获得 2002 年图灵奖。
该！确实该！为什么呢？
因为它真正做到了只有上帝和您知道！
活这么大了， 谁还没点儿秘密呢，而如何绝对的保守秘密？确是个头痛的问题……
有很好的方法吗？ 还真有！
那就是让人惊艳的 RSA 非对称加密！
什么是非对称加密呢？
我们先来看个例子：
有个女孩叫小芳，她想告诉男朋友小明一个秘密，而暗恋她的大鹏想偷听！
传统思路是： 她先准备个盒子，再配两把钥匙，小芳、小明各一把， 小芳把秘密装进盒子锁好，寄给小明，小明用钥匙打开盒子，接收秘密， 大鹏没有钥匙，即使截获了盒子也打不开……
这种方式就是传统的对称加密。
前提是小芳和小明都必须有钥匙。
然而， 这在网络应用中，会有很多问题！
最大的问题就是，小芳和小明没办法总是提前在一起商量好钥匙和锁！她必须把钥匙寄给小明，这个寄的过程就可能被截获破解！
一旦寄（网络传输） 时钥匙被复制，就等于破解！ 大鹏就知道了秘密。
这就是传统对称加密的最大问题！
----------------------------------------------------------------------------------------------------
为了彻底解决这个问题！ RSA 提出了著名的非对称加密：
小芳跟小明说，我要告诉你一个秘密，好！
小明通过网络先给小芳发去一个加密机（公钥），同时自己保有一把与该加密机对应的钥匙，他不用告诉任何人，包括小芳， 只有上帝知道， 这样就彻底避免了钥匙传输截获。
真正的是只有上帝和您一个人知道！
小芳用加密机把消息加成密文通过网络传给小明，小明用自己的钥匙可以很快打开消息。
当然， 在网上， 大鹏可能截获到密文和加密机(公开的)。
但与之配对的钥匙,只在小明脑中。
他要穷举破解的话， 按理论计算最快要几百年， 最慢甚至是太阳系灭亡的时间。
这， 还暗恋个屁啊...…
有的同学可能会问，钥匙只在小明手中，他要回信的话，小芳又如何打开呢？
很简单，小芳也给小明发一个加密机（公钥） ， 而自己保有一把只有自己知道的钥匙， 小明把情话用她的加密机加密成密文回给小芳，小芳有自己的钥匙也可以很快明白小明在说啥。
这样， 就可以绝对安全的 bla、 bla、 bla……互通情话了。
----------------------------------------------------------------------------------------------------
我们举个简单的例子,大家可以试着验证。
取 https://www.zhihu.com/equation?tex=p_1= 3,https://www.zhihu.com/equation?tex=p_2+ = 11，（现实中是很大两个素数）
则有 n= https://www.zhihu.com/equation?tex=p_1%2Ap_2+ = 33， = 210 = 20
在［1， 20］ 之间取一个与 20 互素的数， 3(公钥 e)
求出其关于 20 的取余逆元， 7(私钥) 因为（7× 3％20＝1）
现在有公钥（3， 33）私钥（7， 33）
小芳对小明发送了个数字 9，加密后会得到密文 3
小明用自己的钥匙 7 对密文 3 解密，会得到明文 9
其它数字，大家可以自己试一下（33 以内的）
下面说说， 为什么大鹏要破解的话会如此之难？
主要理论基础， 来源于大数的质因素分解真的很难很难！
不想了解过程原理的同学，到此可以停止了。
----------------------------------------------------------------------------------------------------
过程简要解析：
两个大素数相乘容易，分解难。
2.不大于某数 (n)且与其互素的数的个数，与其素因子有某种关系，欧拉定理已指明，大数找到素因子很难，而若有两个素因子相乘得到大数很简单。
3.在 1 与 之间，随机找一个不等于任一素因子的公钥 e,根据费马小定理，找到 e 的关于取余逆元 d(私钥)，自已保留好。
4.把 n， e 发给小芳,她可以把信息用 n， e 变换后发给小明， 小明通过 d 同余变换轻易还原信息，世界上只有小明知道 d。
5.假设大鹏截获了 n， e 和小芳的密文，想要破解， 他得先把 n 的两个素因子 p1,p2 找到， 才能根据欧拉函数轻易得到， 得几百年，若靠穷举法找估计得等到太阳系灭亡。
6.然后根据和 e 反推私钥 d。
7.再者 e 是［1，］ 中非素因子中随机的一个整数， 一个 e 与一个相应的 d 配对。
8.稍稍变换 e 很容易，而 d 也可以通过公式很快得到。若频繁更换，相应的破解难度就又指数级加大了！
大鹏只有哭啊 ……
下面写两个个人觉得比较漂亮的算法：A. 用于解决无向图的最大切的Goemans-Williamson算法。它把图与高维几何结合起来，思路很奇妙；B. 一个在数据流中找出现次数比较多的字符的算法。
A. 最大切(max cut)
定义：给定一张连通的无向无权图https://www.zhihu.com/equation?tex=G+%3D+%28V%2C+E%29，其中是点集，https://www.zhihu.com/equation?tex=E是边集。如果是的一个划分，即https://www.zhihu.com/equation?tex=S+%5Ccap+T+%3D+%5Cemptyset且https://www.zhihu.com/equation?tex=S%5Ccup+T+%3D+V，我们称与之间的边为一组切(cut)，我们用来表示这个切。最大切问题就是找到的一个划分https://www.zhihu.com/equation?tex=%28S%5E%2A%2C+T%5E%2A%29，使得得到的切所包含的边的数量是最多的。
1. https://www.zhihu.com/equation?tex=%5Cmathcal%7BO%7D%28%7CV%7C%29复杂度的2倍近似比（随机）算法
最大切是一个NP-hard的问题，因此不大可能在合理时间内精确地求解出最优解。如果我们允许最终得到的结果有一定误差，那么对于最大切问题，存在一个非常简单的算法：对每一个https://www.zhihu.com/equation?tex=v+%5Cin+V，等概率随机将其分到和中的一个。用https://www.zhihu.com/equation?tex=%5Ctexttt%7BOPT%7D%5ER表示得到的切的大小，用https://www.zhihu.com/equation?tex=%5Ctexttt%7BOPT%7D表示真正最大切的大小。那么有：https://www.zhihu.com/equation?tex=%5Cmathbb%7BE%7D%5B%5Ctexttt%7BOPT%7D%5ER%5D+%5Cgeq+%5Ctexttt%7BOPT%7D+%2F+2。其中，https://www.zhihu.com/equation?tex=%5Cmathbb%7BE%7D代表期望。证明如下。
证明：对每条边，将出现在切中当且仅当https://www.zhihu.com/equation?tex=u和https://www.zhihu.com/equation?tex=v分别属于和。定义随机变量https://www.zhihu.com/equation?tex=%5Cmathbb%7BI%7D_%7B%28u%2Cv%29%7D：当https://www.zhihu.com/equation?tex=u%5Cin+S+%5Cwedge+v%5Cin+T或者https://www.zhihu.com/equation?tex=u+%5Cin+T+%5Cwedge+v+%5Cin+S时，https://www.zhihu.com/equation?tex=%5Cmathbb%7BI%7D_%7B%28u%2Cv%29%7D+%3D+1；否则https://www.zhihu.com/equation?tex=%5Cmathbb%7BI%7D_%7B%28u%2Cv%29%7D+%3D+0。易得：https://www.zhihu.com/equation?tex=%5Cmathbb%7BE%7D%5B%5Cmathbb%7BI%7D_%7B%28u%2Cv%29%7D%5D+%3D+1+%2F2+。另外，由https://www.zhihu.com/equation?tex=%5Ctextstyle%7B%5Ctexttt%7BOPT%7D%5ER+%3D+%5Csum_%7B%28u%2C+v%29+%5Cin+E%7D%5Cmathbb%7BI%7D_%7B%28u%2Cv%29%7D%7D可以得到https://www.zhihu.com/equation?tex=%5Ctextstyle%7B%5Cmathbb%7BE%7D%5B%5Ctexttt%7BOPT%7D%5ER%5D+%3D+%5Csum_%7B%28u%2C+v%29+%5Cin+E%7D%5Cmathbb%7BE%7D%5B%5Cmathbb%7BI%7D_%7B%28u%2Cv%29%7D%5D+%3D+%7CE%7C+%2F+2+%5Cgeq+%5Ctexttt%7BOPT%7D+%2F+2%7D。https://www.zhihu.com/equation?tex=%5Cblacksquare
2. Goemans-Williamson算法
个人觉得它比前两个方法都巧妙：它不再单纯从图的角度来看最大切，而是将最大切与高维几何结合起来。具体的，对于图中的每个点https://www.zhihu.com/equation?tex=v_i+%5Cin+V，算法把映射到https://www.zhihu.com/equation?tex=n+%3D+%7CV%7C维空间中以原点为中心的单位球的一个点上，即https://www.zhihu.com/equation?tex=x_i+%5Cin+%5Cmathbb%7BR%7D%5En且https://www.zhihu.com/equation?tex=%5C%7Cx_i%5C%7C+%3D+1。这里，https://www.zhihu.com/equation?tex=%5C%7Cx_i%5C%7C代表向量的长度。如果https://www.zhihu.com/equation?tex=%28v_i%2C+v_j%29+%5Cin+E，那么与https://www.zhihu.com/equation?tex=x_j之间也会有一条线段相连。如下图。让是一个随机生成的过原点的超平面。将单位球切成两半，也就是把所有分成了两部分，一部分在的“上面”，另一部分在的“下面”。这两部分对应着原图的一个切，而切的大小就是被切过的线段的数量。如下图。通过为每个点选择适当的，我们能使最终得到的切的大小满足https://www.zhihu.com/equation?tex=%5Cmathbb%7BE%7D%5B%5Ctexttt%7BOPT%7D%5E%7BGW%7D%5D+%5Cgeq+0.878%5Ccdot+%5Ctexttt%7BOPT%7D。这里的随机性来源于超平面的选择的随机性。
如何选择？ 对于边https://www.zhihu.com/equation?tex=%28v_i%2C+v_j%29，其对应的线段的长度为https://www.zhihu.com/equation?tex=%5C%7Cx_i+-+x_j%5C%7C。直观上，的长度越长，其被切到的概率就越大。因此，要使得总的被切到的线段尽可能多，我们应该使所有线段的长度尽可能长。所以，定义以下目标函数：
https://www.zhihu.com/equation?tex=f%28G%2C+x_1%2C+%5Ccdots%2C+x_n%29+%3D+%5Csum_%7B%28v_i%2C+v_j%29+%5Cin+E%7D+%5Cfrac%7B1%7D%7B4%7D+%5C%7Cx_i+-+x_j%5C%7C%5E2+%3D+%5Csum_%7B%28v_i%2C+v_j%29+%5Cin+E%7D+%5Cfrac%7B1%7D%7B2%7D+%281+-+x_i%5ETx_j%29
是所有线段的长度的平方和。这里之所以用平方，主要是为了解决问题的方便。根据我们之前的讨论，应该尽可能大。因此，优化问题如下定义：
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%7D%0A%5Ctext%7Bmaximize%7D%5C+%26%5C+f%28G%2C+x_1%2C+%5Ccdots%2C+x_n%29+%5C%5C%0A%5Ctext%7Bsubject+to%7D%5C+%26%5C+%5C%7Cx_i%5C%7C+%3D+1%5Ctext%7B+for+%7D++1%5Cleq+i+%5Cleq+n+%5C%5C%0A%26%5C+x_i+%5Cin+%5Cmathbb%7BR%7D%5En+%5Ctext%7B+for+%7D+1+%5Cleq+i+%5Cleq+n%0A%5Cend%7Balign%7D
这个问题是多项式可解的（这里就不详述了）。我们用表示问题的最优值。
证明：这里只给出证明的思路。我们主要需要证明两个不等式：（1）https://www.zhihu.com/equation?tex=f_%7Bmax%7D+%5Cgeq+%5Ctexttt%7BOPT%7D，即是的最大切的上界；（2）https://www.zhihu.com/equation?tex=%5Cmathbb%7BE%7D%5B%5Ctexttt%7BOPT%7D%5E%7BGW%7D%5D+%5Cgeq+0.878f_%7Bmax%7D，即GW算法返回的切的大小的期望不小于https://www.zhihu.com/equation?tex=0.878f_%7Bmax%7D。这两个不等式合起来可得：https://www.zhihu.com/equation?tex=%5Cmathbb%7BE%7D%5B%5Ctexttt%7BOPT%7D%5E%7BGW%7D%5D+%5Cgeq+0.878%5Ctexttt%7BOPT%7D。
注：GW算法中的图引自"Geometric representation of graphs"这本书。
B. 在数据流中找Frequent Items
问题定义：用https://www.zhihu.com/equation?tex=%5Cmathcal%7BS%7D+%3D+x_1%2C+x_2%2C+%5Ccdots%2C+x_N，https://www.zhihu.com/equation?tex=x_i+%5Cin+%5CSigma表示一个长度为https://www.zhihu.com/equation?tex=N的数据流。其中，https://www.zhihu.com/equation?tex=%5CSigma表示一个包含https://www.zhihu.com/equation?tex=n个字符的符号表。我们用表示字符在的出现次数。Frequent Items问题的定义是：给定一个常数https://www.zhihu.com/equation?tex=0%3C%5Cphi%3C0.5，找到所有在中出现了至少https://www.zhihu.com/equation?tex=%5Cphi+N次的字符，即https://www.zhihu.com/equation?tex=I%28%5Cmathcal%7BS%7D%2C+%5Cphi%29+%3D+%5C%7Bx+%5Cin+%5CSigma+%5Cmid+f_%5Cmathcal%7BS%7D%28x%29+%5Cgeq+%5Cphi+N%5C%7D。
易知：https://www.zhihu.com/equation?tex=%7CI%28%5Cmathcal%7BS%7D%2C+%5Cphi%29%7C+%5Cleq+1+%2F+%5Cphi；否则中的字符在中将出现大于https://www.zhihu.com/equation?tex=%5Cphi+N+%5Ccdot+1+%2F+%5Cphi+%3D+N次。
我们假设：https://www.zhihu.com/equation?tex=N+%5Cgg+n+%5Cgg+1+%2F+%5Cphi；另外，我们也假设：中的字符按照顺序依次到来。因为内存非常小，我们无法将保存下来。一个例子就是网络中的路由器，数据包会不断地到达路由器，而路由器的内存非常小。
Karp提了一个只需要空间的算法，而且可以保证算法得到的结果满足：。
算法：该算法维护了个计数器（占用的空间），均初始化为0。在算法中，我们将把空闲的计数器（即计数显示为0）赋给新到来的没有计数器的字符。当到达的时候，有三种情况：
如果有计数器，其对应的计数器加1；如果没有计数器，但存在着空闲计数器（计数为0），那么就把这个计数器赋给，计数更新为1；如果前面两种情况都不成立，那么所有计数器都减少1。
当所有元素都已到达并处理完时，返回所有计数器的当前所有者，记作。
这里，我们证明。假设https://www.zhihu.com/equation?tex=x+%5Cnotin+I%5E%2B%28%5Cmathcal%7BS%7D%2C+%5Cphi%29。那么在算法中，一共被消去了次。这里的消去是指：要么（1）到来的时候正好属于上面提到的第三种情况；要么（2）所持有的计数器因为其他字符的到来而减1。无论是哪一种情况，每次被消去的时候，同时也有其他至少个字符被消去。因此， 总的消去的字符至少为https://www.zhihu.com/equation?tex=f_%5Cmathcal%7BS%7D%28x%29%281++%2F+%5Cphi+%2B+1%29+%5Cleq+N。因此，https://www.zhihu.com/equation?tex=f_%5Cmathcal%7BS%7D%28x%29+%3C+%5Cphi+N+%5CRightarrow+x+%5Cnotin+I%28%5Cmathcal%7BS%7D%2C+%5Cphi%29。
如果我们允许读取多一遍，那么我们可以精确求出。
数据流的频率估计问题：Karp的算法也可以用来估计在中出现的次数。唯一的变动是当中所有元素都已处理完的时候，如果一个字符持有一个计数器，就把该计数器的值作为的频率估计值，记作https://www.zhihu.com/equation?tex=c%28x%29；否则，https://www.zhihu.com/equation?tex=c%28x%29+%3D+0。可以保证，当计数器的个数为时，https://www.zhihu.com/equation?tex=c%28x%29+%5Cleq+f_%5Cmathcal%7BS%7D%28x%29+%5Cleq+c%28x%29+%2B+%5Cphi+N。理由如下：对于字符，其一共被消去了https://www.zhihu.com/equation?tex=f_%5Cmathcal%7BS%7D%28x%29+-+c%28x%29次。由前面的证明有：https://www.zhihu.com/equation?tex=f_%5Cmathcal%7BS%7D%28x%29+-+c%28x%29+%5Cleq+%5Cphi+N+%5CRightarrow+f_%5Cmathcal%7BS%7D%28x%29+%5Cleq+c%28x%29+%2B+%5Cphi+N+。 我也来列一些不是那么常见的算法或者算法设计思想。这些算法我已熟知多年，但是回忆起第一次见到的场景仍然是胸中激荡。
1. The power of power of 2
下午跟同事吃饭的时候正好聊到一个问题：假设你站在一个足够长的走廊上，在这个走廊的某个位置有一个物品你需要去找到它，请问你应该选择什么样的搜索策略。这个问题的关键在于你不知道目标是在你的左边还是右边，为了保证在线性复杂度内找到它，你可以先向左走1步，回到起点，再向右走1步，再回到起点并向左走2步，……，就这样按照 1，2，4，8，...的等比数列进行搜索，一直到发现目标为止。（虽然在这里2的等比并非是最优的，但这个不重要。）
很简单的思想对吧，但不知当面试时遇到“请问怎么检测一个链表是否有环”的问题时你是否能举一反三呢？我反正是没想到，但是有人想到了，这就是Brent's Algorithm http://en.wikipedia.org/wiki/Cycle_detection 。这个算法与所谓的标准解法（快慢指针，或者叫做Floyd's Algorithm）一样优秀（如果不是更好的话，）请务必随身装备，这样下次若有面试官还问你就可以好好秀一把：这个问题我有三种解法blablabla...然后把Brent's Algorithm丢出去糊他一脸。
2. Fractional Cascading
http://en.wikipedia.org/wiki/Fractional_cascading，史上最酷炫的算法设计技巧没有之一。首先名字就取得非常骚包，其次，还十分有疗效。利用它可以一次性解决计算几何中的一大票问题，比如Orthogonal Range Query，Multiple List Query，Point Location，等等。
3. Rabin Flips a Coin
https://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/。求平面上最近点对的O(nlogn)算法大家都知道，因为算法导论上有写。但是O(n)的算法就没那么多人了解了。Rabin's Algorithm是随机算法中的一个典型代表，看上去直接粗暴，甚至比算导上那个分治法还要简单得多，为什么某名其妙就O(n)了呢？
4. Indirection
5. Amortizing - Deamortizing
以后再写…… floyd 最短路算法，简洁。 必须是数论变换,我不嫌丢人,看到这个算法之前我根本不知道数论能干吗用.
一个基于数论的变换,把整数域变换到整数域,居然能和FFT形式上一致,还和定点DSP
结合得这么好,连乘法器都不用,直接移位就能快速算卷积,惊了! 当时是在图书馆的一个
很破,旧的发黄的书上看到的,当时有一种摔下悬崖无意中发现了武功秘籍的感觉....