python - Python 3 中的时间复杂度

Question

以下代码适用于 hackerrank 问题:(A和B默认会得到不重复、离散的数据)

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)

时间复杂度如何在list和set中急剧变化，它们是如何工作的？

Answer 1

Python 中的

set 是使用 hash table 实现的.

检查集合中是否存在元素是一个O(1)(即常数时间)操作，此检查的执行时间不取决于集合中有多少元素.

list 被实现为数组，检查元素是否存在需要 O(n)，其中 n 是元素的数量在列表中。检查一个元素是否存在于包含 1000 个元素的列表中所花费的时间是该列表仅包含 100 个元素时所需时间的十倍。