3

在我目前的项目中，我正在测量用 Java 编写的算法的复杂性。我以渐近复杂度（预期结果）进行操作，并且我想通过与实际操作次数进行比较来验证预期。在我看来，每次操作都使用 Incrematation 有点笨拙。有没有更好的方法来衡量运营复杂性？

谢谢

编辑：更多信息

  • 算法可能在不同的机器上运行
  • 分治算法的某些部分可能会被预先缓存，因此该过程很可能比预期的要快
  • 对我来说，找出乘法常数（或加法常数）也很重要，这在渐近复杂性中没有考虑到
4

3 回答 3

2

是否有特别的理由不只测量 CPU 时间？时间实用程序或分析器将为您提供数字。只需使用足够的输入范围运行每个算法并捕获所花费的 cpu 时间（不是挂钟时间）。

于 2012-06-03T17:53:03.100 回答
1

在您想要测量执行时间的实际计算机上，getCurrentTimeMillis()。改变 N 参数，获得可靠的统计数据。做一个误差估计。你的基本最小二乘就可以了。

算法上的计数操作很好，但它的用途有限。不同的处理器以不同的速度做事。计算您实现的算法执行的表达式或语句的数量几乎是无用的。在算法中，您可以使用它来进行比较以进行调整，在您的实现中不再是这种情况，编译器/JIT//CPU 技巧将占主导地位。

如果您进行良好的测量，渐近行为应该非常接近计算/预期。

于 2012-06-03T19:02:01.080 回答
1

ByCounter可用于检测 Java（跨多个类）并计算 JVM 在运行时执行的字节码数量。

于 2014-07-10T14:56:46.517 回答