[数据结构与算法]什么是对数器？

什么是对数器？
对数器的概念：

1.有一个你想要测的方法a；
2.实现一个绝对正确但是复杂度不好的方法b；
3.实现一个随机样本产生器；
4.实现对比算法a和b的方法；
5.把方法a和方法b比对多次来验证方法a是否正确；
6.如果有一个样本使得比对出错，打印样本分析是哪个方法出错；
7.当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

对数器的作用

对数器是通过用大量测试数据来验证算法是否正确的一种方式。. 在算法笔试的时候，我们经常只能确定我们写出的算法在逻辑上是大致正确的，但是谁也不能一次性保证绝对的正确。特别是对于一些复杂的题目，例如贪心算法，我们往往无法在有限时间内用数学公式来推导证明我们程序的正确性。. 而且在线的OJ一般只会给出有数的几个简单的 samples ，可能我们的算法在这些简单的 samples 偶然通过了，但是在一些复杂的 samples 处却出现了问题。

对数器的用法
下面以冒泡排序为例，用C++代码描述对数器的用法

#include<iostream>
#include<cstdlib>
#include <algorithm>
#include<vector>
#include<ctime>
using namespace std;
class Logarithmic_detector {
public:
	Logarithmic_detector(int MaxSize,int MaxNum):MaxSize(MaxSize),MaxNum(MaxNum){}
	void bubbleSort();
	void assignment();//复制当前数组的样本
	void rightSort();用内置的排序算法排序
	void printArray();
	bool isEquals();//判断两个数组是否完全相同
	void generateRandomArray();//生成一个随机大小，最大数随机的数组
protected:
	int MaxSize;//最大测试容量
	int MaxNum;//最大测试数据
	vector<int> array;
	vector<int>array1;
	vector<int>array2;
};

void Logarithmic_detector::bubbleSort()
{
	if (array1.empty()||array1.size()<=2)
		return;
	for (unsigned int end = array1.size()-1; end >=0&&end< UINT_MAX; end--) {
		for (unsigned int i = 1; i <=end; i++) {
			if (array1[i] < array1[i - 1])
			swap(array1[i], array1[i-1]);
		}
	}
}
bool Logarithmic_detector::isEquals()
{
	if (array1.size() != array2.size())
		return false;
	if (array1.empty() || array2.empty())
		return false;
	for (int i = 0; i < MaxSize; i++) {
		if (array1[i] != array2[i])
			return false;
	}
	if (array1.empty() && array2.size())
		return true;
	return true;
}
void Logarithmic_detector::rightSort()
{
	sort(array2.begin(), array2.end());
}

void Logarithmic_detector::printArray()
{
	cout <<endl<< "随机初始值:\t";
	for (unsigned int i = 0; i < array.size(); i++)
		cout <<array[i] << " ";
	cout <<endl<<"自定义排序:\t";
	for (unsigned int i = 0; i < array.size(); i++)
		cout<< array1[i] << " ";
	cout << endl<< "内置的sort排序:\t";
	for (unsigned int i = 0; i < array.size(); i++)
		cout << array2[i] << " ";
}
void Logarithmic_detector::assignment() {
	array1 = array;
	array2 = array;
}
void Logarithmic_detector::generateRandomArray()
{
	array.clear();//每次插入前都做清空处理
	for (int i = 0; i < MaxSize; i++)
		array.push_back(rand() % MaxNum - rand() % MaxNum);
}
int main() {
	srand((unsigned)time(nullptr));
	int testTimes = 500000;//测试次数
	bool flag = true;
	Logarithmic_detector detector(20, 20);
	for (int i = 0; i < testTimes; i++) {
		detector.generateRandomArray();
		detector.assignment();
		detector.bubbleSort();
		detector.rightSort();
		if (!detector.isEquals()) {
			flag = false;
			break;
		}
	}
	if (flag == false) {
		cout << "Error:抱歉！匹配失败" << endl;
		return 0;
	}
	cout << "Success,测试已通过!" << endl;
	detector.printArray();
}

运行结果：

因为便于观察，所以测试代码里就选取了基数较小的数据充当容量和随机范围，运行了大约十几秒