能否开发可输入代码并判定其Big O时间复杂度的程序？

核心结论：可以开发这类工具，但存在一定适用范围和局限性 #

一、非递归代码的分析：完全可行，实现难度较低 #

你提到的通过解析缩进、统计循环嵌套层级的思路完全可行，而且不用手动逐词解析代码——Python自带的ast模块可以直接将代码转换成抽象语法树（AST），遍历AST节点就能精准识别for/while循环的嵌套关系：

• 遍历过程中跟踪循环嵌套深度，比如单层循环对应O(n)，两层嵌套对应O(n²)，以此类推；
• 能识别循环内的分支逻辑，比如if语句里的循环，可分别计算不同分支的复杂度，给出最坏/平均情况结果；
• 对于固定次数的循环（比如for i in range(100)），可直接判定为O(1)的常数复杂度。

这种方法仅基于代码结构推导渐近复杂度上界，无需关心程序是否终止，确实和停机问题完全无关。

二、递归代码的分析：部分可行，需针对性处理 #

递归情况比非递归复杂，但并非无法实现：

• 对于结构固定的递归（比如归并排序的分治递归、尾递归），可通过分析递归表达式推导复杂度：比如识别递归终止条件、每次递归调用的子问题规模（归并排序每次将问题拆成两个1/2规模的子问题，对应O(n log n)）；
• 对于带记忆化的递归（比如用lru_cache装饰的斐波那契实现），可识别缓存逻辑，将原本O(2ⁿ)的复杂度修正为O(n)；
• 但如果是动态递归（比如递归调用次数依赖运行时输入变量，或递归逻辑包含复杂分支判断），很难做到100%准确判定，此时只能给出最坏情况的复杂度估计。

三、开发建议 #

如果你打算自行开发，可以按以下步骤推进：

1. 先从非递归代码分析入手，用ast模块实现基础的循环嵌套识别，快速搭建核心功能；
2. 逐步加入递归分析逻辑，先支持简单递归模式（比如单递归调用、分治递归），再扩展到复杂场景；
3. 优先覆盖常见复杂度类型：O(1)、O(n)、O(n²)、O(log n)、O(n log n)、O(2ⁿ)，再处理边缘情况；
4. 对于无法准确判定的情况，给出“无法确定精确复杂度，最坏情况为XXX”的提示。

内容的提问来源于stack exchange，提问作者user12795105