无额外变量的Python单语句代码空间复杂度是否为O(1)？

先看原代码：

def foo(forest: list[list[int]]) -> int:
    return sum([1 for tree in forest for leaf in tree])

这段代码的空间复杂度不是O(1)，核心原因是：代码里用了带方括号的列表推导式，它会在内存中一次性生成一个包含所有元素的列表——列表里的1的数量等于forest中所有嵌套子列表的元素总数（假设总共有n个元素），所以这个列表占用的空间是O(n)级别的，属于线性空间复杂度。

如果要把空间复杂度优化到O(1)，只需要去掉列表推导的方括号，改用生成器表达式即可：

def foo(forest: list[list[int]]) -> int:
    return sum(1 for tree in forest for leaf in tree)

生成器表达式不会预先创建完整列表，而是在迭代过程中逐个生成值，sum函数可以直接迭代这个生成器，全程只需要常数级别的额外空间。

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