如何测量执行的操作数量

Question

3

在我的当前项目中，我正在测量用Java编写的算法的复杂性。我使用渐进复杂度（预期结果）进行操作，并希望通过与实际操作数的比较来验证预期结果。对于每个操作的增量使用似乎有点笨拙。是否有更好的方法来衡量操作复杂性？

谢谢。

编辑：更多信息

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

- malejpavouk

3个回答

1

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

- Brendan Cody-Kenny

1

在实际计算机上，您想要测量执行时间，可以使用getCurrentTimeMillis()。变化N参数，获取可靠的统计数据。进行误差估计。您的基本最小二乘法将很好地完成。

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

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

- Captain Giraffe

问题有点复杂。因为我希望解决分治算法，并且可能已经预先缓存了一些部分解决方案。因此，我期望的表现比渐近复杂度所示要好得多...而我想知道实际实现与数据相比，“预期复杂度”有多好。 - malejpavouk

是的，测量、测量和测量；不要抱太大希望。你可能想在问题中分享你的D&C。 - Captain Giraffe

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- easel · Accepted Answer

不采用只测量CPU时间的方法有什么特别的原因吗？使用time实用程序或分析器即可获得数字。只需对每个算法运行足够范围的输入，并捕获所花费的CPU时间（而不是墙钟时间）。