第二章 算法分析

原文：Chapter 2 Analysis of Algorithms

译者：飞龙

协议：CC BY-NC-SA 4.0

自豪地采用谷歌翻译

我们在前面的章节中看到，Java 提供了两种List接口的实现，ArrayList和LinkedList。对于一些应用，LinkedList更快；对于其他应用，ArrayList更快。

要确定对于特定的应用，哪一个更好，一种方法是尝试它们，并看看它们需要多长时间。这种称为“性能分析”的方法有一些问题：

  • 在比较算法之前，你必须实现这两个算法。
  • 结果可能取决于你使用什么样的计算机。一种算法可能在一台机器上更好；另一个可能在不同的机器上更好。
  • 结果可能取决于问题规模或作为输入提供的数据。

我们可以使用算法分析来解决这些问题中的一些问题。当它有效时，算法分析使我们可以比较算法而不必实现它们。但是我们必须做出一些假设：

  • 为了避免处理计算机硬件的细节，我们通常会识别构成算法的基本操作，如加法，乘法和数字比较，并计算每个算法所需的操作次数。
  • 为了避免处理输入数据的细节，最好的选择是分析我们预期输入的平均性能。如果不可能，一个常见的选择是分析最坏的情况。
  • 最后，我们必须处理一个可能性，一种算法最适合小问题，另一个算法适用于较大的问题。在这种情况下，我们通常专注于较大的问题，因为小问题的差异可能并不重要，但对于大问题，差异可能是巨大的。

这种分析适用于简单的算法分类。例如，如果我们知道算法A的运行时间通常与输入规模成正比，即n，并且算法B通常与n ** 2成比例，我们预计A比B更快，至少对于n的较大值。

大多数简单的算法只能分为几类。

  • 常数时间：如果运行时间不依赖于输入的大小，算法是“常数时间”。例如，如果你有一个n个元素的数组，并且使用下标运算符（[]）来访问其中一个元素，则此操作将执行相同数量的操作，而不管数组有多大。
  • 线性：如果运行时间与输入的大小成正比，则算法为“线性”的。例如，如果你计算数组的和，则必须访问n个元素并执行n - 1个添加。操作的总数（元素访问和加法）为2 * n -1，与n成正比。
  • 平方：如果运行时间与n ** 2成正比，算法是“平方”的。例如，假设你要检查列表中的任何元素是否多次出现。一个简单的算法是将每个元素与其他元素进行比较。如果有n个元素，并且每个元素与n - 1个其他元素进行比较，则比较的总数是n ** 2 - n，随着n增长它与n ** 2成正比。

2.1 选择排序

例如，这是一个简单算法的实现，叫做“选择排序”（请见 http://thinkdast.com/selectsort）：

  1. public class SelectionSort {
  3.     /**
  4.      * Swaps the elements at indexes i and j.
  5.      */
  6.     public static void swapElements(int[] array, int i, int j) {
  7.         int temp = array[i];
  8.         array[i] = array[j];
  9.         array[j] = temp;
  10.     }
  12.     /**
  13.      * Finds the index of the lowest value
  14.      * starting from the index at start (inclusive)
  15.      * and going to the end of the array.
  16.      */
  17.     public static int indexLowest(int[] array, int start) {
  18.         int lowIndex = start;
  19.         for (int i = start; i < array.length; i++) {
  20.             if (array[i] < array[lowIndex]) {
  21.                 lowIndex = i;
  22.             }
  23.         }
  24.         return lowIndex;
  25.     }
  27.     /**
  28.      * Sorts the elements (in place) using selection sort.
  29.      */
  30.     public static void selectionSort(int[] array) {
  31.         for (int i = 0; i < array.length; i++) {
  32.             int j = indexLowest(array, i);
  33.             swapElements(array, i, j);
  34.         }
  35.     }
  36. }

