提问人:Jason Grace 提问时间:1/29/2023 最后编辑:Jason Grace 更新时间:3/17/2023 访问量:42
未定义变量的空间复杂度
Space Complexity with no variables defined
问:
假设我有一些代码:
def foo(forest: list[list[int]]) -> int:
return sum([1 for tree in forest for leaf in tree])
在此代码中,未定义任何变量。一切都在一行中进行评估,据我所知,这意味着数据没有存储在任何地方。这是否意味着该程序的空间复杂度为O(1)?
感谢您抽出宝贵时间接受采访。
答:
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)。
评论
[1 for ...]