1. 算法的概念

算法(Algorithm)是将一组输入转化成一组输出的一系列计算步骤,其中每个步骤必须能在有限时间内完成。比如第 3 节 “递归”习题1中的Euclid算法,输入是两个正整数,输出是它们的最大公约数,计算步骤是取模、比较等操作,这个算法一定能在有限的步骤和时间内完成(想一想为什么?)。再比如将一组数从小到大排序,输入是一组原始数据,输出是排序之后的数据,计算步骤包括比较、移动数据等操作。

算法是用来解决一类计算问题的,注意是一类问题,而不是一个特定的问题。例如,一个排序算法应该能对任意一组数据进行排序,而不是仅对int a[] = { 1, 3, 4, 2, 6, 5 };这样一组数据排序,如果只需要对这一组数据排序可以写这样一个函数来做:

void sort(void)
{
	a[0] = 1;
	a[1] = 2;
	a[2] = 3;
	a[3] = 4;
	a[4] = 5;
	a[5] = 6;
}

这显然不叫算法,因为不具有通用性。由于算法是用来解决一类问题的,它必须能够正确地解决这一类问题中的任何一个实例,这个算法才是正确的。对于排序算法,任意输入一组数据,它必须都能输出正确的排序结果,这个排序算法才是正确的。不正确的算法有两种可能,一是对于该问题的某些输入,该算法会无限计算下去,不会终止,二是对于该问题的某些输入,该算法终止时输出的是错误的结果。有时候不正确的算法也是有用的,如果对于某个问题寻求正确的算法很困难,而某个不正确的算法可以在有限时间内终止,并且能把误差控制在一定范围内,那么这样的算法也是有实际意义的。例如有时候寻找最优解的开销很大,往往会选择能给出次优解的算法。

本章介绍几种典型的排序和查找算法,并围绕这几种算法做时间复杂度分析。学完本章之后如果想进一步学习,可以参考一些全面系统地介绍算法的书,例如[TAOCP][算法导论]