Python 中函数的时间复杂度

Question

我有 2 个函数执行相同的任务，即识别 2 个列表之间是否有任何共同元素。我想分析一下他们的时间复杂度。

我所知道的是：for 循环如果迭代 n 次则复杂度为 O(n)。但是，我对使用 'in' 运算符时的情况感到困惑。例如：如果元素在 mylist

请查看功能以更好地了解场景：

list1 = ['a','b','c','d','e']
list2 = ['m','n','o','d']


def func1(list1, list2):
  for i in list1:      # O(n), assuming number of items in list1 is n
    if i in list2:     # What will be the BigO of this statement??
      return True
  return False

z = func1(list1, list2)
print(z)

我还有一个函数func2，请帮忙确定一下它的BigO:

def func2(list1, list2):
  dict = {}
  for i in list1:
    if i not in dict.keys():
      dict[i] = True

  for j in list2:
    if j in dict.keys():
      return True
  
  return False

z = func2(list1, list2)
print(z)

func1和func2的时间复杂度是多少？ 2个函数在性能上有什么区别吗？

Answer 1

关于 func1:

• 在列表中搜索是关于元素数量的线性运算，
• 假设项目是随机排序的并且检查顺序也不相关，那么从统计上讲，您会在 n/2 步中遇到一个现有元素，当找不到时会遇到 n（这简化为 O(n)）

if x in list_ 是如上所述的线性搜索，因此 func1 的复杂度为 n^2。

关于func2：

您可能要考虑使用集合而不是字典。检查元素是否存在的复杂度为 O(1)。这将提高 func1 的复杂性，并且您还可以使用 set(list) 创建列表而不是直接在 python 中迭代列表（这比直接从列表初始化集合慢- 但不影响 O 的复杂性，因为它只是速度较慢，但​​保持不变）。