c# - 测试计算复杂度

Question

假设我有一些代码，并且计算复杂度遵守一些（代数）上限对我来说很重要。

例如，我可能有一个算法，当正确实现时在 n^2 中运行，但如果引入了错误，则在 n^3 中运行。测试将检查该方法是否实际上在 n^2 中运行，如果不是，则失败。

我的问题是，是否可以使用 MSTest 来完成此任务？

我可以看到，在引入了一堆数学代码之后，原则上可以将给定的方程拟合到经验测量和/或尝试找到极限。

或者，我想可能会生成图表以及最佳拟合，然后要求人类输入测试是否通过。

但这些真的是现实的吗？有没有做过类似的事情？

Answer 1

出于实际目的，可能无法进行此类测试。如果您尝试仅使用数学分析来比较两种算法，那么结果可能对实际目的没有用处。例如，您可能并不总是喜欢O(n ² )而不是O(n ³ )算法。您必须考虑隐藏常数。例如，从数学角度来看，具有 O(1000000 n ² ) 的算法仍然是 O(n ^{2 )。}但是这样的算法不会比 O(10 n ³ ) 算法好，后者在 n的值大于 100000 之前在 数学上是 O(n ^{3 )。但很多时候我们可能会处理远小于这个限制的输入大小。}

Answer 2

首先，您需要能够检测您的代码，以便您可以测量执行的操作数量。例如，如果您正在测试排序算法，您可以在每次调用比较函数时增加一个计数器。对于其他情况，这可能并不容易，例如所讨论的操作是整数乘法。

然后是“O(n^2)”描述的问题。一些算法具有不同的最佳、最差和平均情况复杂度。如果这适用于您，您将需要知道导致每种情况的输入并单独测试它们。

如果您要测试的是运行时间是 O(n^2) ，则很难验证。如您所知，big-O 谈论渐近复杂性，因此您需要运行非常长的测试，并且我想进行一些曲线拟合以查看它是否可以很好地被某些 ax^2 近似。如果您可以严格限制实际复杂性，似乎会更好，例如如果您知道当 x > 100 时操作数应始终低于 4x^2。然后您选择一些数据点，包括一些相当大的数据点那些，并检查它们是否低于估计值。当然，这意味着您可能必须更新测试以更改系数，同时保持 big-O 复杂度不变，但老实说，这听起来是件好事。