为文本文件中的伪代码构建 Big-O 运行时复杂性分析器的最佳方法是什么？
What would be the best way to build a Big-O runtime complexity analyzer for pseudocode in a text file?
我正在尝试创建一个 class，它接收包含伪代码的字符串输入并计算其最坏情况下的运行时复杂度。我将使用正则表达式来拆分每一行并分析最坏的情况，并将每一行的复杂性（基于大 O 规则）加起来以给出最终的最坏情况运行时间。编写的伪代码将遵循一些数据结构的声明、初始化和操作规则。这是我可以控制的。考虑到迭代和递归分析的规则，我应该如何设计一个class？
感谢 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)
概念：“我希望编写一个分析伪代码的程序，以便打印出它描述的算法的算法复杂度”在数学上是不可能的！
让我试着解释一下为什么会这样，或者你如何绕过你不能写这个的必然性。
您的伪代码具有某些功能。你称它为伪代码，但考虑到你现在正试图解析它，它仍然是一种 'real' 语言，其中的术语具有实际意义。这种语言可以表达算法。
那么，它可以表达哪些算法呢？据推测，'all of them'。有一个概念叫做'turing machine'：你可以证明计算机能做的事，图灵机也能做。图灵机是非常简单的东西。因此，如果您有一些简单的计算机并且可以使用该计算机来模拟图灵机，那么您就可以使用它来模拟完整的计算机。在基础信息学中，这就是如何证明某个 CPU 或系统能够计算其他 CPU 或系统能够计算的所有东西：用它来计算图灵机，从而证明您可以 运行 这一切。任何可用于模拟图灵机的系统都称为 'turing complete'.
然后我们得到一些非常有趣的东西：如果你的伪代码可以用来表达任何一台真正的计算机可以做的事情，那么你的伪代码可以用来'write'...你的伪代码检查器！
所以假设我们这样做，并将描述您的伪代码检查器的伪代码粘贴到我们将调用 pseudocodechecker 的函数中。它接受一个包含一些伪代码的字符串作为参数，returns 一个字符串，例如 O(n^2).
然后你可以用伪代码编写这个程序：
1. if pseudocodechecker(this-very-program) == O(n^2)
2. If True runSomeAlgorithmThatIsO(1)
3. If False runSomeAlgorithmTahtIsO(n^2)
这是弄巧成拙的：我们有 'programmed' 个悖论。这就像“这个陈述是一个谎言”，或者“不包含自己的所有集合的集合”。如果它是假的就是真的，如果它是真的就是假的。 [这里插入电脑爆炸的GIF]。
因此，我们已经从数学上证明了你想要的是不可能的，除非满足以下条件之一：
一个。您的基于伪代码的检查器不正确。比如，它有时会给出错误的答案，从而解决了悖论：如果你给你的程序一个悖论，它就会给出错误的答案。但是这样的应用程序有多大用处？您知道答案的应用程序可能不正确？
乙。您的基于伪代码的检查器不完整：您的伪代码语言的官方定义如此无能，您甚至无法在其中编写图灵机。
最后一个似乎是个不错的解决方案；但这是相当激烈的。这几乎意味着您的算法只能在恒定范围内循环。例如，它不能循环直到条件为真。另一个不错的解决方案似乎是：该程序能够意识到无法给出答案，然后将报告 'no answer available'，但不幸的是，通过更多的工作，您可以证明您仍然可以使用这样的系统来形成一个悖论。
@rzwitserloot 的回答和 link 中给出的答案是正确的。让我补充一点，它 是 可以计算 近似值 既可以解决停机问题，也可以计算一段代码的时间复杂度（用图灵完备的语言编写！）。 （将其与算术和其他二阶逻辑的自动定理证明器的存在进行比较，后者是不可判定的！）对复杂性问题进行低估的工具会为某些输入输出正确的时间复杂度，而“不知道”其他输入。
事实上，代码分析器的整个广泛领域，通常内置于我们每天使用的 IDE 中，往往是无法计算的欠近似决策问题，例如可达性、可空性或值分析。
如果你真的想写这样一个工具：基本思想是识别启发式，即已知解决方案的常见模式，例如嵌套 for 循环的各种模式，只有非常基本的算术运算操作可以直接发现递归关系的索引或简单递归函数。编写一个工具来解决大多数玩具问题（例如您发布的问题）实际上并不太难（尽管绝对不容易！），这些问题作为家庭作业提供给学生，并且经常作为问题发布在这里在 SO 上，因为它们遵循的模式很少。
如果您希望超越简单的启发式方法，更强大的代码分析器背后的主要理论概念是 abstract interpretation。应用于您的用例，这将意味着在您的语言的代码构造与另一种语言的代码构造（或相同语言的更简单的代码构造）之间开发一个映射，这样更容易计算时间复杂度。这种映射必须符合某些约束条件，特别是映射的构造具有与原始代码相同或更差的时间复杂度。实际上，将一段代码映射到递归关系将是抽象解释的一个例子。用“O(1)”之类的东西替换一行代码也是如此。因此，任务只是将我们在分析代码的时间复杂度时无论如何都会在头脑中做的一些事情形式化。
我正在尝试创建一个 class，它接收包含伪代码的字符串输入并计算其最坏情况下的运行时复杂度。我将使用正则表达式来拆分每一行并分析最坏的情况，并将每一行的复杂性（基于大 O 规则）加起来以给出最终的最坏情况运行时间。编写的伪代码将遵循一些数据结构的声明、初始化和操作规则。这是我可以控制的。考虑到迭代和递归分析的规则，我应该如何设计一个class？ 感谢 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)
概念：“我希望编写一个分析伪代码的程序，以便打印出它描述的算法的算法复杂度”在数学上是不可能的！
让我试着解释一下为什么会这样，或者你如何绕过你不能写这个的必然性。
您的伪代码具有某些功能。你称它为伪代码，但考虑到你现在正试图解析它，它仍然是一种 'real' 语言，其中的术语具有实际意义。这种语言可以表达算法。
那么，它可以表达哪些算法呢？据推测，'all of them'。有一个概念叫做'turing machine'：你可以证明计算机能做的事，图灵机也能做。图灵机是非常简单的东西。因此，如果您有一些简单的计算机并且可以使用该计算机来模拟图灵机，那么您就可以使用它来模拟完整的计算机。在基础信息学中，这就是如何证明某个 CPU 或系统能够计算其他 CPU 或系统能够计算的所有东西：用它来计算图灵机，从而证明您可以 运行 这一切。任何可用于模拟图灵机的系统都称为 'turing complete'.
然后我们得到一些非常有趣的东西：如果你的伪代码可以用来表达任何一台真正的计算机可以做的事情，那么你的伪代码可以用来'write'...你的伪代码检查器！
所以假设我们这样做，并将描述您的伪代码检查器的伪代码粘贴到我们将调用 pseudocodechecker 的函数中。它接受一个包含一些伪代码的字符串作为参数，returns 一个字符串，例如 O(n^2).
然后你可以用伪代码编写这个程序：
1. if pseudocodechecker(this-very-program) == O(n^2)
2. If True runSomeAlgorithmThatIsO(1)
3. If False runSomeAlgorithmTahtIsO(n^2)
这是弄巧成拙的：我们有 'programmed' 个悖论。这就像“这个陈述是一个谎言”，或者“不包含自己的所有集合的集合”。如果它是假的就是真的，如果它是真的就是假的。 [这里插入电脑爆炸的GIF]。
因此，我们已经从数学上证明了你想要的是不可能的，除非满足以下条件之一：
一个。您的基于伪代码的检查器不正确。比如，它有时会给出错误的答案，从而解决了悖论：如果你给你的程序一个悖论，它就会给出错误的答案。但是这样的应用程序有多大用处？您知道答案的应用程序可能不正确？
乙。您的基于伪代码的检查器不完整：您的伪代码语言的官方定义如此无能，您甚至无法在其中编写图灵机。
最后一个似乎是个不错的解决方案；但这是相当激烈的。这几乎意味着您的算法只能在恒定范围内循环。例如，它不能循环直到条件为真。另一个不错的解决方案似乎是：该程序能够意识到无法给出答案，然后将报告 'no answer available'，但不幸的是，通过更多的工作，您可以证明您仍然可以使用这样的系统来形成一个悖论。
@rzwitserloot 的回答和 link 中给出的答案是正确的。让我补充一点，它 是 可以计算 近似值 既可以解决停机问题，也可以计算一段代码的时间复杂度（用图灵完备的语言编写！）。 （将其与算术和其他二阶逻辑的自动定理证明器的存在进行比较，后者是不可判定的！）对复杂性问题进行低估的工具会为某些输入输出正确的时间复杂度，而“不知道”其他输入。
事实上，代码分析器的整个广泛领域，通常内置于我们每天使用的 IDE 中，往往是无法计算的欠近似决策问题，例如可达性、可空性或值分析。
如果你真的想写这样一个工具：基本思想是识别启发式，即已知解决方案的常见模式，例如嵌套 for 循环的各种模式，只有非常基本的算术运算操作可以直接发现递归关系的索引或简单递归函数。编写一个工具来解决大多数玩具问题（例如您发布的问题）实际上并不太难（尽管绝对不容易！），这些问题作为家庭作业提供给学生，并且经常作为问题发布在这里在 SO 上，因为它们遵循的模式很少。
如果您希望超越简单的启发式方法，更强大的代码分析器背后的主要理论概念是 abstract interpretation。应用于您的用例，这将意味着在您的语言的代码构造与另一种语言的代码构造（或相同语言的更简单的代码构造）之间开发一个映射，这样更容易计算时间复杂度。这种映射必须符合某些约束条件，特别是映射的构造具有与原始代码相同或更差的时间复杂度。实际上，将一段代码映射到递归关系将是抽象解释的一个例子。用“O(1)”之类的东西替换一行代码也是如此。因此，任务只是将我们在分析代码的时间复杂度时无论如何都会在头脑中做的一些事情形式化。