六、1959-61 计算矩阵特征值的QR算法
[1959–61: J.G.F. Francis of Ferranti Ltd, London, finds a stable method for computing eigenvalues, known as the QR algorithm.]
1959-61:伦敦费伦蒂有限公司的J.G.F. Francis,找到了一种稳定的特征值的计算方法,这就是著名的QR算法。
这也是一个和线性代数有关的算法,学过线性代数的应该记得“矩阵的特征值”,计算特征值是矩阵计算的最核心内容之一,传统的求解方案涉及到高次方程求根,当问题规模大的时候十分困难。
QR算法把矩阵分解成一个正交矩阵(希望读此文的你,知道什么是正交矩阵。:D。)与一个上三角矩阵的积,和前面提到的Krylov 方法类似,这又是一个迭代算法,它把复杂的高次方程求根问题化简为阶段性的易于计算的子步骤,使得用计算机求解大规模矩阵特征值成为可能。这个算法的作者是来自英国伦敦的J.G.F. Francis。
七、1962 快速排序算法
[1962: Tony Hoare of Elliott Brothers, Ltd., London, presents Quicksort.]
1962年:伦敦的,托尼埃利奥特兄弟有限公司,霍尔提出了快速排序。
快速排序算法作为排序算法中的经典算法,它被应用的影子随处可见。快速排序算法最早由Tony Hoare爵士设计,它的基本思想是将待排序列分为两半,左边的一半总是“小的”,右边的一半总是“大的”,这一过程不断递归持续下去,直到整个序列有序。
说起这位Tony Hoare爵士,快速排序算法其实只是他不经意间的小小发现而已,他对于计算机贡献主要包括形式化方法理论,以及ALGOL60 编程语言的发明等,他也因这些成就获得1980 年图灵奖。快速排序的平均时间复杂度仅仅为O(Nlog(N)),相比于普通选择排序和冒泡排序等而言,实在是历史性的创举。
八、1965 快速傅立叶变换
[1965: James Cooley of the IBM T.J. Watson Research Center and John Tukey of Princeton University and AT&T Bell Laboratories unveil the fast Fourier transform.]
1965年:IBM 华生研究院的James Cooley,和普林斯顿大学的John Tukey,AT&T贝尔实验室共同推出了快速傅立叶变换。
快速傅立叶算法是离散傅立叶算法(这可是数字信号处理的基石)的一种快速算法,其时间复杂度仅为O(Nlog(N));比时间效率更为重要的是,快速傅立叶算法非常容易用硬件实现,因此它在电子技术领域得到极其广泛的应用。日后,我会在我的经典算法研究系列,着重阐述此算法。
九、1977 整数关系探测算法
[1977: Helaman Ferguson and Rodney Forcade of Brigham Young University advance an integer relation detection algorithm.]
1977年:Helaman Ferguson和 伯明翰大学的Rodney Forcade,提出了Forcade检测算法的整数关系。
整数关系探测是个古老的问题,其历史甚至可以追溯到欧几里德的时代。具体的说:给定—组实数X1,X2,...,Xn,是否存在不全为零的整数a1,a2,...an,使得:a1 x 1 +a2 x2 + . . . + an x n =0?这一年BrighamYoung大学的Helaman Ferguson 和Rodney Forcade解决了这一问题。该算法应用于“简化量子场论中的Feynman图的计算”。ok,它并不要你懂,了解即可。:D。
十、1987 快速多极算法
[1987: Leslie Greengard and Vladimir Rokhlin of Yale University invent the fast multipole algorithm.]
1987年:莱斯利的Greengard,和耶鲁大学的Rokhlin发明了快速多极算法。
此快速多极算法用来计算“经由引力或静电力相互作用的N 个粒子运动的精确计算——例如银河系中的星体,或者蛋白质中的原子间的相互作用”。