算法基础（第5版）——1.3　算法分析

为了判断一种算法在解决某种问题时的效率如何，需要分析算法。在前一节比较算法时，引入了算法的效率分析。但这些分析过程相当随意，不够正式。我们现在讨论算法分析中使用的术语以及标准的分析方法。在本书后续部分将遵循这些标准。 1.3.1　复杂度分析 在分析一种算法的时间效率时，并没有计算出实际CPU周期数，因为这一数值取决于运行算法的具体计算机。此外，我们甚至不希望计算所执行的指令数，因为指令数取决于用于实现算法的程序设计语言，以及程序员编写程序的方式。我们希望有一种量度，不受计算机、程序设计语言、程序员、算法的所有复杂细节（比如循环索引的递增、指针设定等）的影响。通过对比两种算法在不同n值时完成的比较次数，我们了解到算法1.5的效率要远高于算法1.1，其中n是数组中的项数。这是分析算法的标准方法。一般情况下，算法的运行时间随输入的规模而增加，总运行时间近似正比于某些基本运算（比如比较指令）的执行次数。因此，可以推导某些基本运算的执行次数，将其表示为输入规模的函数，以此来分析算法的效率。 对于许多算法，可以轻松找到一个合理的度量，用来表示输入的大小，我们称之为输入规模（input size）。例如，考虑算法1.1（顺序查找）、算法1.2（数组元素求和）、算法1.3（交换排序）和算法1.5（二分查找）。在所有这些算法中，数组中的项数n都是输入大小的一个简单度量。因此，可以将其称为输入规模。在算法1.4（矩阵乘法）中，行列数n是输入大小的一个简单度量。因此，仍然可以将n称为输入规模。在一些算法中，更合适的做法是用两个数字来度量输入规模。例如，当算法的输入是一幅图时，经常用顶点数和边数来度量输入的大小。因此，我们说输入规模由这两个参数组成。 有时，在将一个参数称为“输入规模”时，一定要非常小心。比如，在算法1.6（斐波那契序列的第n项，递归）和算法1.7（斐波那契序列的第n项，迭代）中，你可能认为应当将n称为输入规模。但是，n是输入，不是输入的规模。对于这一算法，输入规模的合理度量是对n编码所用的符号数。如果采用二进制表示法，则输入规模应当是对n编码所用的比特数，即⌊lgn⌋ + 1。例如， 因此，输入n=13的规模为4。当时，我们将这两种算法分别计算的项数表示为n的函数，从而深入了解了它们的相对效率，但n仍然没有度量输入的规模。这些考虑事项在第9章将变得非常重要，届时将会更详细地讨论输入规模。在此之前，以一种简单度量（比如数组中的项数）作为输入规模，通常就足够了。 在确定了输入规模后，我们选择某条指令或某组指令，使算法完成的总工作量大体与这条指令或这组指令的执行次数成正比。我们将这条指令或这组指令称为算法的基本运算。例如，在算法1.1和算法1.5的每次循环中，都会将x与一个项目S进行比较。因此，在这两个算法中，比较指令都非常适合选为基本运算。我们通过针对每个n值，计算出算法1.1和算法1.5执行这一基本运算的次数，从而深入了解了这两种算法的相对效率。 一般情况下，算法的时间复杂度分析（time complexity analysis）就是针对输入规模的每个取值，计算该算法执行了多少次基本运算。尽管我们不希望考虑算法的实现细节，但通常还是假定基本运算的实现是尽可能高效的。例如，我们假定在算法1.5的实现中，比较运算在每遍while循环中仅执行一次。这样，我们分析的就是基本运算的最高效实现。 基本运算的选择并没有什么一成不变的规则，大多由个人判断力和经验决定。前面已经提到，我们一般不会包含构成控制结构的指令。例如，算法1.1中就没有包含为了控制while循环而对索引值进行递增和比较的指令。有时，完全可以将整个循环看作基本运算。而在另一个极端，对于非常详尽的分析，可能将每条机器指令看作基本运算。前面曾经提到，因为我们希望分析结果与计算机无关，所以本书不会采用这一做法。 有时可能希望考虑两种不同的基本运算。例如，在通过比较键来完成排序的算法中，经常希望将比较指令和赋值指令分别看作基本运算。这并不是说这两条指令一起构成了基本运算，而是有两个不同的基本运算，一个是比较指令，另一个是赋值指令。之所以要这样做，是因为排序算法完成的比较次数和赋值次数通常是不相等的。因此，分别计算出这两种指令的完成次数，可以更深入地了解算法的效率。 回想一下，算法的时间复杂度分析就是针对每个输入规模值，计算基本运算的执行次数。在某些情况下，基本运算的执行次数不仅取决于输入规模，还与输入值有关。算法1.1（顺序查找）就是这种情况。例如，如果x是数组中的第一项，那基本运算仅执行一次，但如果x不在数组中，它就会执行n次。而在其他情况下，比如在算法1.2（数组元素求和）中，确定输入规模n的取值后，基本运算的执行次数都是一样的。在这种情况下，T(n)定义为：对于输入规模n的一个具体取值，该算法执行基本运算的次数。T(n)称为算法的所有情况时间复杂度（every-case time complexity），对T(n)的计算称为所有情况时间复杂度分析。所有情况时间复杂度分析的例子如下。 算法1.2的分析　所有情况时间复杂度（数组元素求和） 除控制指令之外，循环中的唯一指令就是将数组中每个项目加到sum的指令。因此，将这条指令称为基本运算。 基本运算：将数组中的一个项目加到sum。 输入规模：n，数组中的项目数。 无论数组中的数字取何值，for循环的执行遍数均为n。因此，基本运算总是执行n次，T(n) = n。 算法1.3的分析　所有情况时间复杂度（交换排序） 前面曾经提到，在通过键的比较来完成排序的算法中，可以将比较指令或赋值指令看作基本运算。这里将分析比较指令的次数。 基本运算：S[j]与S[i]的比较。 输入规模：n，要排序的项数。 必须求出要执行多少遍for-j循环。对于一个给定的n值，总是执行n1遍for-i循环。在for-i循环的第一遍执行中，for-j循环执行n1遍，在第二遍执行中，for-j循环执行n2遍，在第三遍执行中，for-j循环执行n3遍……在最后一遍执行中，for-j循环执行1遍。因此，for-j循环的总执行遍数给出如下： 最后一个等式在附录A的例A.1中推导。 算法1.4的分析　所有情况时间复杂度（矩阵乘法） 最内层for循环中的唯一指令就是执行乘法和加法的指令。不难看出，可以采用某种方式来实现该算法，使加法运算的执行次数少于乘法运算。因此，我们仅将乘法指令看作基本运算。 基本运算：最内层for循环中的乘法指令。 输入规模：n，行列数。 for-i循环总是执行n遍，在每遍执行中，总是执行n遍for-j循环，在for-j循环的每遍执行中，总会执行n遍for-k循环。因为基本运算在for-k循环内部，所以 T(n) = n × n × n = n3 前文讨论过，在算法1.1中，基本运算的执行次数并非对于所有n值都是相同的。因此，这一算法没有得到所有情况的时间复杂度。对于许多算法都是如此。但是，这并不意味着就不能分析此类算法，因为还有其他三种分析方法可供尝试。第一种是考虑基本运算的最大执行次数。对于给定算法，W(n)的定义为：当输入规模为n时，该算法执行其基本运算的最大次数。所以W(n)称为算法的最差情况时间复杂度（worst-case-time complexity），W(n)的计算称为最差情况时间复杂度分析。如果T(n)存在，显然W(n)=T(n)。下面是当T(n)不存在时对W(n)的分析。 算法1.1的分析　最差情况时间复杂度（顺序查找） 基本运算：将数组中的一个项目与x进行比较。 输入规模：n，数组中的项目数。 基本运算最多执行n次，当x是数组中的最后项目或者当x不在数组时就是这种情况。因此，W(n) = n。 最差情况分析给出的是绝对的最大耗费时间量，但在某些情况下，可能想知道算法的平均运行情况。对于一种给定算法，A(n)定义为：对于输入规模n，该算法执行基本运算的平均次数，也就是均值（期望值）（关于均值的讨论请参阅附录A中的A.8.2节）。A(n)称为算法的平均情况时间复杂度（average-case time complexity），A(n)的计算称为平均情况时间复杂度分析。和W(n)一样，如果存在T(n)，则A(n)=T(n)。 为计算A(n)，需要为所有规模为n的不同输入指定相应概率。基于所有可用信息来指定概率是非常重要的。例如，下面的分析是对算法1.1的平均情况分析。我们将会假定，如果x在数组中，则它位于数组中任一位置的概率相等。如果只知道x可能位于数组中的某一位置，那就没有理由认为某一数组位置会优先于另一位置。因此，为所有数组位置指定相同概率是合理的。这就是说，我们正在计算的是对所有项目执行相同次查找时所需要的平均查找时间。如果有信息表明不会出现服从这种分布的输入，那就不应当在分析中使用这一分布。例如，如果数组中包含一些人的名字，而我们正在查找从所有美国人口中随机选出的名字，那对常见名“John”所在数组位置的查找频率可能要高于对罕见名字“Felix”所在位置的查找频率（关于随机性的讨论，请参阅附录A中的A.8.1节）。我们不应忽略这一信息，再假定所有位置都是等概率的。 下面的分析表明，平均情况的分析通常要难于最差情况的分析。 算法1.1的分析　平均情况时间复杂度（顺序查找） 基本运算：将数组中的一个项目与x进行比较。 输入规模：n，数组中的项数。 首先分析已知x在S中的情景，S中的项目各不相同，而且没有理由认为x在某个数组位置的可能性要高于另一位置。基于这一信息，对于1≤k≤n，x在第k个数组位置的概率为1/n。如果在第k个数组位置中，为找出x位置（然后退出循环）而执行的基本运算次数为k。也就是说，平均情况时间复杂度为： 这个四重等式的第三步在附录A中的例A.1中推导。不出所料，平均来说，将查找数组大约一半的位置。 下面分析x可能不在数组中的情景。为分析这一情景，必须为“x在数组中”这一事件指定某一概率p。如果x在数组中，则再次假设它以相同概率分布在从1至n的位置中。因此，x位于第k个位置的概率就是p/n，不在数组中的概率为1p。回想一下，如果在第k个位置找到了x，则执行k遍循环；如果x不在数组中，则执行n遍循环。因此，平均情况时间复杂度为： 这一三重等式中的最后一步用代数运算推导得出。若p=1，则A(n)=(n+1)/2，与前面一样。若p=1/2，则A(n)=3n/4+1/4。这意味着，平均来说，将大约查找数组位置的3/4。 在继续后续讨论之前，要给出一点有关“平均（值）”的提醒。尽管人们经常将“平均”作为典型情景提及，但在这样解读“平均”时一定要非常小心。例如，气象学者可能会说，在芝加哥，一个典型1月25日的最高温度为22°F，因为在过去80年里，这一天的平均最高温度就是22°F。报纸上可能发表一篇文章，说伊利诺伊州埃文斯通市一个典型家庭的年收入为50 000美元，因为这是平均收入。只有当实际情景不会与“平均值”偏离太多时（也就是说标准偏差很小时），才能说这个平均值是“典型值”。1月25日的最高温度可能属于这一情景。但在埃文斯通市，各个家庭的收入相差很大。一个家庭年收入为20 000美元或100 000美元可能要比50 000美元更为典型。回想上面的分析，当已知x在数组中时，A(n)为(n+1)/2。这并不是典型查找次数，因为介于1至n之间的所有查找次数都是同等典型的。这些考虑事项在涉及响应时间的算法中非常重要。例如，设想一个监测核电厂的系统。哪怕只有一种情景的响应时间极差，其结果也可能是灾难性的。因此，如果说平均响应时间为3秒，那非常重要的一点就是要知道，是因为所有响应时间都大约为3秒，还是因为大多数响应时间为1秒，而其中一部分为60秒。 最后一种时间复杂度分析是计算出基本运算的最小执行次数。对于一种给定算法，B(n)的定义为，对于输入规模n，该算法执行基本运算的最小次数。因此，B(n)称为算法的最佳情况时间复杂度（best-case time complexity），B(n)的求解称为最佳情况时间复杂度分析。和W(n)、A(n)的情景一样，如果T(n)存在，则B(n)=T(n)。下面求算法1.1的B(n)。 算法1.1的分析　最佳情况时间复杂度（顺序查找） 基本运算：将数组中的一个项目与x进行比较。 输入规模：n，数组中的项目数。 因为n≥1，所以至少要执行一遍循环。如果x=S[1]，无论n值如何，都将执行一遍循环。因此，B(n) = 1。 对于不存在所有情况时间复杂度的算法，我们执行最差情况分析和平均情况分析的频率要远高于最佳情况分析。平均情况分析的价值在于，它可以告诉我们，在对许多不同输入多次应用某一算法时，该算法将会耗用多长时间。比如，在反复使用一种排序算法对所有可能输入进行排序时，这一分析就非常有用。一般情况下，如果平均排序时间很不错，那偶尔一次的慢速排序是可以忍受的。在2.4节将会看到一种名为“快速排序”的算法，它的表现恰好就是这种情况。它是最流行的排序算法之一。前面曾经提到，平均情况分析对于监测核电厂的系统来说是不够的。在这种情况下，最差情况分析会更有用一点，因为它会给出算法耗费时间的上限。对于上面刚刚讨论的这两种情况来说，最佳情况分析都没有什么价值。 我们只讨论了对算法时间复杂度的分析。刚刚讨论的所有考虑事项同样适用于内存复杂度（memory complexity）的分析，内存复杂度分析算法在内存方面的效率。尽管本书中的大多数分析为时间复杂度分析，但我们偶尔会发现，进行内存复杂度分析也很有用。 一般情况下，复杂度函数（complexity function）可以是任何一个将正整数映射为非负实数的函数。如果对于某一具体算法，没有说明是时间复杂度还是内存复杂度，通常会使用标准函数符号来表示复杂度函数，比如f(n)和g(n)。 例1.6　下面的函数都是复杂度函数，因为它们都将正整数映射为非负实数。 1.3.2　理论应用 在应用算法分析的理论时，有时需要掌握以下信息：在实现该算法的实际计算机上执行基本运算、开销指令和控制指令所耗费的时间。“开销指令”是指诸如循环之前的初始化指令。这些指令的执行次数并不会随输入规模的增加而增加。“控制指令”是指为控制循环而递增索引之类的指令。这些指令的执行次数会随输入规模的增加而增加。基本运算、开销指令和控制指令都是算法及算法实现的性质。它们不是问题的性质。这就是说，对于同一问题的两个不同算法，这些性质通常是不一样的。 假定同一问题有两种算法，第一种算法的所有情况时间复杂度为n，第二种算法为n2。第一种算法的效率看起来更高一些。但假设给定一台计算机，它分别将两种算法的基本运算处理一遍，第一种算法耗费的时间是第二种算法的1000倍。这里所说的“处理”是指包含了执行控制指令的时间。因此，如果将第二种算法的基本运算处理一遍需要的时间为t，那将第一种算法的基本运算处理一遍将需要1000t。为简单起见，假设执行开销指令耗费的时间在两种算法中都可以忽略。这就是说，对于第一种算法来说，这台计算机处理n的一个实例所需要的时间为n×1000t，而对于第二种算法则为n2×t。必须求解以下不等式，才能确定第一种算法在什么情况更为高效： n2×t > n×1000t 不等式两边同时除以nt，得： n > 1000 如果实际应用的输入规模从来不会超过1000，那就应当实现第二种算法。在继续讨论之前应当指出，要准确判断某种算法何时快于另一算法，并不总是那么容易。有时必须使用近似方法来分析通过对比两种算法而得出的不等式。 回想一下，前面假设处理开销指令耗费的时间是可忽略的。如果事实并非如此，那在判断第一种方法何时更为高效时，这些指令也必须考虑在内。 1.3.3　正确性分析 本书中的“算法分析”是指时间或内存方面的效率分析。还有其他类型的分析。例如，可以分析算法的正确性：证明一种算法的确完成了它应当完成的任务。尽管我们有时会非正式地说明算法是正确的，有时也会加以证明，但关于正确性的详尽讨论，还请参阅Dijkstra（1976年）、Gries（1981年）或Kingston（1990年）的文献。