参考资料：TheBestofthe20thCentury:编者为Top10Algorithms点名。巴里·A·西普拉(BarryA.Cipra)。地址：http://www.uta.edu/faculty/rcli/TopTen/topten.pdf。发明十大算法的几位算法大师1.1946年蒙特卡洛法【1946年：JohnvonNeumann、StanUlam和NickMetropolis，都在LosAlamos科学实验室，炮制出Metropolis算法，又称蒙特卡洛法.]1946年，美国拉斯阿莫斯国家实验室的三位科学家JohnvonNeumann、StanUlam和NickMetropolis共同发明了它，称为蒙特卡洛法。它的具体定义是：在正方形上画一个边长为一米的正方形，在正方形里面用粉笔随意画一个不规则的形状。现在要算这个不规则图形的面积，那柱子怎么算呢？蒙特卡洛（MonteCarlo）Carlo）方法告诉我们将N（N是一个大的自然数）颗黄豆均匀地撒到正方形里，然后统计这个不规则的几何形状里面有多少颗黄豆，比如有M颗，那么，这个奇怪形状的面积大约是M/N，N越大，计算出来的值就越准确。这里我们要假设bean都在同一个平面上，互不重叠。（撒大豆只是个比喻。）可以用蒙特卡洛法来近似圆周率：让计算机一次随机产生两个0到1之间的数，看这两个实数是否在单位圆内。生成一系列随机点，统计单位圆内的点数和总点数。内切圆面积与正方形面积之比为PI:4，PI为圆之比。（感谢网友qilihe指出：S内切圆：S正=PI：4，详见下方第99条评论，16日修正），当获得更多随机点时（但即使选择10当有9个随机点时，结果只与pi的前4位一致），结果越接近pi。2.1947年的单纯形法[1947年：RAND公司的GeorgeDantzig创建了线性规划的单纯形法。]1947年，RAND公司的GeorgeDantzig发明了单纯形法。单纯形法从此成为线性规划学科的重要基石。所谓线性规划，简单地说，就是给定一组线性（所有变量都是一个幂）约束条件（如a1*x1+b1*x2+c1*x3>0），求给定的目标函数极值。这么说似乎太抽象了，但现实中可借鉴的例子并不少见——例如，对于一个公司来说，其可投入生产的人力和物力是有限的（“线性约束”），而公司的目标是利润最大化（“目标函数取最大值”），看，线性规划不是抽象的！线性规划作为运筹学的一部分，已成为管理科学领域的重要工具。Dantzig提出的单纯形法是求解类似线性规划问题的一种极其有效的方法。3.1950Krylov子空间迭代方法[1950年：国家标准局数值分析研究所的MagnusHestenes、EduardStiefel和CorneliusLanczos发起了Krylov子空间迭代方法的开发。]数值分析，MagnusHestenes，EduardStiefel和CorneliusLanczos，发明了Krylov子空间迭代法。Krylov子空间迭代法用于求解形式为Ax=b的方程。A是一个n*n矩阵。当n足够大时，直接计算变得非常困难，Krylov方法巧妙地将其改为Kxi+1=Kxi+b-Axi迭代形式求解。这里的K（源自俄罗斯作者姓氏NikolaiKrylov的首字母）是一个接近A的构造矩阵，迭代算法的美妙之处在于它将复杂的问题简化为阶段性且易于计算的子步骤。4.1951矩阵计算的分解方法[1951:AlstonHouseholderofOakRidgeNationalLaboratory将矩阵计算的分解方法形式化。]1951年，AlstonOakRidgeNationalLaboratory的AlstonHouseholder提出了矩阵计算的分解方法。该算法证明了任何矩阵都可以分解为三角矩阵、对角矩阵、正交矩阵和其他特殊形式的矩阵。该算法的意义使得开发灵活的矩阵计算软件包成为可能。5.1957OptimizingFortranCompiler[1957：JohnBackus在IBM领导一个团队开发Fortran优化编译器。]1957：JohnBackus领导IBM团队的开发并创建了Fortran优化编译器。Fortran，又译为传福音，是两个词的组合，FormulaTranslation，意思是“公式翻译”。它是世界上第一个被正式采用并流传至今的高级编程语言。这种语言现在已经发展到Fortran2008，并且广为人知。6.1959-61QRalgorithmforcomputingmatrixeigenvalues[1959-61:J.G.F.伦敦FerrantiLtd的Francis找到了一种稳定的计算特征值的方法，称为QR算法。]J.G.F.Francis找到了一种稳定的特征值计算方法，这就是著名的QR算法。这也是线性代数相关的算法。学过线性代数的应该记得“矩阵的特征值”。计算特征值是矩阵计算的核心内容之一。传统的解决方案涉及寻找高阶方程的根。当问题规模很大时就非常困难。QR算法将矩阵分解为正交矩阵（希望看到这篇文章的你知道什么是正交矩阵。:D。)与上三角矩阵，类似于上面提到的Krylov方法，这是另一种迭代算法，它将复杂的高阶方程的求根问题简化为易于分步计算的子步骤，从而使计算机可以求解大规模矩阵的特征值。该算法的作者是J.G.F.来自英国伦敦的弗朗西斯。七、1962年快速排序算法[1962年：伦敦ElliottBrothers有限公司的TonyHoare提出Quicksort。]1962年：伦敦TonyElliottBrothers有限公司的Hall提出快速排序。哈哈，恭喜，终于看到一个你可能第一个熟悉的算法了~。快速排序算法作为排序算法中的经典算法，随处可见。快速排序算法首先由TonyHoare爵士设计。它的基本思想是将待排序的列分成两半。左半边总是“小”，右半边总是“大”。这个过程一直递归下去，直到整个序列有序。说起TonyHoare爵士，快速排序算法其实只是他无意中的一个小发现。他对计算机的贡献主要包括形式方法理论和ALGOL60程序设计语言的发明。由于这些成就，他还获得了1980年人物奖。精神奖励。快速排序的平均时间复杂度仅为O(Nlog(N))，相对于普通的选择排序和冒泡排序是历史性的创新。8.快速傅立叶变换1965年JohnTukey与AT&T贝尔实验室共同发明了快速傅立叶变换。快速傅里叶算法是离散傅里叶算法（数字信号处理的基石）的快速算法，其时间复杂度仅为O(Nlog(N))；比时间效率更重要的是，快速傅里叶算法很容易用硬件实现，因此在电子技术领域得到广泛应用。以后我会在我的经典算法研究系列中重点介绍这个算法。9.1977Integerrelationdetectionalgorithm[1977:HelamanFergusonandRodneyForcadeofBrighamYoungUniversityadvancedanintegerrelationdetectionalgorithm.]1977:HelamanFergusonandRodneyForcadeofBirminghamUniversityofBirmingham提出整数关系的Forcade检测算法。整数关系检测是一个老问题，它的历史甚至可以追溯到欧几里得时代。具体来说：给定一组实数X1，X2，...，Xn，是否存在不全为零的整数a1，a2，...an，使得：a1x1+a2x2+。..+xn=0?今年，杨百翰大学的HelamanFerguson和RodneyForcade解决了这个问题。该算法被应用于“简化量子场论中费曼图的计算”。好吧，它不需要你理解它，理解它就可以了。:D.10.1987FastMultipoleAlgorithm[1987:LeslieGreengardandVladimirRokhlinofYaleUniversity发明快速多极算法]1987:GreengardandRokhlinofYaleUniversity发明快速多极算法。这种快速多极算法用于计算“精确计算通过引力或静电力相互作用的N个粒子的运动——例如银河系中恒星之间的相互作用，或蛋白质中原子之间的相互作用”。好吧，明白了。如果您有任何意见和问题，请在博客中留言或评论。原文地址：JULY
