java - 从程序中获取时间复杂度和空间复杂度

Question

我正在创建一个网站（我的学术项目），用户可以在其中上传他的程序文件（.cs、.PHP、.java），然后网络编译程序并能够自动说出时间和空间复杂度。这可能吗？我们如何计算程序的复杂度。Java中是否有用于查找程序复杂性的代码？或者我们可以从编译器本身找到这些吗？

Answer 1

假设你知道给程序什么样的输入，你可以通过实际运行程序的连续迭代来估计复杂度。然而，由于停机问题，一般情况下的静态分析是不可能的。

如果您可以在不同大小的输入集上多次运行应用程序，您可以开发一个近似值。

在对数字进行排序的经典案例中，您可以让应用程序对 2 个数字的列表进行排序，然后对 4、8、16、32 等进行排序……并从本质上绘制每次运行的内存和时间要求。基本曲线拟合将向您展示复杂性的增长。

请注意，这并不严格准确，因为某些算法可能存在其性能发生根本变化的点。这样的系统也可能会被“看起来”相似但性质大不相同的增长之间的差异所迷惑，例如渐近曲线和对数曲线，或指数曲线和多项式曲线。

Answer 2

确定程序的时间和空间复杂度是一个难题。正如反馈所指出的那样，通常甚至不可能指出程序是否会终止。（这被称为停机问题）

要开始您的项目，我建议您研究一下由 GMetrics 项目计算的 Cyclomatic Complexity 。

这将使您开始探索主题。