5.2. 算法比较¶

5.2.1. 算法比较¶

5.2.1.1. 引言¶

就求解某个问题的两种算法而言，如何在效率上加以比较？我们可以把两种算法都实现为计算机程序，然后在适当范围的输入上运行它们，测量每个程序使用了多少相关资源。这种做法常常不能令人满意，原因有四。第一，你充其量只想保留其中一个算法，却要为两个算法的编程和测试付出努力。第二，在做实验比较时，总有可能其中一个程序比另一个 "写得更好"，因而底层算法的相对优劣并没有真正由其实现体现出来。当程序员对涉及的算法有所偏爱时，这种情况很容易发生。第三，实验测试用例的选择可能不公平地偏向某个算法。第四，你可能会发现，即便是两个算法中较好的那个，也不在你的资源预算之内。那样的话，你就得用实现了新算法的又一个程序，把整个过程从头再来一遍。可是，你怎么知道是否存在能满足资源预算的算法？也许这个问题本身就太难，任何实现都无法控制在预算之内。

使用渐近分析常常可以避免这些问题。渐近分析度量的是当输入规模变大时，算法（或其作为程序的实现）的效率。它实际上是一种估算技术，对于两个程序的相对优劣给不出什么结论，比如一个程序只是总比另一个 "稍快一点"的情形。然而，事实证明，对于必须判断某个特定算法是否值得考虑实现的计算机科学家来说，渐近分析是有用的。

程序最关键的资源通常是其运行时间。不过，你不能只关注运行时间，还必须关心其他因素，比如运行程序所需的空间（主存和磁盘空间都在内）。典型做法是：分析算法（或算法以程序形式实例化后）所需的时间，以及 数据结构 所需的空间。

影响程序运行时间的因素很多。有些因素与程序编译和运行所处的环境有关，比如计算机的 CPU、总线和外设硬件的速度。与其他用户争夺计算机（或网络）的资源，可能让程序慢得像爬行一样。程序设计语言以及特定编译器所生成代码的质量，也会有显著影响。把算法转换为程序的程序员其"编码效率"如何，同样可能带来巨大影响。

如果你要让程序在特定计算机上于时间和空间约束之内正常工作，所有这些因素都可能相关。然而，这些因素没有一个涉及两种算法或数据结构之间的差异。公平地说，如果想比较由求解同一问题的两个算法分别得到的两个程序，就应当用同一编译器编译它们，并在相同条件下在同一台计算机上运行。在为每个程序付出的编程投入上，还应尽量花费同等的心力，使两个实现"同等高效"。在这个意义上，前面提到的所有因素都应当从比较中抵消掉，因为它们对两种算法的影响是同等的。

如果你真正想理解算法的运行时间，那么比起机器速度、程序设计语言、编译器等因素，还有一些更合适的考虑因素。理想情况下，我们会在标准的基准测试条件下度量算法的运行时间。然而，除了在某一台计算机上运行算法的实现之外，我们没有可靠计算运行时间的办法。唯一的替代方案，就是用某种别的度量来代替运行时间。

5.2.1.2. 基本操作与输入规模¶

在估算算法性能时，首要考虑的是：为处理一定规模的输入，算法需要执行多少次基本操作。 "基本操作"和"规模"这两个说法都相当含糊，取决于被分析的算法。规模常常是指所处理输入的数目。例如，比较排序算法时，问题规模通常用待排序记录的数目来度量。基本操作必须具有这样的性质：其完成所需的时间不依赖于操作数的具体取值。对两个整型变量做加法或比较，就是大多数程序设计语言中基本操作的例子。对一个含 \(n\) 个整数的数组求和则不是，因为成本取决于 \(n\) 的值（即输入的规模）。

Example 5.2.1

考虑一个简单算法，解决在含 \(n\) 个整数的数组中寻找最大值的问题。该算法依次查看每个整数，保存到目前为止所见最大值的位置。这个算法称为 最大值顺序查找 ，由下面的函数说明：

Java
C++

    // Return position of largest value in integer array A
    static int largest(int[] A) {
        int currlarge = 0;             // Position of largest element seen
        for (int i=1; i<A.length; i++) // For each element
            if (A[currlarge] < A[i])     //   if A[i] is larger
                currlarge = i;            //     remember its position
        return currlarge;              // Return largest position
    }

/** Return position of largest value in integer array A */
int largest(int A[], int size) {
  int currlarge = 0;             // Position of largest element seen
  for (int i=1; i<size; i++)     // For each element
    if (A[currlarge] < A[i])     //   if A[i] is larger
       currlarge = i;            //     remember its position
  return currlarge;              // Return largest position
}

这里，问题规模是 A.length ，即数组 A 中存储的整数的个数。基本操作是把一个整数的值与到目前为止所见最大值进行比较。可以合理地假定，做一次这样的比较花费固定的时间，与两个整数的取值或它们在数组中的位置无关。

由于影响运行时间的最重要因素通常是输入的规模，对给定的输入规模 \(n\) ，我们常把运行算法的时间 \(\mathbf{T}\) 表示为 \(n\) 的函数，记作 \(\mathbf{T}(n)\) 。我们总是假定 \(\mathbf{T}(n)\) 是非负值。

设 \(c\) 为函数 largest 中比较两个整数所需的时间。眼下我们并不关心 \(c\) 的精确值是多少。我们也不关心变量 \(i\) 自增所需的时间（数组中每个值都要做一次自增）、找到更大值时实际执行赋值所需的时间，以及初始化 currlarge 所花的那一点点额外时间。我们只想要执行该算法所需时间的一个合理近似。因此，运行 largest 的总时间约为 \(cn\) ，因为我们必须做 \(n\) 次比较，每次比较耗时 \(c\) 。我们说函数 largest （推广开来，任何典型实现的最大值顺序查找算法）的运行时间由如下方程表示：

