谁能解释一下这一行的复杂性吗？

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)不同的时间复杂度。另外：append是O(k)。

所以总而言之，它是以O(n2)为界的。