脚本的复杂性

Question

我试图在 A 中找到一对 (x,y) 使得 x-y = 0 (mod n)

下面是我写的脚本

如果 n 是常数，运行 时间复杂度是多少？ --> 所以，这是被问到的，但无论如何 n 不是一个常数吗？我有点困惑，问题是“输入是正整数 n...”

def find_equal_pair_mod_n(n, A):
  assert len(A) > n

  X = [-1] * n
  print(X)

  for i in range(len(A)-1,-1,-1) :  #loop backwards
    print(i)
    a = A[i]
    print(a)
    print(len(A))
    A.pop(i)
    r = a % n

    if X[r] == -1:
      X[r] = a
    else:
     return(X[r], a)

Answer 1

简答

1. “就 n 和 m 而言，运行 的时间复杂度是多少？”。正确答案是 O(n).
2. “如果 n 是常数，运行 的时间复杂度是多少？”。正确答案是 O(1).

说明

1. 当你迭代你的循环时，你不能做超过 n + 1 次迭代，因为除以 n 后只有 n 个不同的余数。所以你肯定会在 n + 1 或更少的迭代中找到答案。
2. 如果 n 是常数，您仍然需要 n + 1 或更少的迭代来找到答案，因此您需要常数时间来解决您的问题。