Python disjoint函数时间复杂度疑问：O(n²)判定为何被标记错误？

首先看给定的函数代码：

def disjoint(lst1,lst2):
    res = True
    for x in lst1:
       if x in lst2:
          res = False
    return res

你认为时间复杂度是O(n²)的结论不够严谨，这应该是老师判定错误的原因：

• 严格来说，这个函数的时间复杂度是O(m*n)，其中m代表lst1的长度，n代表lst2的长度。
• 外层循环遍历lst1的所有元素，时间开销为O(m)；每一次循环里的x in lst2操作需要遍历lst2查找匹配，时间开销为O(n)，两者相乘就是整体的时间复杂度。
• O(n²)只是当两个列表长度相等（m=n）时的特殊简化表述，但如果两个列表长度差异较大（比如一个长度为10，另一个为1000），用O(n²)描述就不符合实际的规模关系了。

（注：该函数存在可优化点——一旦发现x in lst2为True，可立即返回False，无需继续遍历，但你提到无需在意效率，这里仅作补充说明）

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