Python集合相关代码的时间复杂度疑问：为何运行耗时远超预期

你的判断是对的，这段代码的时间复杂度确实是O(nm)，核心原因在于Python集合（set）的底层实现特性：

Python的set基于哈希表实现，当你创建包含n个元素的集合时，哈希表会分配足够数量的桶来容纳这些元素。而当你删除集合中所有元素后，Python并不会自动收缩哈希表的桶数量——也就是说，哈希表的大小仍然维持在能容纳n个元素的级别。

这就导致了一个关键问题：每次迭代集合x时，Python会遍历哈希表的所有桶（包括那些已经空了的桶），而不是只遍历存有元素的桶。哪怕集合里最后只剩1个元素，单次迭代x的时间复杂度依然是O(n)。外层循环执行m次，总时间复杂度就变成了O(nm)，这就是代码运行耗时远超预期的原因。

你可以通过修改代码验证这个结论：删除所有元素后，不要在原集合上添加元素，而是重新创建一个新的集合。新集合的哈希表会从最小尺寸开始分配，迭代时只需要遍历少量桶，耗时会大幅降低：

import time

def test(n, m):
    answer = 0
    start = time.time()
    x = set([i for i in range(n)])
    for i in list(x):
        x.remove(i)
    x.add(1234)
    for i in range(m):
        for j in x:
            answer+=1
    return time.time() - start

def test_optimized(n, m):
    answer = 0
    start = time.time()
    x = set([i for i in range(n)])
    for i in list(x):
        x.remove(i)
    # 重新创建集合，而非复用原哈希表
    x = {1234}
    for i in range(m):
        for j in x:
            answer+=1
    return time.time() - start

print("原代码耗时:", test(100000,100000))
print("优化后耗时:", test_optimized(100000,100000))

运行后你会发现，优化后的代码耗时会缩短到原代码的几百分之一甚至更低。

内容的提问来源于stack exchange，提问作者서태영