5

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

4

4 回答 4

3

这是你提出的一个非常好的观点。当然，您为此使用单元测试。

单元测试主要是测试代码结果的一种“方式”。你测试它是否做了它应该做的事情，并且当你希望它失败时它会失败。

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

一些消耗时间的单元测试的伪代码，您可能知道如何解决这个问题，但这是一种相当不错的测试方法：

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);

}

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

于 2009-01-28T11:00:14.750 回答
1

我在调整算法时遇到了类似的问题。我所做的是循环它，然后除以循环数和大 O 值。然后，我称之为“q”或“质量值”。有趣的是，这个值或多或少像我预期的那样是恒定的，并且对于错误的参数来说会更高一些。关键是，如果您查看 big-O 的定义，您会得到对除主要计算之外的“次要”计算的测量。它们通常是恒定的或具有较低的复杂性。就我而言，它有点线性，但仍然没有什么可考虑的。

我的建议是，计算这样的质量值。然后您可以查看是否有突然升高，这表明您上次更改的副作用打破了您的复杂性假设。

于 2009-01-28T11:40:11.157 回答
1

虽然时间方面很好地涵盖了 Filip 和 Josh 的答案，但空间问题更复杂，因为有问题的代码可能会在完成时释放它使用的任何内存和资源。因此，我猜想单元测试本身对于确定空间复杂度并不是特别有用。您将需要一个探针或其他一些与您的代码异步运行的监视器正在测试。

我想说在正在测试的代码中提供一些原位日志/跟踪将是最简单的解决方案，可能会从发布版本中删除。

于 2009-01-28T11:40:30.783 回答
1

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

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

于 2009-01-28T11:10:56.303 回答