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 = 0for x in arr:    if x in A:        count+=1    if x in B:        count-=1print(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 = 0for x in arr:    if x in A:        count+=1    if x in B:        count-=1print(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) 的最坏情况。