\[\mathbf{T}(n) = cn.\]

这个方程描述了最大值顺序查找算法运行时间的增长率。

5.2.1.3. 增长率¶

算法的增长率是指：当算法输入的规模增大时，算法成本增长的速度。下图给出了六条方程的图象，每条方程都想描述某个特定程序或算法的运行时间。图中展示了能够代表典型算法的多种增长率。

标记为 \(10n\) 和 \(20n\) 的两条方程画出来是直线。增长率为 \(cn\) （其中 \(c\) 为任意正常数）常被称为线性增长率或线性运行时间。这意味着随着 \(n\) 的值增大，算法的运行时间按同样的比例增长。当 \(n\) 的值翻倍时，运行时间大致也翻倍。运行时间方程的最高次项含有 \(n^2\) 因子的算法，称为具有二次增长率。图中标记为 \(2n^2\) 的线表示二次增长率。标记为 \(2^n\) 的线表示的是指数增长率。这个名称源于 \(n\) 出现在指数位置。标记为 \(n!\) 的线同样按指数级增长。

正如你从图中所见，运行时间成本为 \(\mathbf{T}(n) = 10n\) 的算法与成本为 \(\mathbf{T}(n) = 2n^2\) 的算法之间的差异，随着 \(n\) 增大而变得极其巨大。对于 \(n > 5\) ，运行时间为 \(\mathbf{T}(n) = 2n^2\) 的算法就已经慢得多，尽管 \(10n\) 的常数因子比 \(2n^2\) 更大。比较标记为 \(20n\) 和 \(2n^2\) 的两条曲线可以看出，改变其中一个方程的常数因子，只会移动两条曲线相交的位置。对于 \(n>10\) ，成本为 \(\mathbf{T}(n) = 2n^2\) 的算法比成本为 \(\mathbf{T}(n) = 20n\) 的算法更慢。该图还显示，方程 \(\mathbf{T}(n) = 5 n \log n\) 的增长比 \(\mathbf{T}(n) = 10 n\) 和 \(\mathbf{T}(n) = 20 n\) 都快一些，但远不及方程 \(\mathbf{T}(n) = 2n^2\) 增长得快。对于常数 \(a, b > 1, n^a\) 的增长快于 \(\log^b n\) 或 \(\log n^b\) 。最后，对于哪怕并不大的 \(n\) 值，成本为 \(\mathbf{T}(n) = 2^n\) 或 \(\mathbf{T}(n) = n!\) 的算法都昂贵得无法承受。注意，对于常数 \(a, b \geq 1, a^n\) 的增长快于 \(n^b\) 。

从下表中，我们可以进一步洞察各种算法相对增长率的高低。表中列出了典型算法中出现的大多数增长率，以及一些有代表性的输入规模。我们再一次看到，增长率对算法消耗的资源有着巨大的影响。

Table 5.2.1 )

有代表性的增长率的成本。

\[\begin{split}\begin{array}{c|c|c|c|c|c|c|c} \mathsf{n} & \mathsf{\log \log n} & \mathsf{\log n} & \mathsf{n} & \mathsf{n \log n} & \mathsf{n^2} & \mathsf{n^3} & \mathsf{2^n}\\ \hline \mathsf{16} & \mathsf{2} & \mathsf{4} & \mathsf{2^{4}} & \mathsf{4 \cdot 2^{4} = 2^{6}} & \mathsf{2^{8}} & \mathsf{2^{12}} & \mathsf{2^{16}}\\ \mathsf{256} & \mathsf{3} & \mathsf{8} & \mathsf{2^{8}} & \mathsf{8 \cdot 2^{8} = 2^{11}} & \mathsf{2^{16}} & \mathsf{2^{24}} & \mathsf{2^{256}}\\ \mathsf{1024} & \mathsf{\approx 3.3} & \mathsf{10} & \mathsf{2^{10}} & \mathsf{10 \cdot 2^{10} \approx 2^{13}} & \mathsf{2^{20}} & \mathsf{2^{30}} & \mathsf{2^{1024}}\\ \mathsf{64 {\rm K}} & \mathsf{4} & \mathsf{16} & \mathsf{2^{16}} & \mathsf{16 \cdot 2^{16} = 2^{20}} & \mathsf{2^{32}} & \mathsf{2^{48}} & \mathsf{2^{64 {\rm K}}}\\ \mathsf{1 {\rm M}} & \mathsf{\approx 4.3} & \mathsf{20} & \mathsf{2^{20}} & \mathsf{20 \cdot 2^{20} \approx 2^{24}} & \mathsf{2^{40}} & \mathsf{2^{60}} & \mathsf{2^{1 {\rm M}}}\\ \mathsf{1 {\rm G}} & \mathsf{\approx 4.9} & \mathsf{30} & \mathsf{2^{30}} & \mathsf{30 \cdot 2^{30} \approx 2^{35}} & \mathsf{2^{60}} & \mathsf{2^{90}} & \mathsf{2^{1 {\rm G}}}\\ \end{array}\end{split}\]

CSci 2101 数据结构

第 5 章算法分析

5.2. 算法比较¶

5.2.1. 算法比较¶

5.2.1.1. 引言¶

5.2.1.2. 基本操作与输入规模¶

5.2.1.3. 增长率¶

5.2.2. 增长率排序练习¶

CSci 2101 数据结构

第 5 章 算法分析

5.2. 算法比较¶

5.2.1. 算法比较¶

5.2.1.1. 引言¶

5.2.1.2. 基本操作与输入规模¶

5.2.1.3. 增长率¶

5.2.2. 增长率排序练习¶

第 5 章算法分析