第一个方法swapElements交换数组的两个元素。元素的是常数时间的操作，因为如果我们知道元素的大小和第一个元素的位置，我们可以使用一个乘法和一个加法来计算任何其他元素的位置，这都是常数时间的操作。由于swapElements中的一切都是恒定的时间，整个方法是恒定的时间。

第二个方法indexLowest从给定的索引start开始，找到数组中最小元素的索引。每次遍历循环的时候，它访问数组的两个元素并执行一次比较。由于这些都是常数时间的操作，因此我们计算什么并不重要。为了保持简单，我们来计算一下比较的数量。

  • 如果start为0，则indexLowest遍历整个数组，并且比较的总数是数组的长度，我称之为n。
  • 如果start为1，则比较数为n - 1。
  • 一般情况下，比较的次数是n - start，因此indexLowest是线性的。

第三个方法selectionSort对数组进行排序。它从0循环到n - 1，所以循环执行了n次。每次调用indexLowest然后执行一个常数时间的操作swapElements。

第一次indexLowest被调用的时候，它进行n次比较。第二次，它进行n - 1比较，依此类推。比较的总数是

  1. n + n−1 + n−2 + ... + 1 + 0

这个数列的和是n(n+1)/2，它（近似）与n ** 2成正比；这意味着selectionSort是平方的。

为了得到同样的结果，我们可以将indexLowest看作一个嵌套循环。每次调用indexLowest时，操作次数与n成正比。我们调用它n次，所以操作的总数与n ** 2成正比。

2.2 大 O 表示法

所有常数时间算法属于称为O(1)的集合。所以，说一个算法是常数时间的另一个方法就是，说它是O(1)的。与之类似，所有线性算法属于O(n)，所有二次算法都属于O(n ** 2)。这种分类算法的方式被称为“大 O 表示法”。

注意：我提供了一个大 O 符号的非专业定义。更多的数学处理请参见 http://thinkdast.com/bigo。

这个符号提供了一个方便的方式，来编写通用的规则，关于算法在我们构造它们时的行为。例如，如果你执行线性时间算法，之后是常量算法，则总运行时间是线性的。∈表示“是…的成员”：

  1. f ∈ O(n) && g ∈ O(1) => f + g ∈ O(n)

如果执行两个线性运算，则总数仍然是线性的：

  1. f ∈ O(n) && g ∈ O(n) => f + g ∈ O(n)

事实上，如果你执行任何次数的线性运算，k，总数就是线性的，只要k是不依赖于n的常数。

  1. f ∈ O(n) && k 是常数 => kf ∈ O(n)

但是，如果执行n次线性运算，则结果为平方：

  1. f ∈ O(n) => nf ∈ O(n ** 2)

一般来说，我们只关心n的最大指数。所以如果操作总数为2 * n + 1，则属于O(n)。主要常数2和附加项1对于这种分析并不重要。与之类似，n ** 2 + 100 * n + 1000是O(n ** 2)的。不要被大的数值分心！

“增长级别”是同一概念的另一个名称。增长级别是一组算法，其运行时间在同一个大 O 分类中；例如，所有线性算法都属于相同的增长级别，因为它们的运行时间为O(n)。

在这种情况下，“级别”是一个团体，像圆桌骑士的阶级，这是一群骑士，而不是一种排队方式。因此，你可以将线性算法的阶级设想为一组勇敢，仗义，特别有效的算法。

2.3 练习 2

本章的练习是实现一个List，使用 Java 数组来存储元素。

在本书的代码库（请参阅 0.1 节）中，你将找到你需要的源文件：

  • MyArrayList.java包含List接口的部分实现。其中四个方法是不完整的；你的工作是填充他们。
  • MyArrayListTest.java包含 JUnit 测试，可用于检查你的工作。

你还会发现 Ant 构建文件build.xml。你应该可以从代码目录运行ant MyArrayList，来运行MyArrayList.java，其中包含一些简单的测试。或者你可以运行ant MyArrayListTest运行 JUnit 测试。

