为文本文件中的伪代码构建Big运行时复杂性分析器的最佳方法是什么？

Question

我正在尝试创建一个类，该类接受包含伪代码的字符串输入，并计算其最坏的运行时复杂性。我将使用regex对每一行进行拆分，分析最坏情况，并将每一行的复杂性(基于大-O规则)相加，从而给出最后的最坏情况运行时。所编写的伪代码将遵循一些关于数据结构的声明、初始化和操作的规则。这是我能控制的。考虑到迭代和递归分析的规则，我应该如何设计类？C++或Java方面的任何帮助都将不胜感激。提前谢谢。

class PseudocodeAnalyzer
{
  public: 
  string inputCode;
  string performIterativeAnalysis(string line);
  string performRecursiveAnalysis(string line);
  string analyzeTotalComplexity(string inputCode);
}

An example for iterative algorithm: Check if number in a grid is Odd:
1. Array A = Array[N][N] 
2. for i in 1 to N
3.   for j in 1 to N
4.    if A[i][j] % 2 == 0
5.      return false
6.    endif
7.   endloop
8. endloop
Worst-case Time-Complexity: O(n*n)    

Answer 1

这个概念：“我想编写一个分析伪码的程序，以便打印出它所描述的算法的复杂性”是数学上不可能的！。

让我来解释一下为什么是这样，或者你是如何克服你写不出这篇文章的必然性的。

你的伪码有一定的能力。您称它为伪代码，但考虑到您现在正试图解析它，它仍然是一种“真实的”语言，其中的术语具有真正的意义。这种语言能够表达算法。

那么，它能表达哪些算法呢？大概是“他们所有人”。有一个叫做“图灵机”的概念:你可以证明电脑能做的任何事情，图灵机也能做到。图灵机是非常简单的东西。因此，如果您有一些简单的计算机，并且可以使用该计算机来模拟图灵机，那么您可以使用它来模拟一台完整的计算机。在基本信息学中，你可以证明某个CPU或系统能够计算其他CPU或系统所能计算的所有东西:用它计算图灵机，从而证明你可以全部运行。任何可以用来模拟图灵机的系统都被称为“图灵完整”。

然后我们要讲一些非常有趣的事情:如果您的伪代码可以用来表示任何真正的计算机可以做的事情，那么您的伪代码可以用来‘写’.你的伪码检查器！

因此，假设我们只是这样做，并将描述您的伪代码检查器的伪代码放在一个我们将称为pseudocodechecker的函数中。它以包含一些伪代码的字符串作为参数，并返回一个字符串(如O(n^2) )。

然后，您可以用伪代码编写这个程序：

1. if pseudocodechecker(this-very-program) == O(n^2)
2.   If True runSomeAlgorithmThatIsO(1)
3.   If False runSomeAlgorithmTahtIsO(n^2)

这是自欺欺人的:我们已经“编程”了一个悖论。这就像“这个陈述是一个谎言”，或者“所有不包含自己的集合”。如果它是假的，它是真实的，如果它是真的，它是假的。在这里插入爆炸计算机的GIF。

因此，我们在数学上证明了你想要的是不可能的，除非以下其中之一是真的：

答:你基于伪码的检查程序是不正确的。它有时会给出一个错误的答案，从而解决这个悖论:如果你给你的程序一个悖论，它就会给出一个错误的答案。但是这样的应用程序有多有用呢？你知道它给出的答案的应用程序可能是不正确的？

基于伪代码的检查程序是不完整的:您的伪代码语言的官方定义是如此的无能，您甚至不能在其中编写图灵机器。

最后一个方案似乎是一个不错的解决办法，但它是相当激烈的。这在很大程度上意味着您的算法只能遍历常量范围。例如，在条件为真之前，它不能循环。另一个很好的解决方案似乎是:程序能够意识到不能给出答案，然后会报告“没有答案”，但不幸的是，通过更多的工作，您可以证明仍然可以使用这样的系统来开发一个悖论。

Answer 2

@rzwitserloot和链接中给出的答案是正确的。让我补充一点，既可以计算终止问题的近似，也可以找到代码段(用图灵全语言编写)的时间复杂性。(将此与算术和其他不可判定的二阶逻辑的自动定理证明器的存在进行比较！)对于某些输入，如果不近似于复杂性问题，就会输出正确的时间复杂度，而对于其他输入，则会输出“不知道”的时间复杂度。

实际上，代码分析器的整个领域，通常都内置在我们每天使用的IDE中，通常是无法计算的近似决策问题，例如可达性、空性或值分析。

如果您真的想编写这样的工具:基本思想是识别启发式，即已知解决方案的常见模式，例如各种嵌套的for -循环模式，其中只有非常基本的算术操作操作索引，或者简单的递归函数，其中可以直接发现递归关系。它实际上不会太难(虽然绝对不容易！)编写一个工具，可以解决大多数玩具问题(比如你发布的玩具问题)，这些问题都是作为家庭作业发给学生的，而这些问题通常都是在这里作为问题发布的，因为它们遵循的模式不多。

如果您希望超越简单的启发式，更强大的代码分析器的主要理论概念是抽象解释。应用到您的用例中，这意味着在您的语言中的代码构造之间开发一个映射，以另一种语言(或在同一语言中使用更简单的代码构造)的代码构造进行映射，这样就可以更容易地计算时间复杂度。这种映射必须符合某些约束，特别是，映射的构造具有与原始代码相同或更糟糕的时间复杂度。实际上，将一段代码映射到一个递归关系将是抽象解释的一个例子。因此，用类似于"O(1)“的代码来替换一行代码。因此，我们的任务就是在分析代码的时间复杂性时，将我们头脑中的一些事情正规化。