对数器的实现

代码实现与解析

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;
}