数据结构基础之《（2）—对数器》
一、认识对数器
1、你在网上找到了某个公司的面试题，你想了好久，感觉自己会做，但是你找不到在线测试
2、你和朋友交流面试题，你想了好久，感觉自己会做，但是你找不到在线测试
3、你在网上做笔试，但是前几个测试用例都过了，突然一个巨大无比数据量来了，结果你的代码报错了，如此大的数据量根本看不出哪错了
二、对数器怎么用
1、你想要测的方法a（你设计的流程时间复杂度低，但是不知道对不对）
2、实现复杂度不好但是容易实现的方法b
3、实现一个随机样本产生器
4、把方法a和方法b跑相同的随机样本，看看得到的结果是否一样
5、如果有一个随机样本使得比较结果不一致，打印样本进行人工干预，改对方法a和方法b
6、当样本数量很多时，比对测试依然正确，可以确定方法a已经正确
例子：
//随机生成数组
public static int[] generateRandomArray(int maxSize, int maxValue) {
//Math.random() 返回[0,1)之间的小数
//Math.random() * N 返回[0,N)之间小数
//(int)(Math.random() * N) 返回[0, N-1]之间的整数
int arr[] = new int[(int) ((maxSize + 1) * Math.random())];
for (int i=0; i<arr.length; i++) {
//[-?, +?] 让负的某个值到正的某个值都有
arr[i]=(int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}