1.4 算法和算法分析

算法（algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列5个重要特性：

（1）有穷性    一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都能在有穷时间内完成。

（2）确定性    算法中每一条指令都必须有明确的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有惟一的一条执行路径，即对相同的输入只能得出相同的输出。

（3）可行性    一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。

（4）输入    一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。

（5）输出    一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。

算法设计的要求：

（1）正确性（correctness）    算法应当满足具体问题的需求。

（2）可读性（readability）    算法主要是为了人的阅读与交流，其次才是机器执行。

（3）健壮性（robustness）    当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。

（4）效率与低存储量需求    效率指算法执行的时间，存储量指算法执行过程中所需要的最大存储空间。效率和低存储量需求这两者都与问题的规模有关。

算法效率的度量

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作

T(n) = O(f(n))

它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐近时间复杂度（asymptotic time complexity），简称时间复杂度。

算法的存储空间需求

空间复杂度

S(n) = O(f(n))

n为问题的规模（或大小），一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单位和存储一些为实现计算所需信息的辅助空间。