1.1.1 算法的基本概念
　　1.1.2 算法复杂度

　　1.1.1 算法的基本概念　

　　所谓算法是指解题方案的准确而完整的描述。
　　对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。但算法不等于程序，也不等于计算方法。当然，程序也可以作为算法的一种描述，但程序通常还需考虑很多与方法和分析无关的细节问题，这是因为在编写程序时要受到计算机系统运行环境的限制。通常，程序的编制不可能优于算法的设计。
　　1. 算法的基本特征
　　作为一个算法，一般应具有以下几个基本特征。
　　（1） 可行性（effectiveness）
　　针对实际问题设计的算法，人们总是希望能够得到满意的结果。但一个算法又总是在某个特定的计算工具上执行的，因此，算法在执行过程中往往要受到计算工具的限制，使执行结果产生偏差。例如，在进行数值运算时，如果某计算工具有7位有效数字（如程序设计语言中的单精度运算），则在计算下列三个量
　　A=1012，B=1，C= —1012
　　的和时，如果采用不同的运算顺序，就会得到不同的结果，即：
　　A+B+C=1012+1+（—1012）=0
　　A+C=B=1012+（—1012）+1=1
　　而在数学上，A+B+C与A+C+B是完全等价的。因此，算法与计算公式是有差别的。在设计一个算法时，必须考虑它的可行性，否则是不会得到满意结果的。
　　（2） 确定性 (definiteness)
　　算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。这一性质也反映了算法与数学公式的明显差别。在解决实际问题时，可能会出现这样的情况：针对某种特殊问题，数学公式是正确的，但按此数学公式设计的计算过程可能会使计算机系统无所适从。这是因为根据数学公式设计的计算过程只考虑了正常使用的情况，而当出现异常情况时，此计算过程就不能适应了。
　　（3） 有穷性 (finiteness)
算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。数学中的无穷级数，在实际计算时只能取有限项，即计算无穷级数值的过程只能是有穷的。因此，一个数的无穷级数表示只是一个计算公式，而根据精度要求确定的计算过程才是有穷的算法。
　　算法的有穷性还应该包括合理的执行时间的含义。因为，如果一个算法需要执行千万年，显然失去了实用价值。
　　（4） 拥有足够的情报
　　一个算法是否有效，还取决于为算法所提供的情报是否足够。通常，算法中的各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这是算法执行的起点或者是依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法本身也就无法执行或导致执行有错。一般来说，当算法拥有足够的情报时，此算法才是有效的，而当提供的情报不够时，算法可能无效。
　　综上所述，所谓算法，是一组严谨的定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。
　　2．算法的基本要素
　　一个算法通常有两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。
　　（1） 算法中对数据的运算和操作
每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。因此，计算机算法就是计算机能处理的操作所组成的指令序列。
　　通常，计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。在一般的计算机系统中，基本的运算和操作有以下四类：
　　①算术运算：主要包括加、减、乘、除等运算。
　　②逻辑运算：主要包括“与”、“或”、“非”等运算。
　　③关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算。
　　④数据传输：主要包括赋值、输入、输出等操作。
　　前面提到，计算机程序也可以作为算法的一种描述，但由于在编制计算机程序时通常要考虑很多与方法和分析无关的细节问题（如语法规则），因此，在设计算法的一开始，通常并不直接用计算机程序来描述算法，而是用别的描述工具（如流程图，专门的算术描述语言，甚至用自然语言）来描述算法。但不管用哪种工具来描述算法，算法的设计一般都应从上述四种基本操作考虑，按解题要求从这些基本操作中选择合适的操作组成解题的操作序列。算法的主要特征着重于算法的动态执行，它区别于传统的着重于静态描述或按演绎方式求解问题的过程。传统的演绎数学是以公理系统为基础的，问题的求解过程是通过有限次推演来完成的，每次推演都将对问题作进一步的描述，如此不断推演，直到直接将解描述出来为止。而计算机算法则是使用一些最基本的操作，通过对已知条件一步一步的加工和变换，从而实现解题目标。这两种方法的解题思路是不同的。
　　（2） 算法的控制结构
　　一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。
　　算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统的流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。
　　3．算法设计基本方法
　　计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。计算机算法不同于人工处理的方法。
　　本节介绍工程上常用的几种算法设计方法，在实际应用时，各种方法之间往往存在着一定的联系。
　　（1） 列举法
　　列举法的基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。因此，列举法常用于解决“是否存在”或“有多少种可能”等类型的问题，例如求解不定方程的问题。
　　列举法的特点是算法比较简单。但当列举的可能情况较多时，执行列举算法的工作量将会很大。因此，在用列举法设计算法时，使方案优化，尽量减少运算工作量，是应该重点注意的。通常，在设计列举算法时，只要对实际问题进行详细的分析，将与问题有关的知识条理化、完备化、系统化，从中找出规律；或对所有可能的情况进行分类，引出一些有用的信息，是可以大大减少列举量的。
列举原理是计算机应用领域中十分重要的原理。许多实际问题，若采用人工列举是不可想象的，但由于计算机的运行速度快，擅长重复操作，可以很方便的进行大量列举。列举算法虽然是一种比较笨拙而原始的方法，其运算量比较大，但在有些实际问题中（如寻找路径、查找、搜索等问题），局部使用列举法却是很有效的，因此，列举算法是计算机算法中的一个基础算法。
　　（2） 归纳法
　　归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找到一般的关系。显然，归纳法要比列举法更能反映问题的本质，并且可以解决列举量为无限的问题。但是，从一个实际问题中总结归纳出一般的关系，并不是一件容易的事情，尤其是要归纳出一个数学模型更为困难。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。
归纳是一种抽象，即从特殊现象中找出一般关系。但由于在归纳的过程中不可能对所有的情况进行列举，因此，最后由归纳得到的结论只是一种猜测，还需要对这种猜测加以必要的证明。实际上，通过精心观察而得到的猜测得不到证实或最后证明猜测是错的，也是常有的事。
　　（3） 递推
　　所谓递推，是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。递推本质上也属于归纳法，工程上许多递推关系式实际上是通过对实际问题的分析与归纳而得到的，因此，递推关系式往往是归纳的结果。
　　递推算法在数值计算中是极为常见的。但是，对于数值型的递推算法必须要注意数值计算的稳定性问题。
　　（4） 递归
　　人们在解决一些复杂问题时，为了降低问题的复杂程度（如问题的规模等），一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。由此可以看出，递归的基础也是归纳。在工程实际中，有许多问题就是用递归来定义的，数学中的许多函数也是用递归来定义的，递归在可计算性理论和算法设计中占有很重要的地位。
　　递归分为直接递归与间接递归两种。如果一个算法P显式的调用自己则称为直接递归。如果算法P调用另一个算法Q，而算法Q又调用算法P，则称为间接递归调用。
　　递归是很重要的算法设计方法之一。实际上，递归过程能将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止。
　　有些实际问题，既可以归纳为递推算法，又可以归纳为递归算法。但递推与递归的实现方法是大不一样的。递推是从初始条件出发，逐次推出所需求的结果；而递归则是从算法本身到达递归边界的。通常，递归算法要比递推算法清晰易读，其结构比较简练。特别是在许多比较复杂的问题中，很难找到从初始条件推出所需结果的全过程，此时，设计递归算法要比递推算法容易的多。但递归算法的执行效率比较低。
　　（5） 减半递推技术
　　实际问题的复杂程度往往与问题的规模有着密切的联系。因此，利用分治法解决这类实际问题是有效的。所谓分治法，就是对问题分而治之。工程上常用的分治法是减半递推技术。
　　所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。
　　下面举例说明利用减半递推技术设计算法的基本思想。
　　例1.1 设方程f(x)=0在区间[a,b]上有实根，且f(a)与f(b)异号。利用二分法求该方程在区间[a,b]上的一个实根。
　　用二分法求方程实根的减半递推过程如下：
　　首先取给定区间的中点c=(a+b)/2
　　然后判断f(c)是否为0。若f(c)=0，则说明c即为所求的根，求解过程结束；如果f(c)≠0,则根据以下原则将原区间减半：
　　若f(a)f(c)<0,则取原区间的前半部分；
　　若f(b)f(c)<0则取原区间的后半部分；
　　最后判断减半后的区间长度是否已经很小；
　　若|a-b|<ε,则过程结束，取（a+b）/2为根的近似值；
　　若|a-b|≥ε，则重复上述的减半过程。
　　（6） 回溯法
　　前面讨论的递推和递归算法本质上是对实际问题进行归纳的结果，而减半递推技术也是归纳法的一个分支。在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。对于这类问题，一种有效的方法就是“试”。通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。这种方法为回溯法。回溯法在处理复杂数据结构方面 有着广泛的应用。

