单元测试以验证时间复杂度

Question

是否有人使用单元测试来验证代码的时间/空间复杂度？

感谢

雨果

Answer 1

这就是你带来了一个非常好的点。当然你使用单元测试来做到这一点。

单元测试主要是测试代码结果的“方法”。你测试它是否做它应该做的事情，当它想要失败时它失败。

时间和空间是非常重要的两个变量，你可能“想”快速和低空间成本，但程序实际上是相反的，那么你有一个错误，这是单元测试的目的，发现错误并解决它们。

的耗时，你可能知道如何解决这个单元测试的一些伪代码，但这是测试它的一个相当不错的方法：当你想想看，你可以

Unit_Test_To_See_If_X_Takes_More_Than_Y_Seconds(int max_milli_seconds) 
{ 
    int current_millis = getMillis(); 

    do_operations_on_objects_and_functions(); 

    int millis_after_executions = getMillis(); 

    int elapes_millis = millis_after_execution - current_millis; 

    if (elapsed_millis > max_milli_seconds) 
     Assert(ERROR); 

} 

而且有太多的测试？不，你不能。即使你测试了“愚蠢”的东西，如果你没有测试一个结果并且一个错误发展了，这是否意味着它不存在只是因为你没有看到它或者你没有测试它？ :)

Answer 2

可能的解决方案是使用Filip的函数进行1次迭代测试，然后是100，然后是1000，然后是10000（等），并将结果绘制在图上以确定时间复杂度。或者使用数学推导每次运行之间的最高因数差异。但我不确定你如何测试空间。

我不认为输出将是一个简单的通过或失败，除非有一个现有的算法来推导出最高的因子（N^2等）并与之比较。

Answer 3

我有一个类似的问题，当我调整算法。我所做的就是循环它，然后除以循环数和大O值。然后，我称之为“q”或“质量值”。有趣的是，这个值或多或少像我预期的那样恒定，并且对于不好的参数有点高。重点是，如果你看一下big-O的定义，那么你可以得到一个主测量之外的“较少主导”计算的度量。它们通常是不变的或具有较低的复杂性。就我而言，这有点线性，但仍然没有什么可考虑的。

我的建议是，计算这样的质量值。然后你可以看到是否有突然的提升，表明你最后一次改变的副作用会打破你的复杂性假设。

Answer 4

而时间方面是相当不错覆盖菲利普的和Josh的回答，空间问题是比较复杂的，因为有问题的代码是容易释放它在完成使用的任何内存和资源。因此我猜测单元测试本身对于确定空间复杂性并不是特别有用。你需要一个探头或者其他一些显示器，在你的coude进行测试时异步运行。

我认为在代码提供一些原位日志/迹线被测试将是最简单的解决方案，可能从发布版本中删除。