是否有编程方式或eclipse插件来计算java方法的大O表示法

Question

是否有编程方式或eclipse插件来计算java方法的big-O表示法？

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 挑战的作者以众所周知的时间复杂度解决了他们的问题（他们手动分析了它）。当他们测量不同输入的解决方案的运行时间并将其与相同输入的解决方案的运行时间进行比较时，他们可以自动确定程序的时间复杂度（当然，考虑到您选择的编程语言）以及测量时间的某些偏差）。