　　1.1.2　算法复杂度

　　算法的复杂度主要包括时间复杂度和空间复杂度。
　　1． 算法的时间复杂度
　　所谓算法的时间复杂度，是指执行算法所需要的计算工作量。
　　为了能够比较客观的反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。基本运算反映了算法运算的主要特征，因此，用基本运算的次数来度量算法工作量是客观的也是实际可行的，有利于比较同一问题的几种算法的优劣。例如，在考虑两个矩阵相乘时，可以将两个实数之间的乘法运算作为基本运算，而对于所用的加法（或减法）运算忽略不计。又如，当需要在　　一个表中进行查找时，可以将两个元素之间的比较作为基本运算。
　　算法所执行的基本运算次数还与问题的规模有关。例如，两个20阶矩阵相乘与两个10阶矩阵相乘，所需要的基本运算（即两个实数的乘法）次数显然是不同的，前者需要更多的运算次数。因此，在分析算法的工作量时，还必须对问题的规模进行度量。
　　综上所述，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即
　　算法的工作量=f(n)
　　其中n是问题的规模。例如，两个n阶矩阵相乘所需要的基本运算（即两个实数的乘法）次数为n3，也就是时间复杂度为n3。
　　在具体分析一个算法的工作量时，还会存在这样的问题：对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关，而实际上又不可能将所有可能情况下算法所执行的基本运算次数都列举出来。例如，“在长度为n的一维数组中查找值为x的元素”，若采用顺序搜索法，即从数组的第一个元素开始，逐个与被查值x进行比较 。显然，如果第一个元素恰为x，则只需要比较1次。但如果x为数组的最后一个元素，或者x不在数组中，则需要比较n次才能得到结果。因此，在这个问题的算法中，其基本运算（即比较）的次数与具体的被查值x有关。
　　在同一个问题的规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量。
　　(1)平均性态（Average Behavior）
　　所谓平均性态分析，是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。
设x是所有可能输入中的某个特定输入，p(x)是x出现的概率（即输入为x的概率），t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为
　　A(n)=∑p(x)t(x)
　　x∈Dn
　　其中Dn表示当规模为n时，算法执行时所有可能输入的集合。这个式子中的t(x)可以通过分析算法来加以确定；而P（x）必须由经验或用算法中有关的一些特定信息来确定，通常是不能解析地加以计算的。如果确定P(x)比较困难，则会给平均性态的分析带来困难。
　　(2)最坏情况复杂性(Worst-Case Complexity)
　　所谓最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。它定义为
　　W(n)=max{t(x)}
　　x∈Dn
　　显然，W(n)的计算要比A(n)的计算方便的多。由于W(n)实际上是给出了算法工作量的一个上界，因此，它比A(n)更具有实用价值。
　　下面通过一个例子来说明算法复杂度的平均性态分析与最坏情况分析。
　　例1．2 采用顺序搜索法，在长度为n的一维数组中查找值为x的元素。即从数组的第一个元素开始，逐个与被查值x进行比较。基本运算为x与数组元素的比较。
　　首先考虑平均性态分析。
　　设被查项x在数组中出现的概率为q。当需要查找的x为数组中第i个元素时，则在查找过程中需要做i次比较，当需要查找的x不在数组中时（即数组中没有x这个元素），则需要与数组中所有的元素进行比较。即 i ,1≤i≤n
　　ti=
　　n,i=n+1
　　其中i=n+1表示x不在数组中的情况。
　　如果假设需要查找的x出现在数组中每个位置上的可能性是一样的，则x出现在数组中每一个位置上的概率为q/n（因为前面已经假设x在数　　组中的概率为q），而x不在数组中的概率为1-q。即
　　q/n,1≤i≤n
　　pi=
　　1-q,i=i+1
　　其中i=n+1表示x不在数组中的情况。
　　因此，用顺序搜索法在长度为n的一维数组中查找值为x的元素，在平均情况下需要做的比较次数为
　　n+1 n
　　A(n)=∑piti=∑(q/n)i+(1-q)n=(n+1)q/2+(1-q)n
　　i=1 i=1
　　如果已知需要查找的x一定在数组中，此时q=1，则A(n)=(n+1)/2。这就是说，在这种情况下，用顺序搜索法在长度为n的一维数组中查找值为x的元素，在平均情况下需要检查数组中一半的元素。
　　如果已知需要查找的x有一半的机会在数组中，此时q=1/2，则
　　A(n)=[(n+1)/4]+n/2≈3n/4
　　这就是说，在这种情况下，用顺序搜索法在长度为n的一维数组中查找值为x的元素，在平均情况下需要检查数组中3/4的元素。
　　再考虑最坏情况分析。
　　在这个例子中，最坏情况发生在需要查找的x是数组中的最后一个元素或x不在数组中的时候，此时显然有
　　W(n)=max{ti|1≤i≤n+1}=n
　　在上述例子中，算法执行的工作量是与具体的输入有关的，A(n)只是它的加权平均值，而实际上对于某个特定的输入，其计算工作量未必是A(n),且A(n)也不一定等于W(n)。但在另外一些情况下，算法的计算工作量与输入无关，即当规模为n时，在所有可能的输入下，算法所执行的基本运算次数是一定的，此时有A(n)=W(n)。例如，两个n阶的矩阵相乘，都需要做n3次实数乘法，而与输入矩阵的具体元素无关。
　　2．算法的空间复杂度
　　一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。
　　一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间（例如，在链式结构中 ，除了要存储数据本身外，还需要存储链接信息）。如果额外空间量相对于问题规模来说是常数，则称该算法是原地（in place）工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。