谁能解释一下这条线的复杂性？

Question

我在计算这条线的时间复杂度时遇到了麻烦。对我来说似乎是二次 O(n**2) 。因为如果我不使用列表理解，我必须在此处进行嵌套循环。

    AB = Counter([(a+b) for a in A for b in B])

Answer 1

您的线路：

AB = Counter([(a+b) for a in A for b in B])

等同于（忽略列表推导速度更快且不逐一追加的事实*）：

# given lists A, B
AB0 = []

# this is O(n2)
for a in A:
    for b in B:
        AB0.append(a+b) 

AB = {}

# this is O(m), m=n2
for ab in AB0:
    if ab not in AB:
        AB[ab] = 0
    AB[ab] += 1

关于与列表理解的区别：理解实现更快（解释），但这并不意味着它具有与 O(n2) 不同的时间复杂度。另外：追加是 O(k).

所以总而言之，它受 O(n2) 的限制。

谁能解释一下这条线的复杂性？

Can anyone please explain the Complexity of this line?

python

complexity-theory

list-comprehension