是否有任何工具可以确定执行 Big-O 复杂性的代码分析？
我还没有看到任何东西，我怀疑定义“n”很困难，因为通常分析一个复杂的函数时，需要定义的变量不仅仅是一两个变量。
有圈复杂度的分析工具，但有时间（和/或空间）复杂度的分析工具吗？ 如果是的话，是哪些，如果不是，为什么不呢？ 难道不可行吗？ 不可能的？ 有人还没来得及做这件事吗？
理想情况下，应用程序的整体复杂性（定义不同的可能的“n”）以及应用程序中的每个方法
编辑：因此，由于 停止问题 但是，某种启发式近似是否可能？ 我意识到，出于实际目的，一个好的分析器会提供更多有用的信息，但这似乎是一个有趣的问题。
另外，对于某个程序子集进行计算怎么样？
I haven't seen anything out there, and I suspect the difficulty with defining "n" since for generally for analyzing a complex function there'd be more than just one or two variables for defining.
There are analysis tools for cyclomatic complexity but are there ones for time (and/or space) complexity? If so which ones, if not, why not? Is it infeasible? Impossible? Someone just hasn't gotten around to it?
Ideally there'd be something like overall complexity for the application (defining different possible "n"s) as well as for each method in the app
Edit: So it seems like an exact solution is impossible because of the Halting Problem however, is some kind of heuristic approximation possible? I realize that for practical purposes a good profiler will give much more useful information, but it seems like an interesting problem.
Also, how about one that calculates for a certain subset of programs?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
不幸的是，这个问题称为停止问题...
Unfortunately there is this problem called the Halting problem...
不，由于停止问题，这是不可能的。
如果您想这样做来改进您的应用程序，您可以考虑进行分析。 它可以让您查明什么实际上花费了最多时间。 这样，您就不必花时间优化仅在小型数据集上运行的 O(n^3) 算法。
No, this isn't possible, due to the halting problem.
If you'd like to do this to improve your applications, you might consider profiling instead. It would allow you to pin-point what is actually taking the most time. This way you don't spend time optimizing a O(n^3) algorithm that only runs on small datasets.
一些想法：
真实的计算机大约是确定性的有限状态机，因此停止问题实际上并不是一个实际的限制。 一个实际的限制是算法的运行时间比您想要等待的时间要长，排除了任何强力分析方法。
要大致了解算法的复杂性，您始终可以在一组随机输入上运行该算法并测量所花费的时间。 然后通过数据绘制一条曲线。
分析算法的时间复杂度可能相当复杂，需要一些创造性的步骤。 （参见快速排序的示例分析）。 该问题与逻辑定理证明和程序验证密切相关。 构建一个能够实现复杂性半自动解决方案的有用工具可能是可行的，即系统地搜索人类给出的提示的解决方案的工具，但这当然并不容易。
A few thoughs:
Real computers are approximately deterministic finite state machines, so the halting problem isn't actually a practical limitation. A practical limitation is an algorithm that takes more time to run than you feel like waiting, ruling out any brute force methods of analysis.
To get a rough idea of complexity of an algorithm, you can always run it on a set of random inputs and measure the time taken. Then plot a curve through the data.
Analyzing the time complexity of algorithms can be fairly complicated, requiring some creative steps. (See for example analysis of quicksort). The problem is related closely to logical theorem proving and program verification. It might be feasible to construct a useful tool that enables semi-automatic solution of complexity, i.e. a tool that searches systematically for solutions given hints from a human, but it certainly isn't easy.
从未见过可以执行此操作的工具，但我们利用分析工具来更好地了解瓶颈所在。 这并不总是显而易见的，有几次我对那些我认为花了很长时间的事情实际上只花了很少的时间感到惊讶，反之亦然。 在 .NET 世界中，我使用过 ANTS 和 < a href="http://www.jetbrains.com/profiler/" rel="nofollow noreferrer">JetBrains 工具。
Never seen a tool to do this but we utilize profiling tools to get a better idea where the bottlenecks are. It isn't always obvious and I've been surprised a few times by things that I thought took a long time actually taking very little and vice-versa. In the .NET world, I've used ANTS and the JetBrains tools.