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

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)，因为您要将大小为 n 和 m 的两个列表分别附加到列表 result。因此，这意味着您在每次迭代中执行三次 O(n+m) 操作，这意味着操作总数为 O(3 * n * (n + m)) = O(n^2 + n * m).

编辑：我将 n 和 m 交替用于列表及其大小，但我想这是可以理解的。

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

What is the Time Complexity of this code sample? like nested loop, but inner loop is a fixed number

python

algorithm

time-complexity

思考