同时迭代的时间复杂度

Question

我正在努力理解同时迭代的时间复杂度是多少。 如果我们有一个函数接受两个数组并按顺序迭代它们，那就很明显了：

def process(a: list, b: list):
    for i in range(len(a)):
      a[i]
    for i in range(len(b)):
      b[i]

我们有 O(a.lenght + b.lengh)

但是如果我们知道列表的长度是相同的并且我们进行同时迭代：

def process(a: list, b: list):
    for i in range(len(a)):
      a[i]
      b[i]

这是否意味着我们有 O(a.lenght)？

Answer 1

大 O 表示法与

a

和

b

的长度无关。无论这些列表有 5 个元素还是 500,000 个元素，迭代每个元素的任务都是线性的，因此它们的复杂度都是 O(n)。

同样，如果你要考虑这个功能

def process(a: list, b: list):
  for i in range(len(a)):
    for j in range(len(b)):
      a[i]
      b[j]

那么无论这些列表的大小如何，其复杂度都是 O(n^2)。