2.2 算法分析

算法（Algorithm）是解题的步骤。在计算机科学中，算法代表用计算机解一类问题的精确、有效的方法。算法分析是对一个算法需要多少计算时间和存储空间进行定量分析，可以预测这一算法适合在什么样的环境中有效地运行，对解决同一问题的不同算法的有效性作出比较。

2.2.1 算法的概念

算法（Algorithm）是一系列解决问题的清晰指令。要使计算机完成某一工作，首先必须为如何完成预定工作设计一个算法，然后根据算法编写程序。也就是说，算法是能够对一定规范的输入，在有限时间内获得所要求的输出。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述，其中程序的数据结构和变量用来描述问题的对象，程序结构、函数和语句用来描述问题的算法。算法和数据结构是程序的两个重要方面，两者的有机结合就构成了程序。

算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，或者看成按照要求设计好的、有限的、确切的计算序列，并且这样的步骤和序列可以解决一类问题。

算法应该具有以下5个重要的特征：

1）有穷性。一个算法必须保证执行有限步之后结束。

2）确切性。算法的每一个步骤必须有确切的定义。

3）输入。一个算法有0个或多个输入，以描述运算对象的初始情况，所谓0个输入是指算法本身定义了初始条件。

4）输出。一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。

5）可行性。算法原则上能够精确运行，而且用笔和纸做有限次运算后即可完成。

2.2.2 时间复杂度和空间复杂度的概念

程序设计是以算法为基础的，能完成某一个任务的算法并不一定是最好的算法，对算法进行分析是一个非常复杂的事情。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务，一个算法的优劣可以用空间复杂度与时间复杂度来衡量。在算法分析中，用数学符号“O”来表示复杂度的数量级。

●O（1）为常量级。

●O（n），O（n2），…，O（nk）为多项式级。

●O（2n），O（en）为指数级。

●O（log2n），O（nlog2n）为对数级。

算法中某一具体语句在算法的运行过程中执行的次数称为该语句的频度，记作F（n）。如下面算法的语句频度：F（n）＝n2＋n3。

算法的时间复杂度是指算法需要消耗的时间资源，是以算法中频度最大的语句来度量的，可记作T（n）＝O（F（n））。例如，下面程序段的时间复杂度是O（n3）。

问题的规模n越大，算法执行时间的增长率与F（n）的增长率正相关，称做渐进时间复杂度（Asymptotic Time Complexity）。常见的时间复杂度有O（1），O（log2n），O（n），O（nlog2n），O（n2），O（n3），…。时间T与n的线性关系如图2-7所示。

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。算法实现所占用的存储空间一般可以分成3种：

1）指令、常数和系统变量所占用的存储空间。

2）I／O数据所占用的存储空间。

3）算法执行过程中所需要的存储空间。

算法的空间复杂度分析是指对其执行过程中所需辅助空间大小的分析。空间复杂度也用O（n）来表示，常见的几种空间复杂度有O（1），O（n），O（n2），O（n3）。例如：

例中，辅助变量i，j，k与变量n没有关系，所以其空间复杂度为O（1），为常量级。

算法的时间复杂度和空间复杂度是一对矛盾，要节省执行时间，就必须占有更多的存储空间，要节省存储空间就必然会增加算法的执行时间，两者不可以兼顾。在分析具体问题时，对时间和空间的消耗，要根据具体问题具体侧重。在软件设计中，算法要求正确、易读、高效、占用空间少。

2.2.3 算法的描述

1.算法描述语言

算法必须通过算法描述语言来表达，或选用某一种高级语言在计算机上实现。常用的算法描述语言有：

（1）自然语言

自然语言就是人们日常使用的语言，利用这种语言来描述算法，比较习惯且容易接受，但是叙述较烦琐和冗长，极易出现歧义，所以在进行算法描述时要谨慎使用此方法。

（2）类Pascal语言描述

类Pascal语言描述是用一种类似于Pascal语法规则的程序语言来描述算法，在算法中可随意注释，无需考虑是否合乎语法约束。

（3）高级语言描述

高级语言描述是用严谨的某一高级语言的语法和函数来描述算法的。例如，常用的C语言、Java语言等高级语言。

2.流程图

流程图是用一些图框表示各种操作。在图形上用扼要的文字和符号表示具体的操作，用箭头的流线来表示操作的先后顺序。流程图表示算法，直观形象，易于理解。图2-8给出了常用的数据流程图符号。

起止框表示算法的开始和结束。输入／输出框，也叫做I／O框，表示进行的输入／输出操作。处理框表示某一处理或运算功能。判断框有一个入口，两个出口，表示根据给定的条件判断是否满足决定算法的执行路径。流程线表示程序执行的路径，即箭头所指的方向。连接符用圆表示，用以表明转向流程图的它处，或从流程图它处转入。它是流线的断点，在图内注明某一标识符表明该流线将在具有相同标识符的另一连接符处继续下去。

【例2-4】 将求5！的算法用流程图表示，如图2-9所示。

一个流程图包括：

●表示相应操作的框。

●带箭头的流程线。

●框内外必要的文字说明。

每一个程序编制人员都应当熟练掌握流程图。

下面具体介绍常用来描述算法的3种基本结构和改进的流程图。

（1）传统流程图的弊端

传统流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制，流程可以随意转来转去，使流程图变得毫无规律。为了限制箭头的滥用而使流程随意转向，规定了3种基本结构。对于所有的程序，整个程序由基本结构通过并列（即顺序）和嵌套构成。

（2）3种基本结构

1）顺序结构，如图2-10所示。

2）选择结构，如图2-11所示。

3）循环结构：循环结构分为while型和until型。

●while型循环结构如图2-12所示。

●until型循环结构如图2-13所示。

（3）3种基本结构的特点

1）只有一个入口。

2）只有一个出口。

3）结构内的每一部分都有机会被执行到。

4）结构内不存在死循环。

已经证明，由以上3种基本结构顺序组成的算法结构可以解决任何复杂的问题。

（4）用N-S流程图表示算法

1）顺序结构，如图2-14所示。

2）选择结构，如图2-15所示。

3）循环结构，如图2-16所示。