对嵌套 If 语句的时间复杂度感到困惑

Question

我试图弄清楚代码的 Big 0 是什么，但对检查数组中是否存在字母的嵌套 If 语句的时间复杂度感到困惑。如果它检查整个数组，那么它将是 O(n) （最坏情况），这反过来又会使整个代码的 Big O O(n^2)，但我被告知它是 O(n)。

If 语句检查数组的具体作用是什么？ 代码

def containscommonitem(arr1,arr2):
  for sym in arr1:
    if sym in arr2:
      print("True")
      break
    else:
      print('False')
      break
containscommonitem(['a','b','c','y'],['m','z','f'])

Answer 1

如果我们要精确的话，因为我们有两个不同的变化输入，所以我们不能只用其中之一来描述复杂性，除非我们证明它是合理的。

所以说N指的是arr1的大小，M指的是arr2的大小。 那么在最坏的情况下，你的时间复杂度为 O(N*M)。您应该考虑为什么这与现实生活场景中的 O(N^2) 不同。

正如 John Gordon 指出的那样，break 语句也极大地改变了分析的方式，因为这样你可能会更关心平均情况而不是最坏的情况。