未定义变量的空间复杂度

Space Complexity with no variables defined

提问人:Jason Grace 提问时间:1/29/2023 最后编辑:Jason Grace 更新时间:3/17/2023 访问量:42

问:

假设我有一些代码:

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

在此代码中,未定义任何变量。一切都在一行中进行评估,据我所知,这意味着数据没有存储在任何地方。这是否意味着该程序的空间复杂度为O(1)?

感谢您抽出宝贵时间接受采访。

python 时间-复杂度 列表-推导式 嵌套列表- 空间复杂度

评论

1赞 John Gordon 1/29/2023
列表推导可能包含许多项目,因此它肯定不是 O(1)。当然,这种理解不会保存在任何地方,但它会占用内存,无论多么短暂。[1 for ...]

答:

4赞 Jasmijn 1/29/2023 #1

首先,这里的n是什么?

我认为这里有两个不同的重要性变量,我称它们为 和 。M = len(forest)K = max(len(tree) for tree in forest)

那么时间复杂度将为 O(MK)。

接下来,您正在构建的列表的长度为 O(MK),因此其空间复杂度与时间复杂度相同。

您可以通过使用生成器表达式而不是列表推导式来避免这种情况,如下所示:

return sum(1 for tree in forest for leaf in tree if leaf < 0)

这避免了必须存储每个值,在计算总和时一次只生成一个值,因此其额外的空间复杂度将为 O(1)。