Java算法分析工具

Question

10

我正在寻找一个可以计算Java函数Big O的算法分析工具。最理想的情况是将其作为构建过程的一部分，并与我的其他代码度量工具一起使用。即使在谷歌上搜索，我也找不到任何开源或商业工具。欢迎提供建议。

谢谢。

- Mansoor

1

这听起来像是关于代码Big O效率的编程问题，可能可以在stackoverflow.com/questions/480775上找到答案。 - Pascal Thivent

请见 https://cs.stackexchange.com/a/33858 - luqui

1个回答

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

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

- polygenelubricants · Accepted Answer

这不是通常可以自动完成的事情。大O分析不是一件简单的事情。

您确定您不是在寻找一个性能剖析器吗？

算法的大O分析通常是在设计阶段用铅笔和纸完成的。可能有些人编写简单的程序并使用自动化工具来测量和比较各种算法的原型实现，以帮助分析，但即使在这种高度假设的情况下，Java也不会是首选语言（也许是Haskell）。

对于用Java等实用语言编写的应用程序，通常需要在实现之前设计和分析算法，然后一旦您将其翻译成Java，请按需要进行性能剖析和优化。此时，您应该已经了解了算法的大O复杂度。

也许令您惊讶的是，假设您有某个算法的实现，然后您对其进行了优化，使其速度加倍。也许是三倍。也许是十倍。也许是一百万倍！

然而，从大O分析的角度来看，它的复杂度仍然相同！如果您有一个线性算法，则改进后速度提高了一百万倍的优化版本仍然是线性的！如果它是二次的，那么它仍将保持如此！

这是因为常数因子在渐近分析中是微不足道的（即随着输入大小向无穷大增长的速度有多快？）。一百万是一个很大的数字，但它仍然只是一个常数。

另一个复杂因素是渐进分析实际上具有阈值，在此之后界限生效。也就是说，对于较小的输入，这些界限可能会被打破，但从这个阈值开始，向无穷大方向，必须遵守这些界限。这使得通过测量进行自动分析非常困难，因为您不知道是否已经到达了阈值。

我建议阅读一些计算机科学基础教材，以了解更多关于这个主题的知识。

有趣的事实：无法确定一个程序是否会停止，这被称为停机问题。起初可能看起来很荒谬，但这有许多严重的理论后果。