我还没有看到任何东西,我怀疑定义“n”很困难,因为通常分析一个复杂的函数时,需要定义的变量不仅仅是一两个。
有圈复杂度的分析工具,但有时间(和/或空间)复杂度的分析工具吗? 如果是的话,是哪些,如果不是,为什么不呢? 难道不可行吗?不可能的? 有人还没有抽出时间吗?
理想情况下,应用程序以及应用程序中的每个方法都具有整体复杂性(定义不同的可能“n”)
编辑:所以由于“停止问题”,似乎不可能有精确的解决方案,但是,某种启发式近似是否可能? 我意识到,出于实际目的,一个好的分析器会提供更多有用的信息,但这似乎是一个有趣的问题。 另外,对于程序的某个子集进行计算怎么样?
如果您想这样做来改进您的应用程序,您可以考虑进行分析。它可以让您查明什么实际上花费了最多时间。这样您就不必花时间优化仅在小数据集上运行的 O(n^3) 算法。
真实的计算机是近似确定性的有限状态机,因此停止问题实际上并不是一个实际的限制。一个实际的限制是算法的运行时间比您想要等待的时间要长,从而排除了任何强力分析方法。
要大致了解算法的复杂性,您始终可以在一组随机输入上运行该算法并测量所花费的时间。然后通过数据绘制一条曲线。
分析算法的时间复杂度可能相当复杂,需要一些创造性的步骤。 (参见快速排序的示例分析)。该问题与逻辑定理证明和程序验证密切相关。构建一个有用的工具来实现复杂性的半自动解决方案可能是可行的,即系统地搜索人类给出的提示的解决方案的工具,但这肯定不容易。
和 JetBrains 工具。