中国科普博览-亚博安卓

数学技术之算法概论篇（3）

3.算法中的问题及其描述

对一个问题的求解可以选用多种不同的模型、方法和算法，难易差异极大。由于机器字长的限制和存贮空间的有限性，不同的模型由于误差的存在，往往使计算的结果存在很大的差异。若执行的结果与精确解之间的误差很大的话，势必会影响与之相关的数据的精确度，这就引出了算法稳定性、收敛性和复杂度等诸多问题。下面，对上述问题进行一些简单介绍。

①算法的稳定性

对一个数值型算法，计算过程中已有的各类误差会继续积累并向前发展。若输入数据的误差在计算过程中迅速增长而得不到控制，则称该算法是不稳定的，否则是算法稳定的。所以，算法稳定性说的是计算过程中的误差（含舍入误差、截断误差等）的敏感性。
算法的稳定性是指算法对于计算过程中的误差不敏感，即稳定的算法能得到原问题相邻问题的精确解。一个算法计算得到的近似解可以看作原计算问题中的参数经适当扰动后的准确解，若扰动是微小的，就说这个算法是数值稳定的，否则就说算法是不稳定的。
对一个非数值型算法，如排序算法的稳定性其意义和数值型算法不同，这里算法稳定性意思是说原本键值一样的元素排序后相对位置不变。对一个复杂类型的数组排序，而排序的键实际上只是这个元素中的一个属性，对于一个简单类型，数字值就是其全部意义，即使交换了也看不出什么不同。但是对于复杂的类型，交换的话可能就会使原本不应该交换的元素交换了。比如，一个“学生”数组，按照年龄排序，“学生”这个对象不仅含有“年龄”，还有其他很多属性，稳定的排序会保证比较时，如果两个学生年龄相同，一定不交换。

②算法的收敛性

算法的收敛性和稳定性不是一个层次的概念，它只在部分算法中出现，比如迭代求解，迭代中的收敛指经过有限步骤的迭代计算可以得到一个稳定的解。但是这个解是不是原问题的解，要看问题的病态性了。如果问题是病态的，则很有可能不是准确的解。
算法的数值稳定性的判别是和(舍入)误差分析密切相关联。对代数求解过程的舍入误差作深入细致的分析，计算结果的精度不但依赖于所用的算法，而且也和问题是良态或病态有关。一个计算问题，如果其中的参数(如线性代数方程组的系数，自由项)的微小扰动只对解的精度产生不大的影响，便说这个计算问题是良态的，否则便称为病态的。

③算法的复杂度

算法的复杂度含算法时间复杂度和空间复杂度，它们合称为算法复杂度。
算法复杂度理论是理论计算机科学的分支学科，使用数学方法对计算中所需的各种资源的耗费作定量的分析，并研究各类问题之间在计算复杂程度上的相互关系和基本性质，是算法分析的理论基础。其他资源亦可考虑，例如在并行计算中，需要多少并行处理器才能解决问题等。
时间复杂度是某个算法的时间耗费，它是该算法所求解问题规模的函数。算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关，是衡量一个算法优劣的重要参数。时间复杂度越小，说明该算法效率越高，算法越有价值。
渐近时间复杂度是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。
空间复杂度是某个算法的空间耗费，它也是该算法所求解问题规模的函数，是算法优劣的重要度量指标之一。空间复杂度越小，算法越好。假设用一个图灵机来解决某一类问题，设有x个字（word）属于这个问题，把x放入这个图灵机的输入端，空间复杂度就是这个图灵机为解决此问题所需要的工作带格子数总量。
算法复杂度按求解问题规模数量级n递增排列依次为：常数阶o(1)、对数阶o(log₂n)、线性阶o(n)、线性对数阶o(nlog₂n)、平方阶o(n²)、立方阶o(n³)、……k次方阶o(n^k)、指数阶o(2ⁿ)等。
复杂度理论和可计算性理论不同，可计算性理论的重心在于问题能否解决，不管需要多少资源，而复杂性理论作为计算理论的分支，某种程度上被认为和算法理论是一种“矛”与“盾”的关系，即算法复杂度理论专注于设计有效的算法，并可依此对同一问题的不同算法进行比较，而可计算性理论专注于理解为什么对于某类问题不存在有效的算法。

4.十大算法

