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)

列表和集合的时间复杂度如何急剧变化以及它们如何工作？

Answer 1

Python 中的

set 是使用 hash table 实现的。 .

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

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