当你运行测试时，其中几个应该失败。如果你检查源代码，你会发现四条 TODO 注释，表示你应该填充的方法。

在开始填充缺少的方法之前，让我们来看看一些代码。这里是类定义，实例变量和构造函数。

  1. public class MyArrayList<E> implements List<E> {
  2.     int size;                    // keeps track of the number of elements
  3.     private E[] array;           // stores the elements
  5.     public MyArrayList() {
  6.         array = (E[]) new Object[10];
  7.         size = 0;
  8.     }
  9. }

正如注释所述，size跟踪MyArrayList中由多少元素，而且array是实际包含的元素的数组。

构造函数创建一个 10 个元素的数组，这些元素最初为null，并且size设为0。·大多数时候，数组的长度大于size，所以数组中由未使用的槽。

Java 的一个细节：你不能使用类型参数实例化数组；例如，这样不起作用：

  1. array = new E [10];

要解决此限制，你必须实例化一个Object数组，然后进行类型转换。你可以在 http://thinkdast.com/generics 上阅读此问题的更多信息。

接下来，我们将介绍添加元素到列表的方法：

  1. public boolean add(E element) {
  2.     if (size >= array.length) {
  3.         // make a bigger array and copy over the elements
  4.         E[] bigger = (E[]) new Object[array.length * 2];
  5.         System.arraycopy(array, 0, bigger, 0, array.length);
  6.         array = bigger;
  7.     } 
  8.     array[size] = element;
  9.     size++;
  10.     return true;
  11. }

如果数组中没有未使用的空间，我们必须创建一个更大的数组，并复制这些元素。然后我们可以将元素存储在数组中并递增size。

为什么这个方法返回一个布尔值，这可能不明显，因为它似乎总是返回true。像之前一样，你可以在文档中找到答案：http://thinkdast.com/colladd。如何分析这个方法的性能也不明显。在正常情况下，它是常数时间的，但如果我们必须调整数组的大小，它是线性的。我将在 3.2 节中介绍如何处理这个问题。

最后，让我们来看看get；之后你可以开始做这个练习了。

  1. public T get(int index) {
  2.     if (index < 0 || index >= size) {
  3.         throw new IndexOutOfBoundsException();
  4.     }
  5.     return array[index];
  6. }

其实get很简单：如果索引超出范围，它会抛出异常; 否则读取并返回数组的元素。注意，它检查索引是否小于size，大于等于array.length，所以它不能访问数组的未使用的元素。

在MyArrayList.java中，你会找到set的桩，像这样：

  1. public T set(int index, T element) {
  2.     // TODO: fill in this method.
  3.     return null;
  4. }

阅读set的文档，在 http://thinkdast.com/listset，然后填充此方法的主体。如果再运行MyArrayListTest，testSet应该通过。

提示：尽量避免重复索引检查的代码。

你的下一个任务是填充indexOf。像往常一样，你应该阅读 http://thinkdast.com/listindof 上的文档，以便你知道应该做什么。特别要注意它应该如何处理null。

我提供了一个辅助方法equals，它将数组中的元素与目标值进行比较，如果它们相等，返回true（并且正确处理null），则 返回。请注意，此方法是私有的，因为它仅在此类中使用；它不是List接口的一部分。

完成后，再次运行MyArrayListTest；testIndexOf，以及依赖于它的其他测试现在应该通过。

只剩下两个方法了，你需要完成这个练习。下一个是add的重载版本，它接受下标并将新值存储在给定的下标处，如果需要，移动其他元素来腾出空间。

再次阅读 http://thinkdast.com/listadd 上的文档，编写一个实现，并运行测试进行确认。

提示：避免重复扩充数组的代码。

最后一个：填充remove的主体。文档位于 http://thinkdast.com/listrem。当你完成它时，所有的测试都应该通过。

一旦你的实现能够工作，将其与我的比较，你可以在 http://thinkdast.com/myarraylist 上找到它。