What:
对数器是通过用大量测试数据来验证算法是否正确的一种方式。有时候,我们只能确定我们写出的算法在逻辑上大致正确的,不能一次性保证绝对的正确。特别是对于一些复杂的题目,例如贪心算法,往往无法在有限时间内用数学公式来推导证明我们程序的正确性。在线的OJ一般只会给出有数的几个简单的样例,可能我们的算法在这些简单的样例偶然通过了,但是在一些复杂的样例处却出现了问题。这时我们无法使用复杂的样例来分析调试我们的代码,人工设计样例来测试代码的效率又太低,而且不能确保考虑各种特殊情况。因此,能随机产生不同情况的数据的对数器就派上了用场。对数器,就是一个绝对正确的方法和能产生大量随机样例的随机器的组合。既然我们知道了绝对正确的方法,直接用这个方法不就好了嘛?请注意,算法追求的不是解决问题,而是高效率的解决问题。对于一个数组的排序,如果笔试中要求的时间复杂度是O(NlogN),但是你却写了一个冒泡排序的算法交上去了,这时OJ就会提示:超时。而在对数器中,我们要求的绝对正确的算法是没有时间和空间复杂度的限制的,唯一的要求是确保绝对正确。因为只有绝对正确,我们才能通过样例的比对,发现我们的代码是在哪里出了错误。
How:
1、有一个你要测的方法a;
2、实现一个简单可能复杂度高但是绝对正确的方法b;
3、实现一个随机样本产生器;
4、实现对比算法a和b的方法,把方法a运行结果和方法b运行结果比对多次来验证方法a是否正确;
5、如果有一个样本使得比对出错,打印样本分析是哪个方法出错;
如果当样本数量很多时比对测试依然正确,可以确定方法a已经正确。
Attention:
随机产生的样本要进行多次(至少上千次甚至上万次)的对比。算法b要保持正确性。