测试计算复杂度
本文关键字：计算复杂度 测试 | 更新日期: 2023-09-27 18:09:12
假设我有一些代码，对我来说，计算复杂度观察一些(代数)上界是很重要的。
例如，我可能有一个算法，当正确实现时运行在n^2，但如果引入一个错误，运行在n^3。测试将检查方法是否在n^2内运行，如果不是，则失败。
我的问题是，有可能用MSTest完成这个吗?
我可以看到，在引入一堆数学代码之后，原则上有可能将给定的方程拟合到经验测量和/或试图找到极限。
或者，我想象有可能生成图形，连同最佳拟合，然后要求人类输入测试是否通过。
但是这些都是现实的吗?类似的事情发生过吗?
出于实际目的，可能不可能进行这样的测试。如果您试图通过单独使用数学分析来比较两种算法，那么结果可能对实际目的没有用处。例如，您可能并不总是更喜欢O(n2)而不是O(n3)算法。你必须考虑隐藏的常数。例如，从数学角度来看，具有O(1000000n 2)的算法仍然是O(n2)。但是这样的算法不会比O(10n 3)算法更好，在数学上是O(n3)，直到n的值大于100000。但是很多时候我们可能会处理远小于这个限制的输入大小。
首先，您需要能够检测您的代码，以便度量执行的操作的数量。例如，如果您正在测试排序算法，则可以在每次调用比较函数时增加计数器。在其他情况下，这可能不容易，比如所讨论的操作是整数乘法。
接下来的问题是"O(n^2)"描述了什么。一些算法具有不同的最佳、最差和平均情况复杂度。如果这适用于你，你需要知道导致每种情况的输入是什么，并分别测试它们。
如果你想测试的是运行时是O(n^2)，这将很难验证。正如你所知，大0讨论的是渐近复杂性所以你需要进行很长的测试我想做一些曲线拟合看看它是否能很好地近似于ax^2。如果你能对实际的复杂度有一个严格的限定，就好像你知道当x> 100时，操作的次数应该总是低于4x^2。然后选择一些数据点，包括一些相当大的数据点，并检查它们是否低于估计。当然，这意味着您可能必须更新您的测试，以修改系数，同时保持大o复杂度不变，但老实说，这听起来像是一件好事。