这个代码示例的时间复杂度是多少？与嵌套循环类似，但内部循环是一个固定数字

Question

result = []
for i in n:
  for jj in range(len(m)):
    if jj < 3:
      result.append((n,m))
    else:
      jj = len(m)

• m、 n是两个python数组
• 内环最大值为3

思考

• O（n）？因为内循环是固定数量的
• O（n*m）
• O（n*3）？这不是正确的方法：（

---

What is the correct O time complexity for this?

Answer 1

内部循环内语句的时间复杂度为O(1)。因为，它只是一个比较和一个变量赋值，而len(m)的计算是在O(1)中完成的。剩下的很简单：两个嵌套循环，分别进行n和m迭代。因此，时间复杂度为O(m * n)

Answer 2

答案是O(n^2 + n * m)。内部循环最多执行三次，在每一次迭代中，您都在执行以下操作：result.append((n,m))。这种方法的时间复杂度是O(n+m)，因为您将在列表result中分别添加两个大小列表n和m。这意味着在每次迭代中要执行三次O(n+m)操作，这意味着操作的总数是O(3 * n * (n + m)) = O(n^2 + n * m)

编辑：我使用n和m来交换列表及其大小，但我想这是可以理解的