关于intersect函数双嵌套循环时间复杂度的疑问

示例代码 #

def intersect(L1, L2):
    """
    Assumes L1 and L2 are lists
    Returns a list without duplicates that is intersection of L1 and L2
    """
    
    # Part i - Build a list containing common elements
    tmp = []
    for e1 in L1:
        for e2 in L2:
            if e1 == e2:
                tmp.append(e1)
                break
             
    # Part ii - Build a list without duplicates
    result = []
    for e in tmp:
        if e not in result:
            result.append(e)
    
    return result  

问题1：第一部分的时间复杂度争议 #

你对第一部分复杂度的分析是正确的，作者说的Θ(len(L1)*len(L2))是最坏情况下的结论，并非所有场景都适用：

• 最坏情况：L1每个元素都要遍历完整个L2才能找到匹配（比如L1所有元素等于L2最后一个元素），内层循环每次执行len(L2)次，总操作数为len(L1)*len(L2)，复杂度为Θ(len(L1)*len(L2))。
• 最好情况：L1每个元素都匹配L2第一个元素，内层循环仅执行1次就break，总操作数等于len(L1)，复杂度为Θ(len(L1))。

教材用Θ符号属于简化表述，默认讨论最坏情况；旧版用Big-O更严谨，因为Big-O描述的是复杂度上界，而Θ要求是紧界——只有当所有场景的复杂度都落在同一个紧区间时才适用，显然第一部分不满足这个条件。

问题2：第二部分的时间复杂度困惑 #

作者提到的Θ(len(tmp)*len(result))同样是最坏情况的分析，不同场景下复杂度确实有差异：

• 最坏情况：tmp中的元素完全不重复（比如L1和L2的交集元素都是唯一的，且L1每个元素都在L2中存在），此时len(result)会逐步增长到等于len(tmp)，每次e not in result都要遍历整个当前result，总操作数是1+2+...+len(tmp)，等价于Θ(len(tmp)²)，而len(result)最大等于len(tmp)，所以可以表述为Θ(len(tmp)*len(result))。
• 你说的result长度为1的场景（比如tmp全是同一个元素），属于第二部分的最好情况，此时每次检查e not in result只需判断1个元素，总操作数等于len(tmp)，复杂度为Θ(len(tmp))。

作者说“len(result)和len(tmp)受len(L1)与len(L2)中较小值限制，该项可忽略”，是从整个函数的宏观复杂度出发：第一部分最坏情况是Θ(len(L1)*len(L2))，第二部分最坏情况Θ(len(tmp)²)最大不超过Θ(min(len(L1), len(L2))²)，当len(L1)和len(L2)差距较大时，这个项的复杂度远低于第一部分，可以被忽略，所以整个函数的最坏复杂度由第一部分主导。

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