Python 3中的时间效率

Question

我在hackerrank上编写代码，遇到以下错误

n,m = map(int,input().split())
arr = list(map(int,input().split()))
A = set(map(int,input().split()))
B = set(map(int,input().split()))
count = 0
for x in arr:
    if x in A:
        count+=1
    if x in B:
        count-=1
print(count)

[这个很好用，但是下一个在4个测试用例中显示时间错误。我想知道列表和集合中的时间复杂度如何急剧变化以及它们如何工作。

n,m = map(int,input().split())
arr = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
count = 0
for x in arr:
    if x in A:
        count+=1
    if x in B:
        count-=1
print(count)

感谢您的帮助

Answer 1

更改的行是：

A = list(map(int,input().split()))
B = list(map(int,input().split()))

[在好的情况下，请使用set而不是list。当您这样做时会产生影响：

if x in A:
if x in B:

因为检查元素是否在列表/集中。对于列表，它是O（n），因为它们是无序的（因此您必须查看每个元素），对于列表，它是O（lg n），因为它们是有序的（二进制搜索）。

Answer 2

Python中的[set使用hash table实现。

检查集合中是否存在元素是O(1)（即恒定时间）操作，并且此检查的执行时间不取决于集合的大小。

list而是实现为数组，并且检查元素是否存在需要O(n)，其中n是列表中元素的数量。如果列表中仅包含100个元素，那么检查元素是否包含在包含1000个元素的列表中将花费十倍的时间。]