2.1　算法的基本概念

算法是解决问题的完整的步骤描述，是解决问题的策略、规则和方法。算法与程序设计、数据结构密切相关，正如著名计算机科学家Niklaus Wirth提出的公式：算法+数据结构=程序。

算法是程序不可缺少的部分。算法的描述形式有很多种，如传统流程图、结构化流程图、计算机程序语言等。下面介绍算法的几个特性，并且分析一个好的算法应该具备哪些特点。

2.1.1　算法的特性

算法是为解决某个特定类型的问题而设计的一个实现过程，它具有以下特性。

1.有穷性

一个算法必须在执行有穷步之后结束，并且每一步都在有穷时间内完成，不能无限地执行下去。就像一条线段，有起点有终点，不能无限延长，如图2.1所示。

例如，要编写一个整数由小到大累加的程序，一定要设置整数的上限，否则程序会无终止地运行下去，也就是常说的死循环。

2.确定性

算法的每一步都应该是确切定义的，不能有二义性，要执行的每个步骤都必须有严格而清楚的规定。

3.可行性

算法中的每一步都应该能有效地运行，也就是说算法是可执行的，并且要求最终能得到正确的结果。例如，如图2.2所示的程序，代码中的“z=x/y；”就是一个无效的语句，因为0不可以作分母。

4.输入

一个算法可以有一个或多个输入，也可以没有输入，输入就是在执行算法时从外界获取的数据，如算法所需的初始量。有多个输入的算法代码如下：

没有输入的算法代码如下：

5.输出

输出是算法最终得到的结果，一个算法有一个或多个输出。编写程序的目的就是要得到输出。例如，在控制台中输出“MingRi”，如图2.3所示。

如果一个程序在运行后没有得到输出，那么这个程序就失去了意义。

2.1.2　算法的优劣

衡量一个算法的优劣，通常要从以下几个方面分析。

1.正确性

正确性是指所写的算法能满足具体问题的要求，即对任何合法的输入，算法都会得出正确的输出。

2.可读性

可读性是指算法被理解的难易程度。一个算法的可读性十分重要，如果一个算法比较抽象，难以理解，那么这个算法就不易交流和推广，在修改、扩展及维护时都十分不方便。因此在编写算法时，要尽量将该算法写得简明易懂。

3.健壮性

在一个程序编写完成后，运行该程序的用户对程序的理解各不相同，并不能保证每个人都能按照要求进行输入。健壮性是指当输入的数据非法时，算法能够做出相应判断和反应，而不会因为输入错误造成程序瘫痪。例如，用积木搭建“高塔”，即使取下几块积木，“高塔”仍然不会倒，这就是“高塔”的健壮性。

4.时间复杂度与空间复杂度

时间复杂度是指算法运行所需的时间。不同的算法具有不同的时间复杂度。如果一个程序比较小，就感觉不到时间复杂度的重要性；如果一个程序特别大，就会察觉到时间复杂度是十分重要的。因此，写出更高速的算法一直是算法不断改进的目标。空间复杂度是指算法运行所需的存储空间。