这段代码的空间复杂度是多少（它找出嵌套的整数列表中有多少个负数）？是因为没有定义变量所以复杂度是O（1），还是因为列表解析导致复杂度是O（n）？
def foo(forest: list[list[int]]) -> int: return sum([1 for tree in forest for leaf in tree if leaf<0])
再确认一下，这个程序的时间复杂度是O（n2），对吧？谢谢！
s3fp2yjn1#
首先，这里的 n 是什么？我认为这里有两个不同的重要变量，我称之为M = len(forest)和K = max(len(tree) for tree in forest)。时间复杂度为O（K）。接下来，你要构造的列表长度为O（MK），所以它的空间复杂度和时间复杂度是一样的。你可以通过使用生成器表达式而不是列表解析来避免这种情况，如下所示：
M = len(forest)
K = max(len(tree) for tree in forest)
return sum(1 for tree in forest for leaf in tree if leaf < 0)
这避免了必须存储每个值，而在计算总和时一次只生成单个值，因此其额外的空间复杂度将是O（1）。
1条答案
按热度按时间s3fp2yjn1#
首先，这里的 n 是什么？
我认为这里有两个不同的重要变量，我称之为
M = len(forest)和K = max(len(tree) for tree in forest)。时间复杂度为O（K）。
接下来，你要构造的列表长度为O（MK），所以它的空间复杂度和时间复杂度是一样的。
你可以通过使用生成器表达式而不是列表解析来避免这种情况，如下所示：
这避免了必须存储每个值，而在计算总和时一次只生成单个值，因此其额外的空间复杂度将是O（1）。