对嵌套 If 语句的时间复杂度感到困惑。（已解决）

Question

我试图弄清楚代码的 Big 0 是什么，但对检查数组中是否存在字母的嵌套 If 语句的时间复杂度感到困惑。如果它检查整个数组，那么它将是 O(n) （最坏情况），这反过来又会使整个代码的 Big O O(n*m)，但我被告知它是 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 语句也极大地改变了分析的方式，因为这样你可能会更关心平均情况而不是最坏的情况。

Answer 2

for

循环仅进行一次迭代，因为其主体保证执行

break

。这意味着您拥有的每个语句最多执行一次。这些语句中唯一不是 O(1) 的语句是

if sym in arr2

。

in

运算符可能必须完全扫描

arr2

，因此最坏情况的时间复杂度为 O(m)，其中 m 是

arr2

的大小。

arr1

的大小不相关，因为仅检查其第一个条目。

现在，函数的名称表明，当两个列表没有共同值时，它应该输出“False”。但这样就错了：如果你只查看

arr1

中的第一个值，你就无法知道这一点。例如，您的代码将为此输入输出“False”：

containscommonitem(['a','m'],['m'])

...因为它从未查看第一个列表中的“m”。

更正方法是将

False

的打印移到

else

语句的

for

子句中：

def containscommonitem(arr1,arr2):
    for sym in arr1:
        if sym in arr2:
            print("True")
            break
    else: # when the for loop has finished without executing a break
        print('False')

现在最坏情况的时间复杂度是 O(n*m)。不用说，有更有效的方法可以做到这一点——使用

set

。