算法对我们极其重要，一些模不着、看不见的算法正在掌控着我们的数字世界，现在是一个“算法为王”的时代，已经到了我们必须透彻地了解算法的时候了。软件正在统治世界，而软件的核心是算法。算法千千万万，又有哪些算法属于 “皇冠上的珍珠” 呢？下面分别列出从不同角度、不同时段、不同领域得到的十大算法，供参考。
显然，不同领域、不同时代的人，对什么是“十大算法”自然会有不同看法和不同的选择，不可能统一，也没有必要统一。应该说，受时间、经验、领域和参选人数等诸多限制，入选的十大算法，不一定个个都是最优秀的；受条件和个数所限，没有入选的有些算法，也不能说是不好的；有些算法在不同选法中出现，也是自然的；每类算法都选成“十大”，确有凑数之嫌，不无道理，但10是最小的两位数，选10也有一定的道理。
下面在互联网上分别从发展过程、研究方向和领域、考虑问题的重点、所处时间区间、评价优劣的标准和评选方法不同等各个不同方面的考虑给出不同类别的十大算法并对其进行一些简要的介绍，供大家参考。稍后，对其中一项重要的算法，再进行较详细的一些介绍。

① 二十世纪的十大算法

21世纪初，美国物理学会(american institute of physics)和ieee计算机社团(ieee computer society)的联合刊物《科学与工程中的计算》发表了由田纳西大学的jack dongarra和橡树岭国家实验室的francis sullivan联名撰写的“20世纪十大算法”一文，该文“试图整理出在20世纪对科学和工程领域的发展产生最大影响力的十大算法”。作者苦于“任何选择都将充满争议，因为实在是没有最好的算法”，他们只好用编年顺序依次列出了这十项算法领域人类智慧的巅峰之作——给出了一份没有排名的算法排行榜。这里带领网友走马观花，一同回顾一下二十世纪算法界的发展历程，并对这些算法进行一些简短介绍。
（1）1946蒙特卡罗方法
1946年：蒙特卡罗方法，是一类基于“随机数”的计算方法。由于该方法应用域多面广，有数十种不同的名称或叫法，如蒙特卡罗计算、统计试验方法、随机模拟方法等；又由于该方法特点显著、能和其他学科与方法广泛深入结合，因而有了众多的分支，如拟蒙特卡罗方法、多群蒙特卡罗方法、动态蒙特卡罗方法、量子蒙特卡罗方法、变分蒙特卡罗方法、马氏链蒙特卡罗方法和并行蒙特卡罗方法等。
蒙特卡罗方法以概率和统计理论为基础，将所求解的问题同概率模型相联系，用计算机上产生的随机数实现统计模拟或抽样，以获得问题的近似解。为象征性地表明这一方法的概率统计特征，借用欧洲赌城蒙特卡罗(monte carlo)命名，由s.m.乌拉姆和j.冯 诺伊曼在20世纪40年代为研制核武器而首先提出。它的基本思想是，为了求解数学、物理、工程技术以及管理等方面的问题，首先建立一个概率模型或随机过程，使它们的参数，如概率分布或数学期望等成为问题的解，然后通过对模型或过程的观察或抽样试验来计算所求参数的统计特征，并用算术平均值作为所求解的近似值。
蒙特卡罗方法有很强的适应性，问题的几何形状的复杂性对它的影响不大。该方法的收敛性是指概率意义下的收敛，因此问题维数的增加不会影响它的收敛速度，而且存贮单元也很省，这些是用该方法处理大型复杂问题时的优势。因此，随着电子计算机的发展和科学技术问题的日趋复杂，蒙特卡罗方法的应用也越来越广泛。它不仅较好地解决了多重积分计算、微分方程求解、积分方程求解、特征值计算和非线性方程组求解等高难度和复杂的数学计算问题，而且在统计物理、核物理、真空技术、系统科学、信息科学、公用事业、地质、医学，可靠性及计算机科学等广泛的领域都得到成功的应用。
（2）1947单纯形法
1947年：单纯形法，是由“预测未来”的兰德公司的grorge dantzig发明的，成为线性规划学科的重要基石。
所谓线性规划，简单的说，就是在给定一组线性约束条件（如a₁*x₁ a₂*x₂ a₃*x₃>0)，求一个给定的目标函数的极值。在现实中能派上用场的例子并不罕见——比如对于一个公司而言，其能够投入生产的人力物力有限（“线性约束条件”），而公司的目标是利润最大化（“目标函数取大值”），所以线性规划并不抽象。线性规划作为运筹学研究的一部分，成为管理科学领域的一种重要工具，dantzig提出的单纯形法便是求解这类线性规划问题的一个极其有效的算法。
（3）1950 krylov子空间迭代法
1950年：美国国家标准局数值分析研究所hestenes，lanczos，发明了krylov子空间迭代法。
krylov子空间迭代法是用来求解形如ax=b的线代数方程组，a是一个n*n的矩阵，当n很大时，直接计算非常困难，而krylov方法则巧妙地将其变为kx_{i 1}=kx_i b-ax_i的迭代形式来求解。这里的k(来源于作者俄国人nikolai krylov姓氏的首字母)是一个构造出来的接近于a的矩阵，而迭代形式的算法的妙处在于，它将复杂问题化简为阶段性的易于计算的子步骤。
（4）1951矩阵计算的分解方法
1951年：由阿尔斯通橡树岭国家实验室的alston householder提出矩阵计算的分解方法。该算法证明任何矩阵都可以分解为三角、对角、正交和其他特殊形式的矩阵，其重大意义使得开发灵活的矩阵计算软件包成为可能。
（5）1957优化的fortran编译器
1957年：fortran编译器，由fortran之父——john backus发明的人类历史上第一个计算机高级语言。
说实话，在这份学术气息无比浓郁的榜单里突然冒出一个编译器如此工程化的东西实在让人有“关公战秦琼”的感觉。不过换个角度想想，fortran这一门几乎为科学计算度身定制的编程语言，对于科学家（尤其是数学家，物理学家）们实在是太重要了，简直是他们形影不离的一把瑞士军刀，这也难怪他们纷纷抢着要把票投给了它。要知道，fortran是第一个能将数学公式转化为计算机程序的高级语言，它的诞生使得科学家们真正开始利用计算机作为计算工具为他们的研究服务，这是计算机应用技术的一个里程碑级别的贡献。
（6）1959-61计算矩阵特征值的qr算法
1959-61年：矩阵特征值的qr算法，也是一个和线性代数有关的算法，发明者为来自英国伦敦的j.g.f.francis。
计算特征值是矩阵计算的最核心内容之一，传统的求解方案涉及到高次方程求根，当问题规模大的时候十分困难。qr算法把矩阵分解成一个正交矩阵与一个上三角矩阵的积，和前面提到的krylov方法类似，又是一个迭代算法，它把复杂的高次方程求根问题化简为阶段性的易于计算的子步骤，使得用计算机求解大规模矩阵特征值成为可能。
（7）1962快速排序算法
1962年：快速排序算法，最早由tony hoare爵士设计，它的基本思想是将待排序数序列分为两半，左边的一半总是“小的”，右边的一半总是“大的”，这一过程不断递归持续下去，直到整个序列有序。说起这位tony hoare爵士，快速排序算法其实只是他不经意间的小小发现而已，他对于计算机贡献主要包括形式化方法理论，以及algol 60编程语言的发明等，他也因这些成就获得1980年图灵奖。
快速排序的平均时间复杂度为o(nlog(n))，相比于普通选择排序和冒泡排序等而言，实在是历史性的创举。
（8）1965快速傅立叶变换
1965年：快速傅立叶变换fft，由ibm华生研究院的james cooley和普林斯顿大学的john tukey共同提出。
如果要评选对我们的日常生活影响最大的算法，快速傅立叶变换算法应该是当仁不让的冠军——每天当拿起话筒，打开手机，听mp3，看dvd，用dc拍照——毫不夸张的说，哪里有数字信号处理，哪里就有快速傅立叶变换。快速傅立叶算法是离散傅立叶算法的一种快速算法，时间复杂度仅为o(nlog(n))；比时间效率更为重要的是，快速傅立叶算法非常容易用硬件实现，因此它在电子技术领域得到极其广泛的应用。
（9）1977整数关系探测算法
1977年：整数关系探测算法，由brigham young大学的helaman ferguson和rodney forcade解决。
整数关系探测是个古老的问题，其历史甚至可以追溯到欧几里德的时代。具体的说：给定—组实数x₁，x₂，...，x_n，是否存在不全为零的整数a₁，a₂，...a_n，使得:a₁x₁ a₂x₂ ... a_nx_n＝0，该算法可用于简化量子场论中的feynman图的计算。
（10）1987快速多极算法
1987年：快速多极算法，耶鲁大学leslie greengard和vladimir rokhlin提出的快速多极算法用来计算经由引力或静电力相互作用的n个粒子运动的精确计算——例如银河系中的星体，或者蛋白质中的原子间的相互作用。
浪花淘尽英雄，这些算法的发明者许多已经驾鹤西去。二十一世纪的前十五年也已经在不知不觉中从我们指尖滑过，不知下一次十大算法评选的盛事何时再有。