是否有编程方式或Eclipse插件来为Java方法计算大O表示法 [英] Is there a programmatic way or eclipse plugin to calculate big O notation for java method

问题描述

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

Is there a programmatic way or eclipse plugin to calculate big-O notation for java method ?

推荐答案

不，没有不是这样的插件，如果是的话，那将仅仅是一个近似值。也就是说，即使确定该程序是否将完成运行也很棘手-请参见停止问题。

No, there isn't such plugin, and if it was, it would be a mere approximation. Namely, even determining whether the program will finish running or not is intractable - see Halting problem.

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

Now, about the possible approximation. Let's say you have a plugin that tests your program with a small dataset (e.g. N = 1000) and a medium dataset (e.g. N = 10000). If your program runs 10 times longer with a medium dataset compared to a small dataset, plugin should conclude that your program is O(N), right? Not quite. What about best/average/worst case? For example, quicksort's worst case is O(N^2), but it is generally considered as O(N*logN) sorting algorithm. Therefore, if the plugin hits the special input, it will give a wrong result. What about constants? The program whose running time is O(N + k*logN) is considered O(N), but if a constant k is large enough compared to N, plugin would not be able to reach this conclusion, etc.

关于您的评论：

如果有人尝试了挑战性挑战
，他们就是评价您的解决方案
相对于使用大O表示法的性能，我确定他们不是手动计算
，这就是为什么我问这个问题。

If anybody tried codility challenges they are evaluation your solution against performance using big O notation , and I'm sure that they are not calculation it manually, that's why I'm asking this question.

作者的挑战性以众所周知的时间复杂度（他们手动分析）解决了他们的问题。当他们测量各种输入的解决方案的运行时间并将其与相同输入的解决方案的运行时间进行比较时，他们可以自动确定程序的时间复杂度（当然，记下您选择的编程语言以及所测得的时间的某些偏差）。

Authors of Codility challenges have solutions of their problems with a well-known time complexity (they analyzed it manually). When they measure the running time of your solution for various input and compare it with a running time of their solutions for the same input, they can automatically determine the time complexity of your program (of course, taking into account the programming language you have chosen and certain deviations of the measured time).

这篇关于是否有编程方式或Eclipse插件来为Java方法计算大O表示法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！