@rzwitserloot和链接中给出的答案是正确的。我只想补充一点，计算一个近似值，既可以解决停顿问题，也可以解决一段代码（用图灵完备语言编写）的时间复杂度问题(将其与算术和其他二阶逻辑的自动定理证明器进行比较，后者是不可判定的！）一个工具如果低估了复杂性问题，那么对于某些输入输出正确的时间复杂性，而对于其他输入输出“不知道”。
事实上，整个广泛的代码分析器领域，通常内置在我们每天使用的ide中，更多的时候是在不可计算的近似决策问题下，例如可达性、可空性或值分析。
如果您真的想编写这样一个工具：基本思想是识别启发式，即已知解决方案的常见模式，例如只有非常基本的算术运算操作索引的嵌套for循环的各种模式，或者可以直接发现递归关系的简单递归函数。这其实并不难（尽管绝对不容易！）写一个工具，可以解决大部分玩具问题（比如你贴的问题），这些问题作为家庭作业交给学生，通常作为问题贴在这里，因为它们遵循的模式很少。
如果您希望超越简单的启发式，那么更强大的代码分析器背后的主要理论概念是抽象解释。应用于您的用例，这意味着开发一个在您的语言中的代码构造到另一种语言（或同一种语言中更简单的代码构造）中的代码构造之间的Map，从而更容易计算时间复杂度。这种Map必须符合某些约束条件，特别是Map的构造与原始代码具有相同或更差的时间复杂度。实际上，将一段代码Map到递归关系就是一个抽象解释的例子。用类似“o（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]。
因此，我们从数学上证明了你想要的东西是不可能的，除非下列其中一个是真的：
答。基于伪代码的检查器不正确。如中所述，它有时会直接给出错误的答案，从而解决了悖论：如果您向程序提供悖论，它就会给出错误的答案。但是这样的应用程序有多有用呢？你知道答案的应用程序可能不正确？
b。你的基于伪代码的检查器是不完整的：你的伪代码语言的官方定义是如此的无能，你甚至不能用它来写一个图灵机器。
最后一个似乎是一个很好的解决方案；但这是相当激烈的。这几乎意味着你的算法只能在恒定范围内循环。例如，在条件为真之前它不能循环。另一个很好的解决方案似乎是：程序能够意识到无法给出答案，然后会报告“没有可用的答案”，但不幸的是，通过更多的工作，您可以证明您仍然可以使用这样的系统来开发悖论。