20世纪计算机领域十大算法

文章来自微信公众号“科文路”，欢迎关注、互动。转发须注明出处。

文章内容基于The Best of the 20th Century: Editors Name Top 10 Algorithms

谈及计算机时代的十大算法，很难说某一个算法是“最佳”的。于是这篇文章称其内容为CiSE top-10 list，意为《Computing in Science & Engineering》评选的十佳算法。

需要注意的是，下文想特指这些算法在计算机领域的影响或应用。

1 The Monte Carlo method

1946, John von Neumann, Stan Ulam, and Nick Metropolis, all at the Los Alamos Scientific Laboratory

蒙特·卡罗方法，也称统计模拟方法，由[冯·诺伊曼]以赌城命名，是一种以概率统计理论为指导的一类非常重要的数值计算方法。

2 The simplex method for linear programming

1947, George Dantzig, at the RAND Corporation

单纯形法，学过 Optimization 的同学应该不陌生。它是求解线性规划问题最常用、最有效的算法之一。

3 Krylov subspace iteration methods

1950, Magnus Hestenes, Eduard Stiefel, and Cornelius Lanczos, all from the Institute for Numerical Analysis
at the National Bureau of Standards

子空间迭代法，该方法用以简化大型矩阵的某些计算，如求解大型、稀疏矩阵特征值问题。

4 The decompositional approach to matrix computations

1951, Alston Householder of Oak Ridge National Laboratory

矩阵分解，这里是指将矩阵分解为三角、对角、正交等矩阵的方法，（线代手算噩梦😂）。这些分解理论促进了矩阵软件包的开发，也助力了“舍入”误差分析。

5 The Fortran optimizing compiler

1957, John Backus’ team

优化的 Fortran 编译器，Backus 带领团队不断优化 Fortran 编译器，使其以计算速度惊人。

注，Fortran 取自 Formula Translation，搞高性能计算的人绕不开这门语言。

6 The QR algorithm

1959-61, J.G.F. Francis of Ferranti Ltd.

QR分解，耳熟能详的求矩阵特征值的方法。

7 Quicksort

1962, Tony Hoare of Elliott Brothers, Ltd.

快速排序，面试笔试常客。理论上，排序一个列表至少需要 O(N log N) 次比较。快排将理论拉近现实，实现了该 O(N log N) 的平均时间复杂度。

8 Fast Fourier transform

1965, James Cooley of the IBM T.J. Watson Research Center and John Tukey of Princeton University and AT&T Bell Laboratories

快速傅里叶变换。FFT依赖于分治策略，将表面上的O(N^2)开销减少为O(N log N)。

9 Integer relation detection algorithm

1977, Helaman Ferguson and Rodney Forcade of Brigham Young University

整数关系是指对于某实数数组 $x_1, x_2, \cdots, x_n$，存在不全为 0 的整数数组 $a_1, a_2, \cdots, a_n$，使得下式成立，

$$
a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}=0
$$

整数关系探测算法，用以在一组已知精度的实数中寻找他们的整数关系。

它是零误差计算的算法基础。

它也被证明在简化量子场论中的 Feynman 图的计算方面是有用的。

10 Fast multipole method

1987, Leslie Greengard and Vladimir Rokhlin of Yale University

快速多极子算法，FMM，在很多物理系统中，该方法可以降低涉及到特定密集矩阵类型的矩阵-向量乘法计算的复杂度。

The FMM algorithm reduces the complexity of matrix-vector multiplication involving a certain type of dense matrix which can arise out of many physical systems. Fast multipole method

比如去处理银河系中的星体、蛋白质中的原子间的相互作用。

同时，该方法具备很多其他方法没有的、严格的误差估计。

看不懂，没学过，很厉害的样子。

As Sullivan writes in the introduction to the top-10 list, “The new century is not going to be very restful for us, but it is not going to be dull either!”

都看到这儿了，不如关注每日推送的“科文路”、互动起来~