求证Python公共字符检测函数的正确大O时间复杂度

你和同学的判断是准确的：该函数的通用最坏时间复杂度为O(m*n)，其中m为输入string1的长度，n为输入string2的长度。认为复杂度是O(n²)的结论，仅在两个输入字符串长度相等（即m=n）的特殊前提下成立，不属于通用场景下的严谨表述。

逐行拆解代码的执行开销：

def contain_letters_in_common(string1, string2):

    duplicates = []
    for letter in string1:
        if letter in string2:
            if letter not in duplicates:
                duplicates.append(letter)

    return len(duplicates) > 0

• 初始化空列表duplicates、最终返回判断len(duplicates) > 0、列表尾部追加append操作均为常数时间O(1)，不主导整体复杂度。
• 外层for letter in string1循环会完整遍历string1的全部字符，共执行m轮，m为string1的长度。
• 循环内的if letter in string2判断：Python中字符串属于顺序序列，没有内置哈希索引，成员判断需要逐字符线性扫描整个string2，单次执行最坏时间复杂度为O(n)，n为string2的长度。
• 循环内的if letter not in duplicates判断：duplicates存储的是两个字符串共有的去重字符，而可作为字符串元素的字符总量是固定常数（即便覆盖所有通用Unicode字符，规模也和输入长度无关），因此该判断的扫描长度存在固定上限，时间复杂度为O(1)，不会影响整体复杂度量级。

把各部分开销累加，整体最坏时间复杂度就是外层循环次数乘以内层单次线性扫描的开销，即O(m*n)。

O(n²)的表述本质是O(m*n)在m=n场景下的简化形式：如果题目明确给出两个输入字符串长度一致的约束，确实可以将复杂度简写为O(n²)。但在没有等长约定的通用分析场景下，两个输入的规模是独立变量，不能强行合并为单变量的平方复杂度，否则会丢失输入规模的独立信息，分析结果不严谨。

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