第二章算法分析 · 數據結構思維中文版

# 第二章算法分析 > 原文：[Chapter 2 Analysis of Algorithms](http://greenteapress.com/thinkdast/html/thinkdast003.html) > 譯者：[飛龍](https://github.com/wizardforcel) > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻譯](https://translate.google.cn/) 我們在前面的章節中看到，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>）： ```java public class SelectionSort { /** * Swaps the elements at indexes i and j. */ public static void swapElements(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } /** * Finds the index of the lowest value * starting from the index at start (inclusive) * and going to the end of the array. */ public static int indexLowest(int[] array, int start) { int lowIndex = start; for (int i = start; i < array.length; i++) { if (array[i] < array[lowIndex]) { lowIndex = i; } } return lowIndex; } /** * Sorts the elements (in place) using selection sort. */ public static void selectionSort(int[] array) { for (int i = 0; i < array.length; i++) { int j = indexLowest(array, i); swapElements(array, i, j); } } } ``` 第一個方法`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`比較，依此類推。比較的總數是 ``` 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>。這個符號提供了一個方便的方式，來編寫通用的規則，關于算法在我們構造它們時的行為。例如，如果你執行線性時間算法，之后是常量算法，則總運行時間是線性的。`∈`表示“是...的成員”： ``` f ∈ O(n) && g ∈ O(1) => f + g ∈ O(n) ``` 如果執行兩個線性運算，則總數仍然是線性的： ``` f ∈ O(n) && g ∈ O(n) => f + g ∈ O(n) ``` 事實上，如果你執行任何次數的線性運算，`k`，總數就是線性的，只要`k`是不依賴于`n`的常數。 ``` f ∈ O(n) && k 是常數 => kf ∈ O(n) ``` 但是，如果執行`n`次線性運算，則結果為平方： ``` 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 注釋，表示你應該填充的方法。在開始填充缺少的方法之前，讓我們來看看一些代碼。這里是類定義，實例變量和構造函數。 ```java public class MyArrayList<E> implements List<E> { int size; // keeps track of the number of elements private E[] array; // stores the elements public MyArrayList() { array = (E[]) new Object[10]; size = 0; } } ``` 正如注釋所述，`size`跟蹤`MyArrayList`中由多少元素，而且`array`是實際包含的元素的數組。構造函數創建一個 10 個元素的數組，這些元素最初為`null`，并且`size`設為`0`。·大多數時候，數組的長度大于`size`，所以數組中由未使用的槽。 Java 的一個細節：你不能使用類型參數實例化數組；例如，這樣不起作用： ``` array = new E [10]; ``` 要解決此限制，你必須實例化一個`Object`數組，然后進行類型轉換。你可以在 <http://thinkdast.com/generics> 上閱讀此問題的更多信息。接下來，我們將介紹添加元素到列表的方法： ```java public boolean add(E element) { if (size >= array.length) { // make a bigger array and copy over the elements E[] bigger = (E[]) new Object[array.length * 2]; System.arraycopy(array, 0, bigger, 0, array.length); array = bigger; } array[size] = element; size++; return true; } ``` 如果數組中沒有未使用的空間，我們必須創建一個更大的數組，并復制這些元素。然后我們可以將元素存儲在數組中并遞增`size`。為什么這個方法返回一個布爾值，這可能不明顯，因為它似乎總是返回`true`。像之前一樣，你可以在文檔中找到答案：<http://thinkdast.com/colladd>。如何分析這個方法的性能也不明顯。在正常情況下，它是常數時間的，但如果我們必須調整數組的大小，它是線性的。我將在 3.2 節中介紹如何處理這個問題。最后，讓我們來看看`get`；之后你可以開始做這個練習了。 ```java public T get(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException(); } return array[index]; } ``` 其實`get`很簡單：如果索引超出范圍，它會拋出異常; 否則讀取并返回數組的元素。注意，它檢查索引是否小于`size`，大于等于`array.length`，所以它不能訪問數組的未使用的元素。在`MyArrayList.java`中，你會找到`set`的樁，像這樣： ```java public T set(int index, T element) { // TODO: fill in this method. return null; } ``` 閱讀`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> 上找到它。