算法学习笔记——对数器

对数器

对数器的实现：

1. 你想要测的方法a（最优解）
2. 实现复杂度不好但是容易实现的方法b（暴力解）
3. 实现一个随机样本产生器（长度也随机、值也随机）
4. 把方法a和方法b跑相同的输入样本，看看得到的结果是否一样
5. 如果有一个随机样本使得比对结果不一致，打印这个出错的样本进行人工干预，改对方法a和方法b
6. 当样本数量很多时比对测试依然正确，可以确定方法a（最优解）已经正确。

关键是第5步，找到一个数据量小的错误样本，便于你去带入debug

然后把错误例子带入代码一步一步排查

Print大法、断点技术都可以

对数器的门槛其实是比较高的，因为往往需要在两种不同思路下实现功能相同的两个方法，暴力一个、想象中的最优解是另一个。

以后的很多题目都用到对数器，几乎可以验证任何方法，尤其在验证贪心、观察规律方面很有用。

public static void main(String[] args){
    // 随机数组最大长度
    int N = 100;
    // 随机数组每个值，在1~V之间随机
    int V = 1000;
    // testTimes : 测试次数
    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("出错了！");
            // 当有错了
            // 打印是什么例子，出错的
            // 打印三个功能，各自排序成了什么样
            // 可能要把例子带入
        }
    }
    System.out.println("测试结束");
}

// 为了验证
// 得到一个随机数组，长度是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)一个小数，0.37463473126、0.001231231
        // 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;
}

// 为了验证
// 拷贝数组
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[j];
    }
    return ans;
}

// 为了验证
// 验证数组是否一样
public static boolen 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;
}

....