python - 比较两个列表中元素的复杂性

Question

我在 Python 中编写了一个函数来查找另一个排序列表中存在的排序列表的元素并打印出结果：

# assume that both lists are sorted
def compare_sorted_lists(list1, list2):
  res = []
  a = 0
  b = 0
  while a < len(list1) and b < len(list2):
    if list1[a] == list2[b]:
      res.append(list1[a])
      a += 1
    elif list1[a] < list2[b]:
      a += 1
    else:
      b += 1
  return res

我想弄清楚用这种方法比较元素的时间复杂度。

假如说：

• list1 的长度为 A 并且 list1 元素中的最大数字/字母数是 X
• list2 的长度为 B 并且 list2 元素中的最大数字/字母数为 Y

对于这些列表，我在用指针遍历它们时具有 O(A+B) 时间复杂度，但是比较元素将如何影响此函数的时间复杂度（特别是最坏情况下的时间复杂度）？

编辑：2021 年 3 月 12 日 16:30 - 改写的问题

标签： pythonalgorithmtime-complexitycomplexity-theory

Answer 1

两个元素之间的比较是恒定时间，因此这不会影响整个算法的复杂性，您将其更正为 O(A+B)。