有没有编程方式或Eclipse插件可以计算Java方法的大O符号？

Question

是否有一种编程方式或 Eclipse 插件，可以计算 Java 方法的大 O 表示法（Big-O notation）？

- Amgad Hanafy

---

可能会有一个插件，但如果没有，那么您可以尝试跟踪方法调用并手动计算（或至少近似）运行复杂度。 - Tim Biegeleisen

我还没有尝试过它们，但是看起来metrics和checkstyle插件都具有圈复杂度计算功能。 - guleryuz

这通常是不可能的。在许多情况下，证明算法的复杂性需要很多聪明才智，而程序实际上无法提供。 - Louis Wasserman

为什么会有人关闭这个问题？这似乎是你想要提出并得到正确回答的问题。显然，这个问题表明了对渐近分析的误解，但这并不意味着它不值得得到一个好的回答，让其他人受益。@LouisWasserman - 为什么不把你的评论转化成稍微更详细的答案呢？ - Mike Dinescu

@CoderinoJavarino，圈复杂度和运行时复杂度分析是两个非常不同的指标。正如Louis Wasserman所评论的那样，在除了最基本的情况之外，确定算法的运行时复杂度将需要一些抽象推理，这是计算机无法实现的 - 参见停机问题，这是不可判定的 - 这就是为什么。 - Mike Dinescu

Answer 1

没有这样的插件，即使有，它也只是一个近似值。换句话说，即使确定程序是否会完成运行也是棘手的 - 请参见停机问题。

现在，关于可能的近似值。假设您有一个插件，可以使用小数据集（例如N = 1000）和中等数据集（例如N = 10000）测试您的程序。如果您的程序在中等数据集上运行时间比小数据集长10倍，则插件应该得出结论，您的程序是O(N)，对吗？不完全是这样。最好/平均/最坏情况如何？例如，快速排序的最坏情况是O(N^2)，但通常被认为是O(N*logN)排序算法。因此，如果插件遇到特殊输入，它将给出错误的结果。常数呢？运行时间为O(N + k*logN)的程序被认为是O(N)，但如果常数k相对于N足够大，插件将无法得出这个结论，等等。

关于您的评论：

如果有人尝试过Codility的挑战，他们会使用大O符号评估您的解决方案的性能，并且我确信他们没有手动计算，这就是我问这个问题的原因。 Codility挑战的作者拥有其问题的解决方案和已知时间复杂度（他们手动分析了它）。当他们测量您的解决方案在各种输入下的运行时间并将其与相同输入的他们解决方案的运行时间进行比较时，他们可以“自动”确定您的程序的时间复杂度（当然，考虑到您选择的编程语言和测量时间的某些偏差）。

- Miljen Mikic