是否有任何工具可以确定Big-O复杂性的执行代码分析？

Question

我没有看到任何东西，我怀疑定义<！>“; n <！>的困难;因为通常用于分析复杂函数，所以不止一个或两个变量用于定义。

有关于圈复杂度的分析工具，但有时间（和/或空间）复杂性吗？如果是这样的话，如果没有，为什么不呢？这是不可行的吗？不可能？有人还没有找到它吗？

理想情况下，应用程序的整体复杂性（定义不同的可能<！>; n <！> s）以及应用程序中的每个方法都有类似的东西

编辑：因此，由于停止问题，似乎无法获得确切的解决方案，是某种启发式近似可能吗？我意识到，出于实际目的，一个好的分析器将提供更多有用的信息，但它似乎是一个有趣的问题。

另外，如何计算某个程序子集？

Answer 1

不幸的是，这个问题被称为暂停问题 ......

Answer 2

不，由于停止问题，这是不可能的。

如果您想要改进应用程序，可以考虑进行性能分析。它可以让你指出实际花费最多的时间。这样，您就不会花时间优化仅在小型数据集上运行的O（n ^ 3）算法。

Answer 3

一些但是：

真正的计算机是近似确定性的有限状态机，因此暂停问题实际上并不是实际限制。一个实际的限制是一种算法，它比你想要的等待运行时间更长，排除了任何强力的分析方法。

为了大致了解算法的复杂性，您始终可以在一组随机输入上运行它并测量所花费的时间。然后在数据中绘制曲线。

分析算法的时间复杂度可能相当复杂，需要一些创造性的步骤。 （参见例如快速排序的分析）。该问题与逻辑定理证明和程序验证密切相关。构建一个能够实现复杂性半自动解决方案的有用工具可能是可行的，即系统搜索给出人类提示的解决方案的工具，但这当然不容易。

Answer 4

从未见过这样做的工具，但我们利用分析工具来更好地了解瓶颈所在。这并不总是显而易见的，我曾经多次感到惊讶的事情，我认为花了很长时间实际上很少，反之亦然。在.NET世界中，我使用了 ANTS 和< a href =“http://www.jetbrains.com/profiler/”rel =“nofollow noreferrer”> JetBrains 工具。