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

Question

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

Answer 1

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

要开始您的项目，我建议您研究一下循环复杂度，例如由 GMetrics 项目计算的。

这将帮助您开始探索该主题。

Answer 2

假设您知道要为程序提供什么样的输入，您可以通过实际运行程序的连续迭代来“估计”复杂性。 然而，由于停止问题，一般情况下的静态分析是不可能的。 如果您可以在不同大小的输入集上多次运行应用程序，则可以得出近似值。

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

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