1.2 算法和算法分析

1.2.1 算法的描述

算法（algorithm）定义：为了解决某一类问题而设计的一个有限长的操作序列。一个算法必须满足以下5个重要特性。

① 有穷性。算法对于任意合法的输入值，在执行有限步之后一定能结束。

② 确定性。算法中的每一个操作必须有确切的含义，无二义性，并在任何条件下，算法都只有一条执行路径。

③ 可行性。算法中的所有操作都可通过已经实现的基本运算有限次地实现。

④ 输入。算法具有零个或多个输入，这些输入为一组特定的数据对象集合。

⑤ 输出。算法具有一个或多个输出，它是一组与“输入”有确定关系的量值。

1.2.2 算法设计的要求

（1）正确性（correctness）

算法的执行结果应当满足预先规定的4个要求：①程序不含语法错误；② 程序对于几组输入数据能够得出满足规格说明要求的结果；③程序对于精心选择的典型、苛刻且带有刁难性的几组输入数据能够得出满足规格说明要求的结果；④程序对于一切合法的输入数据都能产生满足规格说明要求的结果。

（2）可读性（readability）

算法应有助于人们阅读、理解和调试，晦涩难懂的算法易于隐藏较多错误，难以调试和修改。

（3）健壮性（robustness）

当输入不合法的数据时，算法能够做出适当的反应或处理，不至于产生莫名其妙的结果。同时，处理出错的方法应该是返回一个表示错误或错误性质的值，并终止程序的执行，以便在更高的抽象层次上进行处理。

（4）时空效率（efficiency）

要求算法执行的时间应该尽可能短、算法执行过程中占用的存储空间应该尽可能少。时空要求与求解问题的规模有关，两者通常相互矛盾，因此，应在它们之间有所平衡。

1.2.3 算法分析

算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度，主要考察算法的时间效率和空间效率，以便比较和改进算法。通常，在算法的运算空间较为充裕的情况下，更多地关注算法的时间复杂度。

1.时间复杂度

算法执行的时间可通过依据该算法编制的程序在计算机上从开始运行到结束运行所消耗的时间来度量，也就是算法中每条语句的执行时间之和。由于每条语句的执行时间是该语句重复执行的次数或频度（frequency count）与该语句执行时间的乘积，而语句的执行时间又与机器性能、编译程序等诸多因素有关，难以统一和确定。因此，假设每条语句的执行时间为一个单位时间，则算法的执行时间为算法中所有语句的频度之和。

一般而言，算法中基本操作的频度是问题规模 n（如算法所处理的矩阵的阶数，线性表的长度）的某个函数 f(n)，算法的时间量度记作 T(n)=O(f(n))，它表示随问题规模 n 的增大，算法的执行时间增长率与 f(n)的增长率相同，称为算法的渐进时间复杂度（asymptotic time complexity），简称时间复杂度。同时，要全面地分析算法，需要分别考虑算法在最坏情况、最好情况以及平均情况下的时间代价。对于最坏情况下的时间复杂度，主要采用大写数学符号O表示法来描述。一般定义为：当且仅当存在正整数c和n0，使得T(n)≤c f(n)对所有的n≥n0成立，则称该算法的渐进时间复杂度为T(n)=O(f(n))。

在一般情况下，对于一个问题（算法）只需选择一种基本操作来讨论算法的时间复杂度即可，有时也需要同时考虑几种基本操作，甚至可对不同的操作赋以不同权值，以反映执行不同操作所需的相对时间，这种做法便于综合比较解决同一问题的两种完全不同的算法。由于算法的时间复杂度考虑的只是对于问题规模n的增长率，因此在难以精确计算基本操作执行次数（或语句频度）的情况下，只需求出它关于n的增长率或阶即可。

【例1-3】 如何进行算法的时间复杂度分析。

首先介绍计算增长率的加法规则和乘法规则。设 T1(n)和 T2(n)分别是程序段P1和P2的运行时间，且 T1(n)=O(f(n))，T2(n)=O(g(n))，即 T1(n)是 f(n)的函数，T2(n)是 g(n)的函数（O函数定义见后），则执行P1 之后紧接着执行P2 的运行时间为：T1(n)+T2(n)=O(max{f(n)，g(n)})，称为加法规则；T1(n)×T2(n)=O[f(n)×g(n)]，称为乘积规则。一般来说，分析程序的时间复杂度是，先求出各模块（各语句）的运行时间，再求整个程序的运行时间，它可表示成唯一参数——输入数据的规模n的函数。具体可遵循以下规则。

① 每个赋值或读/写语句的运行时间通常是O(1)。如果赋值语句的右部为函数调用，则要考虑计算函数值所消耗的时间。

② 序列语句的运行时间由加法规则确定。

③ 语句if B then S1 else S2的运行时间为条件B的测试时间（通常取O(1)）加上两个分支语句S1、S2运行时间的较大者。若无else S2，则只需加上S1的运行时间。

④ 循环语句的运行时间是循环体本身的运行时间和计算循环参数、测试循环终止条件及跳回循环开头所花的时间，后一部分通常取 O(1)。遇到多层循环时，要由内层向外层逐层分析。在分析外层循环时间时，内层循环的运行时间应该是已知的，可把内循环看成是外循环体的一部分。

