下面是二十世纪最好的十大算法：(自http://yinyifan.com/blog/2008/10/the_most_famous_alogrithm_in_20)

20世纪最好的算法，计算机时代的挑选标准是对科学和工程的研究和实践影响最大。下面就是按年代次序排列的20世纪最好的10个算法。

1. Monte Carlo方法
1946年，在洛斯阿拉莫斯科学实验室工作的John von Neumann，Stan Ulam和Nick Metropolis编制了Metropolis算法，也称为Monte Carlo方法。Metropolis算法旨在通过模仿随机过程，来得到具有难以控制的大量的自由度的数值问题和具有阶乘规模的组合问题的近似解法。数字计算机是确定性问题的计算的强有力工具，但是对于随机性（不确定性）问题如何当时并不知晓，Metropolis算法可以说是最早的用来生成随机数，解决不确定性问题的算法之一。

2. 线性规划的单纯形方法
1947年，兰德公司的Grorge Dantzig创造了线性规划的单纯形方法。就其广泛的应用而言，Dantzig算法一直是最成功的算法之一。线性规划对于那些要想在经济上站住脚，同时又有赖于是否具有在预算和其他约束条件下达到最优化的能力的工业界，有着决定性的影响(当然，工业中的“实际”问题往往是非线性的；使用线性规划有时候是由于估计的预算，从而简化了模型而促成的)。单纯形法是一种能达到最优解的精细的方法。尽管理论上讲其效果是指数衰减的，但在实践中该算法是高度有效的——它本身说明了有关计算的本质的一些有趣的事情。

3. Krylov子空间叠代法
1950年，来自美国国家标准局的数值分析研究所的Magnus Hestenes, Eduard Stiefel和Cornelius Lanczos开创了Krylov子空间叠代法的研制。这些算法处理看似简单的求解形为Ax=b的方程的问题。当然隐藏的困难在于A是一个巨型的n*n 矩阵，致使代数解x=b/A是不容易计算的(确实，矩阵的“相除”不是一个实际上有用的概念)。叠代法——诸如求解形为Kx(k+1)=Kx(k)+b-Ax(k)的方程，其中K 是一个理想地“接近”A 的较为简单的矩阵——导致了Krylov子空间的研究。以俄罗斯数学家Nikolai Krylov命名的Krylov子空间由作用在初始“余量”向量 r(0)=b-Ax(0)上的矩阵幂张成的。当 A是对称矩阵时，Lanczos找到了一种生成这种子空间的正交基的极好的方法。对于对称正定的方程组，Hestenes 和Stiefel提出了称为共轭梯度法的甚至更妙的方法。过去的50年中，许多研究人员改进并扩展了这些算法。当前的一套方法包括非对称方程组的求解技巧，像字首缩拼词为GMRES和Bi-CGSTAB那样的算法。(GMRES和Bi-CGSTAB分别首次出现于1986和1992 SIAM journal on Scientific and Statistical computing(美国工业与应用数学学会的科学和统计计算杂志)。

4. 矩阵计算的分解方法
1951年，橡树岭国家实验室的A1ston Householder系统阐述了矩阵计算的分解方法。研究证明能把矩阵因子分解为三角、对角、正交和其他特殊形式的矩阵是极其有用的。这种分解方法使软件研究人员能生产出灵活有效的矩阵软件包。这也促进了数值线性代数中反复出现的大问题之一的舍入误差分析问题。 (1961年伦敦国家物理实验室的James Wilkinson基于把矩阵分解为下和上三角矩阵因子的积的LU分解，在美国计算机协会(ACM)的杂志上发表了一篇题为“矩阵逆的直接方法的误差分析”的重要文章。)

5. Fortran最优编译程序

1957年，John Backus在IBM领导一个小组研制Fortran最优编译程序。Fortran的创造可能是计算机编程历史上独一无二的最重要的事件：科学家(和其他人)终于可以无需依靠像地狱那样可怕的机器代码，就可告诉计算机他们想要做什么。虽然现代编译程序的标准并不过分――Fortran I只包含23，500条汇编语言指令――早期的编译程序仍然能完成令人吃惊的复杂计算。就像Backus本人在1998年在IEEE annals of the History of computing 发表的有关Fortran I，II, III的近代历史的文章中回忆道：编译程序“所产生的如此有效的代码，使得其输出令研究它的编程人员都感到吓了一跳。”

6. 矩阵本征值计算的QR算法
1959—61年，伦敦Ferranti Ltd.的J.G. F. Francis找到了一种称为QR算法的计算本征值的稳定的方法。本征值大概是和矩阵相连在—起的最重要的数了，而且计算它们可能是最需要技巧的。把—个方阵变换为一个“几乎是”上三角的矩阵――意即在紧挨着矩阵主对角线下面的一斜列上可能有非零元素――是相对容易的，但要想不产生大量的误差就把这些非零元素消去，就不是平凡的事了。QR 算法正好是能达到这一目的的方法，基于QR 分解， A可以写成正交矩阵Q 和一个三角矩阵R 的乘积，这种方法叠代地把 A=Q(k)R(k) 变成 A(k+1)==Q(k)R(k) 就加速收敛到上三角矩阵而言多少有点不能指望。20世纪60年代中期QR 算法把一度难以对付的本征值问题变成了例行程序的计算。

7. 快速分类法
1962：伦敦Elliott Brothers, Ltd.的Tony Hoare提出了快速(按大小)分类法.把n个事物按数或字母的次序排列起来，在心智上是不会有什么触动的单调平凡的事。智力的挑战在于发明一种快速完成排序的方法。Hoare的算法利用了古老的分割开和控制的递归策略来解决问题：挑一个元素作为“主元”、把其余的元素分成“大的”和“小的”两堆(当和主元比较时)、再在每一堆中重复这一过程。尽管可能要做受到严厉责备的做完全部N(N-1)/2 次的比较(特别是，如果你把主元作为早已按大小分类好的表列的第一个元素的话！)，快速分类法运行的平均次数具有O(Nlog(N)) 的有效性，其优美的简洁性使之成为计算复杂性的著名的例子。

8. 快速Fourier变换
1965年，IBM的T. J. Watson研究中心的James Cooley以及普林斯顿大学和AT＆T贝尔实验室的John Tukey向公众透露了快速Fourier变换(方法)(FFT)。应用数学中意义最深远的算法，无疑是使信号处理实现突破性进展的FFT。其基本思想要追溯到Gauss(他需要计算小行星的轨道)，但是Cooley—Tukey的论文弄清楚了Fourier变换计算起来有多容易。就像快速分类法一样，FFT有赖于用分割开和控制的策略，把表面上令人讨厌的O(N*N) 降到令人满意的O(Nlog(N)) 。但是不像快速分类法，其执行(初一看)是非直观的而且不那么直接。其本身就给计算机科学一种推动力去研究计算问题和算法的固有复杂性。

9. 整数关系侦查算法
1977年，BrighamYoung大学的Helaman Ferguson 和Rodney Forcade提出了整数关系侦查算法。这是一个古老的问题：给定—组实数，例如说x(1),x(2),…,x(n) ，是否存在整数a(1),a(2),..,a(n) （不全为零），使得
a(1)x(1)+a(2)x(2)+…+a(n)x(n)=0
对于n=2 ，历史悠久的欧几里得算法能做这项工作、计算x(1)/x(2) 的连分数展开中的各项。如果x(1)/x(2) 是有理数，展开会终止，在适当展开后就给出了“最小的”整数a(1)和a(2) 。欧几里得算法不终止——或者如果你只是简单地由于厌倦计算——那么展开的过程至少提供了最小整数关系的大小的下界。Ferguson和Forcade的推广更有威力，尽管这种推广更难于执行(和理解)。例如，他们的侦查算法被用来求得逻辑斯谛(logistic)映射的第三和第四个分歧点，b(3)=3.544090 和 b(4)=3.564407所满足的多项式的精确系数。(后者是120 阶的多项式；它的最大的系数是257^30 。)已证明该算法在简化量子场论中的Feynman图的计算中是有用的。

10. 快速多极算法
1987年，耶鲁大学的Leslie Greengard 和Vladimir Rokhlin发明了快速多极算法。该算法克服了N体模拟中最令人头疼的困难之一：经由引力或静电力相互作用的N个粒子运动的精确计算(想象一下银河系中的星体，或者蛋白质中的原于)看来需要O(N*N) 的计算量——比较每一对质点需要一次计算。该算法利用多极展开(净电荷或质量、偶极矩、四矩，等等)来近似遥远的一组质点对当地一组质点的影响。空间的层次分解用来确定当距离增大时，比以往任何时候都更大的质点组。快速多极算法的一个明显优点是具有严格的误差估计，这是许多算法所缺少的性质。

一般筛法，即埃拉托斯特尼筛法复杂度为O((nlogn)(loglogn))

利用积性函数的优化可以达到O(n)

以下是转载（自http://www.cnblogs.com/suno/articles/1064368.html）

bool notp[mr];//素数判定

__int64 pr[670000],pn,ans;//pr存放素数,pn当前素数个数。



void getprime()

{

    pn=0;

    memset(notp,0,sizeof(notp));

for(int i=2;i<mr;i++)

{

if(!notp[i])pr[pn++]=i;

for(int j=0;j<pn && pr[j]*i<mr;j++)

{

            notp[pr[j]*i]=1;

if(i%pr[j]==0)break;

        }

    }

}

 

利用了每个合数必有一个最小素因子。

每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。

代码中体现在：

if(i%pr[j]==0)break;

pr数组中的素数是递增的,当i能整除pr[j]，那么i*pr[j+1]这个合数肯定被pr[j]乘以某个数筛掉。

因为i中含有pr[j],pr[j]比pr[j+1]小。接下去的素数同理。所以不用筛下去了。

在满足i%pr[j]==0这个条件之前以及第一次满足改条件时,pr[j]必定是pr[j]*i的最小因子。

n个作业要在由两台机器M1和M2组成的流水线上完成加工. 每个作业i必须先在M1上然后在M2上加工, 时间分别为ai和bi

确定这n个作业的加工顺序, 使得从第一个任务开始在M1上加工到最后一个任务在M2上加工完成的总时间尽量小

Johnson算法.
设N1为a<b的作业集合, N2为a>=b的作业集合, 将N1的作业按a非减序排序, N2中的作业按照b非增序排序, 则N1作业接N2作业构成最优顺序.(证明略)

for 所有的组k

for v=V..0

for 所有的i属于组k

f[v]=max{f[v],f[v-c[i]]+w[i]}

二分图的构建：一定要分成两个互不相交的集合

判断二分图：染色法

最大匹配：匈牙利算法

最优匹配：KM算法

最大匹配数＝最小点覆盖数

V：点集  M：最大匹配或最小点覆盖  U：最大独立集

关系：|M|=|V|-|U|

求多元最短路

选图里任意一个点用bellman-ford求出到其它所有点的最短路，h[i]表示该点到i的最短路值

修改边权，w[u,v]＝w[u,v]+h[u]-h[v]，保证所有边为非负的

再做V次dijkstra，时间复杂度为O(V^2logV+VE)

两个割点之间不一定是桥

桥两边不一定是割点，若不是割点肯定是“叶子节点”

没有割点<=>双连通

没有割点肯定没有桥，但没有桥不一定没有割点

计数排序:   

T[i]表示小于等于数值i出现的次数。在原序列中从右往左扫描，当前数值为k，则把该数直接放在新数组的第T[k]位，然后把T[K]减一，很显然这样的排序是稳定的。

对于数值很大的情况：

例如把一个8位数分成四段两位的数，从小的开始直接用计数排序，一共排4次，当大的位置不同时显然是正确的，当大的位置不同时，由于计数排序是稳定的，所以小的位置一定满足的。

一个序列有n!种情况,基于交换的排序,交换k次可以判断2^k种情况

则2^k>=n!  ->  log(2^k)>=log n!  ->  k>=nlogn

所以基于交换的排序时间复杂度最好只能是O(nlogn)

稳定的排序:冒泡排序、插入排序、选择排序、归并排序

一个链表的形式,每个数有个层次

一层的只能跳到相邻的一个,两层的可以跳到相邻的一个和最近的一个两层的,三层的......

每个数的层次是random的(一层、二层、三层....按一定的比例关系)

查找时从高层开始找,若找过了就降一层

插入和删除就和普通的链表一样

o----------------------------->o

o------->o------>o----------->o

o-->o-->o-->o-->o-->o-->o-->o

静态二叉树定是离线算法

对于离线算法,可以打开文件两次

先把树建出来,用完全二叉树记录(中序遍历放数),满足二叉排序树的性质,每次插入元素就做个标记,删除元素就去掉标记,查找是第几大就直接看子树的打标记数.

并查集满足等价关系

等价关系:自反,对称,传递

Tarjan算法(需要用到并查集)

深度优先遍历,正在处理的点是指向集合是自己,处理完的点指向集合为父亲,处理完后再看它是否有询问,询问的对方点一定是处理完的点,若没处理完,则等到下次再问.若处理完,则合并,并且路径压缩.

LCA问题转换成RMP问题:

按层次标号,再深度优先遍历,得到遍历序列(每个点正在处理或处理完都需打印),则LCA问题就转换成了RMP问题.

正负1RMP问题转换成LCA问题:

该序列的任何相邻数一定相差1,那么+1表示往下走一步(加一个新的儿子),-1表示往上走一步(回到父亲).当然在首尾要补数保证第一个和最后一个数是最小值.最后就可构建一棵树,这种RMP问题的询问就可以转换到这棵树上的LCA问题的询问.

f[i,j]=min{f[i,k]+f[k+1,j]}+w[i,j]

用s[i,j]=k 表示决策

则s[i,j-1]<=s[i,j]<=s[i+1,j] , s[i+1,j]<=s[i+1,j+1]<=s[i+2,j+1] ...... (该结论很显然,就不证明了)

所以对于相同长度的j-i,决策总共是O(n),所有长度为j-i状态为O(n),总是件复杂度为O(n^2)

当出现类型于f[i,j]=min{f[i,k]+f[k+1,j]}+w[i,j]的DP,可以先用三方把决策s[i,j]用二维表打出来,如果行和列都是递增的,那么就可以用四边形不等式优化.

问题:一个序列,多次询问某段区间的最大值

f[i,k] 表示从第i个开始2^k个数的最大值

则f[i,k]=max{f[i,k-1],f[i+1,k-1]} 

询问(i,j),则返回max{f[i,k],f[j-2^k,k]} (取最大的k使2^k<=j-i)

预处理 O(nlogn)  询问 O(1)

一个图上A到B的最优路径一定在一棵最小生成树上(最优路径：最大边最小的路径)

最小生成树一定是瓶颈生成树,瓶颈生成树不一定是最小生成树

瓶颈生成树算法:

1.最小生成树

2.二分最大边,判断是否连通 O(ElogE)

由于KM的过程是每次都做一次匈牙利中的"增广操作",没有增广路就修改顶标值标,直到找到完备匹配.

那么这个二分图首先必须是存在完备匹配的.不过这样还不一定能求出最优匹配,因为最优匹配不一定是最大匹配.

如果这个二分图两个集合的任意两个点之间都有边的话,那肯定可以保证正确性,但是这样KM就很有局限性了.

我们不妨自行地加上若干条边和若干个点(加点为了使两个集合的点数相等)使这个二分图变为"完全的".

每个新加的边的权值都赋为0,这样就能用KM算法解决所有二分图的最优匹配问题.

把第i种物品换成n[i]件01背包中的物品，则得到了物品数为Σn[i]的01背包问题，直接求解，复杂度仍然是O(V*Σn[i])。

方法：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。