Python任意嵌套列表扁平化函数的时间复杂度分析

嘿，我来帮你把这两个嵌套列表扁平化函数的时间复杂度掰扯清楚～ 其实核心逻辑比你想象的要统一，咱们一步步来：

先明确关键变量：别搞混定义！ #

要聊复杂度，得先把变量说清楚，避免歧义：

• 设T为所有嵌套层级中元素的总个数——这里的元素包括最内层的非列表原子（比如整数、字符串），也包括所有中间层的列表本身（比如[[1],2]里的外层列表[[]]和内层列表[1]都算，总T是3：两个列表+一个原子1）
• 设D为嵌套的最大深度（比如[[[1]]]的D是3，[1,[2,[3]]]的D也是3）

递归版函数：时间复杂度O(T) #

递归版的逻辑无非是：遍历当前列表的每个元素，要是元素是列表就递归进去处理，否则直接加入结果。
这里的关键是：每一个元素（不管是列表还是原子）都会被访问且处理一次，每次处理都是O(1)的操作（判断类型、添加元素到结果等）。不管嵌套多少层，总操作数完全和T成正比，所以时间复杂度是线性的O(T)。
顺带提一句，递归的调用栈深度是O(D)，但这是空间复杂度的范畴，不影响时间复杂度的计算～

迭代版函数：时间复杂度也是O(T) #

迭代版一般用栈/队列模拟递归过程：比如把待处理的列表压入栈，弹出后遍历每个元素，遇到列表就压回栈继续处理，原子元素直接加入结果。
和递归版本质一样：每个元素（列表+原子）都会被压入栈一次、弹出一次、处理一次，所有操作都是O(1)级别的。哪怕嵌套1000层，只要总元素数T是固定的，总操作数就是T量级，所以时间复杂度同样是O(T)。
你之前想的O(n*m)应该是误解了变量定义——如果把n当嵌套层数、m当每层元素数，其实n*m本质就是总元素数T的另一种表达，只是换了个说法而已。

两者的效率对比：理论等价，实际有差异 #

• 时间复杂度层面：完全等价，都是线性时间O(T)，因为最终都要遍历所有元素一遍，没有冗余操作。
• 实际运行效率：迭代版通常略快一点，因为递归会有函数调用的开销（栈帧的创建、销毁、参数传递）。尤其是当嵌套深度D超过Python默认的递归深度限制（默认1000）时，递归版直接会抛出RecursionError，但迭代版完全没这个问题。
• 空间复杂度补充：递归版是O(D)（递归调用栈的深度），迭代版的空间复杂度取决于栈/队列的最大元素数，最坏情况是O(T)（比如一个列表里全是子列表，[[1],[2],[3],...,[n]]），但大多数场景下两者空间差异不大。

为什么你在SO上没找到明确结论？因为很多问题聚焦“普通嵌套”，但不管嵌套多少层，核心逻辑都是遍历所有元素一次，复杂度本质是一样的，只是大家没特意强调n层嵌套的场景而已～

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