关于嵌套If语句检查数组的时间复杂度及代码Big O分析的疑问

一、sym in arr2的检查方式 #

Python中对列表（数组）使用in运算符时，会执行线性遍历搜索：从列表的第一个元素开始，逐个将元素与目标值sym对比，直到找到匹配项或遍历完整个列表。单次in操作的时间复杂度为O(m)，其中m是arr2的长度。

二、当前代码的实际执行流程 #

你提供的代码里，for循环只会执行第一次迭代，核心原因是不管if条件是否成立，都会执行break终止循环：

• 取出arr1的第一个元素sym；
• 执行sym in arr2检查是否存在；
• 若存在：打印True，执行break，循环直接结束；
• 若不存在：进入if的else分支，打印False，执行break，循环同样直接结束。

也就是说，无论arr1有多少元素，循环都只会处理第一个元素就终止，不会遍历整个arr1。

三、时间复杂度分析 #

你之前认为的O(n*m)是错误的——这个结论的前提是循环会遍历整个arr1，每次迭代都执行O(m)的in操作，但当前代码的逻辑完全不满足这个前提。

实际情况下，函数仅执行一次sym in arr2操作，因此整体时间复杂度为O(m)（m为arr2的长度）。至于你听到的O(n)，大概率是对方的错误判断；除非问题中默认arr1和arr2的长度为同阶量级（此时用O(n)泛指线性复杂度），但严格来说应为O(m)。

补充：正确的“检查共同元素”代码优化 #

如果你的本意是检查两个数组是否存在共同元素（遍历arr1直到找到匹配项），正确的代码应该调整else的层级并移除多余的break，示例如下：

def containscommonitem(arr1, arr2):
    for sym in arr1:
        if sym in arr2:
            print("True")
            return
    print("False")

这种情况下，最坏时间复杂度为O(n*m)（当两数组无共同元素时，遍历完arr1的所有n个元素，每个都执行O(m)的搜索）。若要进一步优化，可将arr2转换为集合，此时in操作的时间复杂度变为O(1)，整体复杂度降至O(n + m)（转集合耗时O(m)，遍历arr1耗时O(n)）。

内容的提问来源于stack exchange，提问作者Mr Nobody