有没有工具可以确定Big-O复杂度的代码分析性能?

14

我还没有看到相关的内容,我怀疑定义 "n" 的困难之处在于分析复杂函数通常需要多个变量来定义。

有针对圈复杂度的分析工具,但是否有用于时间(和/或空间)复杂度的工具呢?如果有,是哪些工具?如果没有,为什么没有?不可行吗?不可能实现吗?还是只是没有人去做这件事?

理想情况下,应该有一种类似整体应用程序复杂性(定义不同的可能的 "n")以及每个应用程序方法的复杂性的工具。

编辑:看起来由于停机问题的存在,确切的解决方案是不可能的,但是,是否可能使用某种启发式逼近?我意识到,就实际目的而言,一个好的分析器将提供更有用的信息,但这似乎是一个有趣的问题。

此外,如何计算特定程序子集的复杂度呢?

4个回答

13

不幸的是,有一个被称为“停机问题”(Halting problem)的难题...


2
为了让事情更加清晰,这意味着所提出的工具是不可能的,而不仅仅是不可行的。 - David Thornley

7

不,这是不可能的,因为存在停机问题。

如果您想要改进应用程序,可以考虑使用性能分析。这将允许您确定实际上需要最多时间的内容。这样,您就不会花费时间优化仅在小数据集上运行的O(n^3)算法。


2
如果您可以假定程序实际上会停止运行,那么我想原则上来说,分析器可能会猜测该算法的复杂度。然而正如Ben所说,在真实代码中,瓶颈的真实世界分析比理论复杂性更有用。 - stevemegson
1
那么,如果我们只是要求助于性能分析,为什么在编程面试中如此强调大O符号? - Isaac Pak

1

一些想法:

真正的计算机大约是确定性有限状态机,因此停机问题实际上并不是一个实际的限制。一个实际的限制是一个算法需要比你愿意等待的时间更长,排除了任何暴力分析方法。

要对算法的复杂度有一个大致的想法,您可以在一组随机输入上运行它,并测量所花费的时间。然后通过数据绘制一条曲线。

分析算法的时间复杂度可能相当复杂,需要一些创造性的步骤。(例如快速排序的分析)。这个问题与逻辑定理证明和程序验证密切相关。构建一个有用的工具,使得半自动解决复杂度成为可能,即一个根据人类提示系统地搜索解决方案的工具,但这肯定是很困难的。


0

我从未见过一个专门做这件事的工具,但我们利用性能分析工具来更好地了解瓶颈所在。有时候并不明显,我曾经被一些我认为需要很长时间才能完成的任务实际上只需要很少的时间,反之亦然。在.NET世界中,我使用ANTSJetBrains工具。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接