第二章 算法分析
原文： 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）：
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
indexLowest
n
-
start
1
n - 1
- 一般情況下，比較的次數是
n - start
indexLowest
第三個方法
selectionSort
對數組進行排序。它從
循環到
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
你還會發現 Ant 建構檔案
build.xml
。你應該可以從代碼目錄運作
ant MyArrayList
，來運作
MyArrayList.java
，其中包含一些簡單的測試。或者你可以運作
ant MyArrayListTest
運作 JUnit 測試。
當你運作測試時，其中幾個應該失敗。如果你檢查源代碼，你會發現四條 TODO 注釋，表示你應該填充的方法。
在開始填充缺少的方法之前，讓我們來看看一些代碼。這裡是類定義，執行個體變量和構造函數。
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
設為
。·大多數時候，數組的長度大于
size
，是以數組中由未使用的槽。
Java 的一個細節：你不能使用類型參數執行個體化數組；例如，這樣不起作用：
array = new E [10]; 要解決此限制，你必須執行個體化一個
Object
數組，然後進行類型轉換。你可以在
http://thinkdast.com/generics上閱讀此問題的更多資訊。
接下來，我們将介紹添加元素到清單的方法：
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
；之後你可以開始做這個練習了。
public T get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
return array[index];
} 其實
get
很簡單：如果索引超出範圍，它會抛出異常; 否則讀取并傳回數組的元素。注意，它檢查索引是否小于
size
，大于等于
array.length
，是以它不能通路數組的未使用的元素。
在
MyArrayList.java
中，你會找到
set
的樁，像這樣：
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上找到它。
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)