【左程云算法03】對數器算法和數據結構大致分類

對數器的實現

代碼實現與解析

1. 隨機樣本生成器 (randomArray)

2. 核心驅動邏輯 (main?方法)

3. 輔助函數 (copyArray?和?sameArray)

對數器的威力

算法和數據結構簡介?編輯

1. 硬計算類算法 (Hard Computing)

2. 軟計算類算法 (Soft Computing)

核心觀點

一個宏觀的數據結構分類

1. 連續結構 (Continuous Structure)

2. 跳轉結構 (Jumping Structure)

視頻鏈接

算法講解005【入門】對數器-驗證的重要手段

算法講解008【入門】算法和數據結構簡介

對數器的實現

對數器的本質，就是通過大規模的隨機樣本測試，來對比我們實現的“精巧算法”和一個“絕對正確”的暴力方法，從而驗證我們算法的正確性。

構建一個對數器的完整流程分為以下六步：

你要有一個想測的方法 a（最優解）
這是我們自己實現的、希望驗證其正確性的算法。
實現一個復雜度不好但是容易實現的方法 b（暴力解）
這個方法是我們的“真理標桿”。我們不要求它性能好，但必須保證它的邏輯是絕對正確的。通常，我們會用最直觀、最暴力的方式來實現它。
實現一個隨機樣本產生器
我們需要一個函數，能夠生成各種隨機情況的測試數據（例如，長度隨機、值也隨機的數組）。
把方法 a 和方法 b 跑相同的輸入樣本，看看得到的結果是否一樣
這是對數器的核心對比環節。對于同一個隨機樣本，分別用方法 a 和方法 b 去處理。
如果有某個隨機樣本使得比對結果不一致，打印出這個出錯的樣本進行人工干預，改對方法 a 和方法 b
一旦發現不一致，就意味著我們的方法 a 存在 bug。對數器會自動捕獲這個導致錯誤的“反例”，我們就可以用這個具體的樣本去輕松地進行 debug。
當樣本數量很多時比對依然正確，可以確定方法 a（最優解）已經正確。
經過成千上萬，甚至幾十萬次隨機樣本的“轟炸”都未曾出錯，我們就可以非常有信心地認為，我們的算法 a 是正確的。

代碼實現與解析

下面，我們結合截圖中的 Java 代碼，來一步步拆解對數器的具體實現。這里的例子是用來同時驗證我們寫的多個排序算法是否正確。

1. 隨機樣本生成器 (randomArray)

負責源源不斷地提供測試數據。

// 得到一個隨機數組，長度是n
// 數組中每個數，都在1~v之間，隨機得到
public static int[] randomArray(int n, int v) {int[] arr = new int[n];for (int i = 0; i < n; i++) {// Math.random() -> double -> [0,1)的一個小數// Math.random() * v -> double -> [0,v)的一個小數// (int)(Math.random() * v) -> int -> 0 1 2 3 ... v-1，等概率的！// (int)(Math.random() * v) + 1 -> int -> 1 2 3 .... v，等概率的！arr[i] = (int) (Math.random() * v) + 1;}return arr;
}

這個函數接收最大長度?n?和最大值?v，生成一個長度和值都在指定范圍內的隨機數組。注釋清晰地解釋了?Math.random()?如何通過一系列變換，生成我們需要的?[1, v]?范圍內的隨機整數。

2. 核心驅動邏輯 (main?方法)

這里是對數器的“發動機”，它組織了整個測試流程。

// 為了驗證
public static void main(String[] args) {// 隨機數組最大長度int N = 100;// 隨機數組每個值，在1~V之間隨機int V = 1000;// 測試次數int testTimes = 50000;System.out.println("測試開始");for (int i = 0; i < testTimes; i++) {// 隨機得到一個長度，長度在[0~N-1]int n = (int) (Math.random() * N);// 得到隨機數組int[] arr = randomArray(n, V);// 拷貝數組，確保每個排序算法處理的是相同的原始數據int[] arr1 = copyArray(arr);int[] arr2 = copyArray(arr);int[] arr3 = copyArray(arr);// 分別用不同方法排序selectionSort(arr1);bubbleSort(arr2);insertionSort(arr3);// 對比排序結果if (!sameArray(arr1, arr2) || !sameArray(arr1, arr3)) {System.out.println("出錯了!");// 當出錯時，可以把原始樣本arr打印出來，// 方便把這個例子帶入到每個方法去debug！}}System.out.println("測試結束");
}

關鍵點解析：

在后續的很多題目中，對數器都會是我們驗證復雜算法（如動態規劃、貪心等）的得力助手。

算法和數據結構簡介

循環測試：通過?testTimes?控制測試次數，量級越大，覆蓋的樣本情況就越全面，結果越可靠。
拷貝數組：copyArray(arr)?這一步至關重要！因為排序是原地操作，會修改原數組。如果不拷貝，那么第一個排序（selectionSort）完成后，arr2?和?arr3?拿到的將是一個有序數組，測試就失去了意義。必須保證每個待測算法都工作在完全相同的、未經修改的原始樣本上。

結果比對：if (!sameArray(arr1, arr2) || !sameArray(arr1, arr3))?負責檢查。這里我們讓多個排序算法互相驗證

3. 輔助函數 (copyArray?和?sameArray)

這兩個是保證對數器能正確運行的工具函數。

copyArray：

。如果其中任何兩個的結果不一致，就說明至少有一個算法出了問題。

// 為了驗證
public static int[] copyArray(int[] arr) {int n = arr.length;int[] ans = new int[n];for (int i = 0; i < n; i++) {ans[i] = arr[i];}return ans;
}```
功能很簡單：創建一個和原數組一模一樣的新數組，避免引用傳遞導致的問題。**`sameArray`：**
```java
// 為了驗證
public static boolean sameArray(int[] arr1, int[] arr2) {// 這里可以先補充長度是否相等的判斷int n = arr1.length;for (int i = 0; i < n; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;
}