⑤ 若程序中只包含非递归过程，则从没有调用语句（对函数也认为是调用）的过程开始，计算所有这种过程的运行时间。然后考虑有调用语句的任一过程P，在P调用的全部过程的运行时间都算完之后，即可开始计算P的运行时间。若在程序中有递归过程，则可令每个递归过程对应于一个未知的时间开销函数T(n)，其中n是过程参数的长度。之后，列出一个关于T的递归方程并求解之。

【例1-4】 下面是一个n×n阶矩阵A自乘得到B=A×A的算法，分析其时间复杂度。

            int  A[n][n]；                                                        //全局数组
            void  mtxmlt（）
            {        int B[n][n]；                                                //语句频度
                    for（int i=0；i<n；i++）                                     //n+1
                            for（int j=0；j<n；j++）                              //n×（n+1）
                            {   B[i][j]=0；                                       //n×n
                                for（int k=0；k<n；k++）                          //n2×（n+1）
                                    B[i][j]=B[i][j]+A[i][k]*A[k][j]；             //n×n×n
                            }
            }

时间复杂度 T(n)=n+1+n(n+1)+n×n+n2(n+1)+n×n×n=2n3+3n2+2n+1。当 n→∞时，T(n)∝n3，故算法时间复杂度的数量级为O(n3)。

【例1-5】 已知算法如下，求带下划线语句的频度。

            int i=0；
                while（（i<n）&&（x!=A[i]））i++；
                  if（A[i]==x） return i；

在此程序段中，语句的频度不仅是 n 的函数，而且与 x 及数组A中各分量的值有关。在这种情况下，通常考虑最坏的情况。由于while循环执行的最大数为n-1，因此下划线语句频度为n-1。

【例1-6】 分析计算n！的递归函数fact(n)的时间复杂度。

            long  fact（int n）
            {    if（n==1） return 1；
                return  fact（n-1）*n；
            }

递归函数fact(n)的输入规模是 n，设 T(n)是fact(n)的时间开销函数。在上述算法中，if语句条件测试及语句return的运行时间是O(1)，递归调用fact(n-1)的运行时间是T(n-1)。假设两个整数相乘和赋值操作的运算时间是 O(1)，故return fact(n-1)*n 的运行时间是O(1)+T(n-1)。因此，对于常数 C 和 D 有 T(n)=D，n≤1；T(n)=C+T(n-1)，n＞1。现在来解这个递归方程。设 n＞2，对上式中 T(n-1)进行展开有 T(n-1)=C+T(n-2)，代入 T(n)中，有T(n)=2C+T(n-2)，再展开 T(n-2)得 T(n)=3C+T(n-3)。一般有 T(n)=iC+T(n-i)，n＞i。最后，当i=n-1时，得T(n)=C(n-1)+T(1)=C(n-1)+D。当n→∞时，T(n)∝n。

2.空间复杂度

算法在执行时需要占用一定的存储空间，这些空间除了包括程序、输入数据、常数、变量所占的空间外，还包括算法对输入数据进行运算以及为实现运算所需信息的额外空间。额外空间与算法的质量密切相关，好的算法既节省时间又节省额外空间。如果算法的输入数据所占用的空间只取决于问题本身，与算法无关，则算法的存储空间只需要分析除输入数据和程序之外的额外空间；否则，应同时考虑输入数据本身所需空间（与输入数据的表示形式有关）。通常，只有完成同一功能的几个算法之间才具有可比性，因此这些输入数据所占用的空间不用进行比较，只需比较那些辅助的或附加的存储空间即可。

类似于算法的时间复杂度，一般以空间复杂度（space complexity）作为算法所需存储空间的量度，记作S(n)=O(f(n))，其中n为问题的规模（或大小）。在大多数的算法设计中，时间效率和空间效率两者很难兼得，设计者往往需要根据具体的问题进行权衡，有时会用更多的存储空间来换取时间，有的时候又会用增加算法执行时间来减少所需的存储空间。

【例1-7】 如何进行算法的空间复杂度分析。

对算法占用存储空间的分析类似于时间复杂度。估计渐近空间复杂度，称为空间复杂度。由于问题中原始数据所占用的空间与算法无关，故一般考虑空间复杂度时只估算算法中所需增添的辅助空间。例如，例1-5中除原始数据外，只用了两个变量x和i的辅助空间。因为与问题的规模n无关，所以空间复杂度S(n)=O(1)。

在一般情况下，算法的时间和空间开销是一对矛盾。要想空间比较节约，往往时间消耗就大，反之亦然。具体在一个问题中到底注重哪一方面，这要看实际的需要和可能而定。在本书中，着重考虑时间因素，而假设内存足够大。因为在求解实际问题中，当输入量急剧增加时，如果没有高效率的算法，单纯依靠提高计算机的速度，有时是无法达到要求的。

注：O 是数学符号，它的定义是，若 f(n)是正整数 n 的一个函数，则 T(n)=O(f(n))表示存在一个正的常数 M，使得当 n≥n0时都满足|T(n)|≤ M|f(n)|，即表明算法所需执行时间是f(n)的常数倍。如例1-6中，当n≥1时，T(n)≤3n，即n0=1，M=3，f(n)=n。