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

set在 Python 中是使用哈希表实现的。检查集合中是否存在元素是一个O(1)（即恒定时间）操作，并且该检查的执行时间不取决于集合中有多少元素。list而是作为数组实现，并且检查元素是否存在需要列表中元素的数量O(n)在哪里n。检查一个元素是否存在于包含 1000 个元素的列表中将花费十倍于该列表仅包含 100 个元素所需的时间。

Answer 2

改变的行是：A = list(map(int,input().split())) B = list(map(int,input().split()))对于好的情况，您使用set而不是list. 当您这样做时，这会产生影响：if x in A: if x in B:因为这会检查一个元素是否在列表/集中。对于列表，这是 O(n)，因为您必须执行线性搜索，因为它是一个无序容器。对于集合，在 Python 中它们是使用哈希表实现的，这意味着您可能会进行平均 O(1) 时间查找，但请注意，文档并未明确说明使用哪种哈希。因此，您必须假设 O(n) 的最坏情况。