【转】张 建中老师谈算法（1）

我要吃章鱼丸子

! U( j' C4 s, F
什么是数学算法？Posted on 2016年1月18日 by 张 建中
9 G$ n) {4 C; v& N7 f
9 }( B5 [& [8 x' N! \$ L4 q& f原文转自中国科普网http://zhangjianzhong.blog.kepu.cn/20160118171409.html
数学技术之算法概论篇（1）1.算法概述

计算机算法是在计算机上有限步内求解某一问题所使用的一组定义明确的规则或对解题步骤的精确描述，通俗点说，就是计算机解题的过程，即以一步接一步的方式详细描述计算机如何将输入转化为所要求的输出的过程，下面简称其为算法。在这个过程中，无论是形成解题公式还是编写程序，都是实施某种算法，前者利用推理实现算法，后者通过计算机操作实现算法。

计算机算法的基本特征可概括为：

①  正确性：对于任意一组输入，包括合理的输入与不合理的输入，总能得到预期的输出；如果一个算法只是对合理的输入才能得到预期的输出，而在异常情况下却无法预料输出的结果，那它就是不正确的；

②  确切性：算法的每一步必须有确切的定义，无二义性；

③  可行性：算法是由一系列具体步骤组成的，每一步都能够准确运行，有确定的执行顺序；

④  有穷性：算法必须保证经有限步运行之后结束，即算法的步骤必须是有限的。在任何情况下，算法都不能陷入无限循环中；

⑤  输  入：算法有一个或多个输入，表示运算对象的初始条件；

⑥ 输  出：算法有一个或多个输出，反映运算的最终结果。

描述算法的方法有多种，常用的有自然语言、结构化流程图、伪代码和PAD图（Problem Analysis Diagram）等，其中最普遍的是流程图。虽然算法与计算机程序密切相关，但二者还是不同的，计算机程序是算法的一个实例，是将算法通过某种计算机语言表达出来的具体形式；同一个算法可以用不同的计算机语言来表达。

对同一个计算问题，不同人会用选用不同的算法，而不同的算法使得计算机的运行效率、解题精度和对计算资源的需求会有一定的差异。在实际问题中遇到的高难度计算问题，有的问题在巨型计算机上用普通算法求解可能要用数天时间，甚至也难以找到可用的解，但用一个好的算法，即使在普通的微机上，只用几分钟就可以找到满意的解。因此，用计算机求解一个实际问题的计算速度和结果满意度不仅仅与计算机设备的水平有关，更取决于求解该问题算法水平的高低和对问题的适应性，由此可见算法的重要性。算法研究的重点随问题的不同而异，主要有算法设计和分析、计算复杂性和新的高效算法设计与研究等。

对一个给定问题的算法要进行设计和分析。算法设计，就是对一个给定问题设计出良好的算法，并研究设计算法的规律及其有关的方法；算法分析，就是对一个给定问题设计出来的算法，利用数学工具，研究该算法对问题的适应性和算法的稳定性、收敛性、复杂性和误差问题等。

评价算法优劣的标准有：

①时间复杂度：同样的问题规模需花费多少时间；

②空间复杂度：同样的问题规模需花费多少空间（主要是内存）；

以上两点越小越好

③稳定性：不会因为输入稍有不同而导致计算结果不稳定的情况发生；

④算法思路是否简单：越简单越容易实现越好，最好有现成软件系统可用。

算法复杂度是对算法在计算机上运行时所需要的计算机资源的度量，需要的时间资源量（如计算所需的步数或反复执行指令的条数）称作时间复杂度，需要的空间资源量（即需占用存储空间的大小）称作空间复杂度，是对算法效率的度量和评价算法优劣的重要依据。这些量应该集中反映算法中所采用方法的效率，而从运行该算法的实际计算机中抽象出来。换句话说，这些量应只依赖于算法要解的问题的规模、算法的输入、输出和算法本身。

计算机和数学技术的快速发展，近些年来出现了许多新算法。它们技巧性强，在时间复杂度、空间复杂度和计算精度等方面各占一定优势，应用广泛，效果显著。

算法对我们真有那么重要吗？现在，这些看不见、摸不着的算法正在掌控着我们与数字世界的互动，从谷歌网站上推荐图书、电影和音乐的算法到Facebook网站上推荐朋友的算法，从操纵华尔街股票交易的算法再到各种搜索引擎的算法及好莱坞预测电影票房的算法，算法似乎已无声地渗入到我们的世界并重塑着我们身处的世界。有专家指出：计算机用来做决定的算法正在以“随风潜入夜，润物细无声”的方式，慢慢渗透进我们日常生活的方方面面。这些看不见摸不着的算法正在慢慢掌控着我们与电子世界的相互交流，现在是一个“算法为王”的时代。随着算法开始将其影响力延伸并塑造我们身处的世界，现在已经到了我们必须透彻地了解算法的时候了。

2.计算机里的数及其计算

数学应用、应用数学，数学计算、计算数学，数学技术、技术数学，粗看起来，它们都和数学密切相连，都是以数学为工具，解决现实世界中遇到的各种各样实际中遇到的问题；细分起来，在发展过程、研究方向、考虑问题的重点和评价优劣的标准等方面确有不少差异。但不管怎么说，以数学为思维的方法，研究的工具，把实际问题经抽象处理，构建可用的数学模型，研究其中用到的各类算法，编制成在计算机上可运行的程序，通过计算机上的实际计算和计算结果的分析处理，解决遇到的实际问题，这些都是它们应含有的思想和实际应用中要处理的问题。

说到计算机，就像显微镜对医学、望远镜对天文学一样，是数学应用、数学计算、数学技术中不可缺少的设备，时时、处处都要用到计算机，有的还要用到巨型计算机。计算机使数学原理得以实现，为数学应用开辟了无限广阔的天地；计算机是具体化了的数学，现代数学的实验室，进行现代数学研究和实际应用时必不可少的工具。这里只能挂一漏万，介绍一下计算机上数据的表示、数学运算及其误差和几个简单的算例。

① 计算机里的数据

数据（Data）是信息的载体，是计算机加工处理的对象，描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号集合，它能够被计算机识别、存储和加工处理。它是计算机程序加工的原料，应用程序处理各种各样的数据。计算机里的数据可以是数值型数据，也可以是非数值型数据。数值型数据是一些整数、实数或复数，主要用于工程计算、科学计算和商务处理等；非数值型数据包括字符、文字、图表、图形、图像、语音等。数据元素（Data Element）是数据的基本单位。

计算机中，以位（0或1）表示数据。数据的最小的寻址单位称为字节（通常是八位），机器码指令处理的单位，称作字长。大部分对字长的指令解译，主要以二进制为主，如一个32位的字长，可以表示从0至232-1的无符号整数值，或者表示从-(232-1)至(232-1)有符号整数值。存在着特殊的算术指令，对字长中的位使用不同的解释，以此作为浮点数。

数据类型(Data type)是用来约束数据的解释，有很多种，最简单的就是数字。数据也可以是文字、图像、声音等，可用于科学研究、设计、查证等。在编程语言中，常见的数据类型包括原始类型（如：整数、浮点数或字符）、多元组、记录单元、代数数据类型、抽象数据类型、参考类型、类别以及函数型等。数据类型描述了数值的表示法、解释和结构，并以算法操作，或是物件在内存中的储存区，或者其它储存装置，随不同的计算机语言系统会有所不同。

数据在计算机里的基本运算和操作有如下四类：

1.算术运算：加减乘除等运算；

2.逻辑运算：或、且、非等运算；

3.关系运算：大于、小于、等于、不等于等运算；

4.数据传输：输入、输出、赋值等运算。

② 数值计算

用计算机高级语言研制的程序，大都含有数值计算；因此，在计算机应用中，进行数值计算是其最重要的功能之一。计算机语言中的数值表示及其运算和数学中的数值与运算有所不同，对此要有明确的认识和严格的区分，并在计算机上实施实际计算中给予足够的重视和进行细致的分析。在计算机各种不同的编程语言中，数值计算多采用32位（4字节）的单字长或64位（8字节）的双字长作为一个数存单元，每一个数值都存放在计算机里数存的一个单元中。数值的大小和数值的精度都受到一定限制。

受计算机字长的限制，输入到计算机里的数会有原始误差和舍入误差，经计算得到结果的数含有运算误差、传递误差和累积误差，计算公式进过简化、离散、近似逼近等处理也会出现误差。在计算机亿万次计算过程中，误差的积累和传递是纸上手工计算中无法体会和了解的，两者有很大不同，甚至在数学上成立的恒等式，在计算机上实施计算的过程中也会产生异化而不再成立。

这里将对上述问题及应注意的一些事项进行一些简单扼要介绍。

从我们接受基础教育开始到中学学习结束，接触到的数多是数学中的数，像小学中的自然数、小数、分数，中学时的负数、无理数、实数、复数等等，如53、123.618、2/3、-35.4、√2、3+10i（这里，i= √-1，为虚数单位）等，用来表示一个明确的数；代数中，更是用英文字母表示非常广义的数，如向量、矩阵等。但在计算机上和计算机语言中表示的数和运算，和数学中的数和运算却有所不同，即计算机上计算公式里的运算必须是计算机上可实际执行的运算，参与运算的数是有限小数或整数，并有一定的表示格式。

在计算机内，所有的数均用二进制表示，优点在于表示容易、物理实现简单、节省设备、代数运算简单可靠、逻辑运算方便。在计算机里，除二进制数（用B表示）外、还有八进制数（用O表示）、十进制数（用D表示）、十六进制数（用H表示）和二/十进制数（全名为“二进制编码的十进制数”，用BCD表示）等。

计算机上的数，用二进制的一位数码表示数的符号，称为“数符”，且用“0”表示正数，“1”表示负数。小数点的位置隐含表示，以节省存储空间。隐含的小数点位置有固定和可变两种，分别称为定点数和浮点数。

1.定点数表示法

定点整数：最高二进制的一位数码表示数的符号，小数点位置约定在最低数值位的后面，用于表示整数。

定点小数：最高二进制的一位数码表示数的符号，小数点位置约定在符号位的后面，用于表示绝对值小于1的有限位小数。

2.浮点数表示法

阶符：位于左侧最高位二进制的一位数字，表示阶码的符号；

阶码：表示指数部分，阶码的位数决定数的范围；

数符：二进制的一位数字，表示数的符号；

尾数：小于1的小数，尾数的位数（长度）决定数的精度。

在计算机语言中，把数分为实型数和复型数两大类，分别和数学中的实数和复数相对应。在实型数中，又有整型数、定点数和浮点数之分，其中整型数相当于数学中的整数，定点数相当于数学中的小数，浮点数又称作指数记数法，相当于数学中的科学计数法，不同只在于表示方法，例如，数学中的-79*105，在计算机上用浮点数表示为-0.79E7，其中-0.79为其尾数部分，E7为代表107的指数部分。那么像√2 ，2/3等无理数、分数，在计算机及其语言中，又表示成什么样子呢？

在BASIC语言中，有一个计算平方根的函数SQR（X），和数学中的√X起同样作用，都是求X的平方根，如2的平方根SQR（2）=√2 ，只是SQR（X）被称作函数，受计算机字长的限制，不再是无理数，而是一个有限字长的浮点数，取为√2 的近似值；像2/3，在BASIC语言中，称作表达式，所得的是分子除以分母后所得的结果，只是为了计算机方便和清晰明了采用2/3这种表示方法。在计算机上使用的2/3，实际上是2除以3后的用有限字长表示的2/3的近似值。

此外，在计算机语言中，数的大小有着明确规定的范围。如在BASIC语言中，数的绝对值取值范围为[2.938736*10-39，1.701412*1038]；绝对值低于2.938736*10-39，计算机判为0，称作下溢为0；超过上限1.701412*1038，计算机将显示出错信息，称为上溢出错停机；而在数学当中，数的大小是无限的，范围是（-∞，+∞）。

在数学中，0.1=1/10，是一个不存在误差的小数；但在计算机上，0.1用八进制将无法精确表示，是一个含有误差的数。

计算机中的复数，把实部和虚部分开存放，通过内部子程序实现复数各种不同类型的运算。

; N6 v. q0 k, R6 G9 M& b

, `: r0 U' a4 {
( F  P* V7 n$ P7 m/ S7 ^6 l