2.1 算法的概念

2.1.1 算法的定义

算法（Algorithm）描述的是解决某个问题的完整步骤，可以理解为一系列的指令，也可以理解为一种系统的策略机制。也就是说，当输入符合一定规范的时候，算法能用有限的时间、有限的空间或一定的效率获得所要求的输出。在数学中，解决一个问题的有限的顺序排列的运算步骤组成了一个算法。类比数学思想，在计算机中，解决一个问题的有限的顺序排列的指令可以称为一个算法。算法中的指令描述的是计算过程，当运行一个算法时，计算机将从初始状态开始，经过有限且明确的指令，产生输出并停止运行。

2.1.2 算法的特征

一般来说，对于一个算法，有5个重要的特征：输入项（Input）、输出项（Output）、确定性（Definiteness）、可行性（Finiteness）和有穷性（Effectiveness）^[1]，见表2-1。

表2-1 算法的特征

（续）

2.1.3 算法的评价

由于同一个问题可以用不同的算法解决，因此往往需要根据具体的要求选择合适的算法，这就要对算法进行评价，主要的评价依据为时间复杂度（Time Complexity）和空间复杂度（Space Complexity）。

1.时间复杂度

算法的时间复杂度是一个能够定性描述算法运行时间的函数，也可以把它看作一个关于问题规模的函数，常用符号O表示。一般来说，问题的规模越大，算法执行的指令越多，时间越长，则算法的时间复杂度越大^[2]。

例如，计算下列代码的时间复杂度。

具体的计算过程见表2-2。

表2-2 计算时间复杂度

由表2-2可知，上述代码的时间复杂度为O（n³）。

2.空间复杂度

算法的空间复杂度是度量该算法在运行过程中临时占用的存储空间大小的度量函数，问题的规模越大，算法的空间复杂度也越大。空间复杂度的表示符号与时间复杂度相同，都用O表示。

除了时间复杂度和空间复杂度，还可以用正确性、可读性、容错性等指标评价一个算法，对算法进行评估可以在节约资源的前提下，选择更合适的算法去解决问题。