如何降低Python中这段4位数字比对compare函数的时间复杂度？

核心结论 #

你当前的实现时间复杂度已经达到最优水平，没有进一步降低的空间。
原因非常简单：你的输入是固定长度的4位数字，所有遍历、查询操作的执行次数都是固定常数，本身就是O(1)的常数时间复杂度，不存在更低的复杂度等级。
如果拓展到任意k位无重复数字的通用比对场景，你的现有实现时间复杂度为O(k)，这也是该问题的理论最优值——要完成比对你至少需要遍历两个数字的每一位各一次，不可能得到比线性时间更低的复杂度。 #

可选效率/可读性优化方案 #

你原来的实现逻辑是完全正确的，如果想要简化代码、提升实际运行速度，可以参考如下思路：
所有相同数字要么位置匹配（计入x）要么位置不匹配（计入y），因此只需先算出两个数字的公共数字总数，减去位置匹配的x，即可直接得到y，不需要额外存储位置字典。
优化后代码：

def compare(n1, n2):
    s1, s2 = str(n1), str(n2)
    # 统计两个数的公共数字总数
    common_count = len(set(s1) & set(s2))
    # 统计位置相同的位数x
    x = sum(a == b for a, b in zip(s1, s2))
    # 剩余公共数字就是位置不同的y
    y = common_count - x
    return x, y

这个实现的优势：

• 逻辑更简洁易读，不需要手动维护字典存储位置映射
• 用到的集合操作、生成器表达式都是Python底层C实现的，实际运行速度比手写Python循环的版本更快
• 天然支持任意长度的无重复数字比对，不需要修改代码逻辑

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