两类提取唯一电话号码算法的时间复杂度对比及验证问询

嘿，你的初步猜测不完全准确哦——第一种方法的平均时间复杂度确实是O(n)，但第二种方法的最坏时间复杂度是O(n²)，下面我来详细拆解两者的复杂度：

第一种算法（基于集合的实现） #

先看这段核心代码：

print(f"There are {len(set(list(zip(*texts))[0]))} different telephone numbers in the records.")

我们一步步拆解每部分的时间开销：

• zip(*texts)：将二维列表texts转置，本质是遍历所有n条记录的每个元素，时间复杂度O(n)（这里n是记录总数）。
• list(zip(*texts))[0]：提取转置后的第一列（所有电话号码），生成这个列表需要遍历所有n个电话号码，时间复杂度O(n)。
• set(...)：将电话号码列表转换为集合。Python的集合基于哈希表实现，每个元素的插入操作平均时间是O(1)，处理n个元素的总平均时间就是O(n)。（注：最坏情况如果所有元素哈希碰撞，会退化为O(n²)，但实际工程中这种情况极少，我们通常按平均复杂度分析）
• len(set(...))：获取集合长度是常数时间O(1)。

把这些加起来，总时间复杂度是O(n) + O(n) + O(n) + O(1) = 平均O(n)。

第二种算法（基于列表的去重实现） #

再看这段循环代码：

phone_book = []
for phone_number, _, _ in texts:
    if phone_number not in phone_book:
        phone_book.append(phone_number)
print(f"There are {len(phone_book)} different telephone numbers in the records.")

这里的性能瓶颈在phone_number not in phone_book这一步：

• 列表的in操作是线性扫描，每次检查需要遍历当前phone_book的所有元素，时间复杂度是O(k)，其中k是当前phone_book的长度。
• 假设所有电话号码都是唯一的，那么第一次检查时k=0（O(1)），第二次k=1（O(1)），第三次k=2（O(2)）……第n次k=n-1（O(n)）。总时间开销是1+2+3+...+(n-1) = n(n-1)/2，对应的时间复杂度是O(n²)。
• 即使存在重复号码，最坏情况下（比如只有最后一个号码是重复的），总时间依然是O(n²)；只有当所有号码都完全重复时，才会达到最好情况O(n)，但我们分析时间复杂度通常关注最坏情况。

总结 #

• 第一种方法（集合实现）：平均时间复杂度O(n)，效率更高，是Python中做去重统计的推荐写法。
• 第二种方法（列表遍历去重）：最坏时间复杂度O(n²)，当记录数n很大时，性能会显著下降。

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