列表推导式比O(n²)嵌套循环更快，是否代表其时间复杂度更低？

你的初始认知没有问题：不管是用列表推导式还是手写等价嵌套循环，这段代码的渐近时间复杂度都是严格O(n²)。你观察到的运行速度差是Python解释器的实现优化带来的常数项区别，和算法复杂度的高低没有关系。

先把两种写法的等价逻辑摆出来，方便对比开销：

• 手写同逻辑嵌套循环的常规实现：

ab_list = []
for a in A:
    for b in B:
        ab_list.append(a + b)
AB = Counter(ab_list)

• 你用到的列表推导式写法：

AB = Counter([(a+b) for a in A for b in B])

二者的核心操作次数完全一致：都要遍历A中每个元素，搭配B中每个元素完成一次加法，收集所有和之后再做频次统计。速度差不是因为少做了遍历，而是Python解释器从设计上就给列表推导式做了路径优化：

• 列表推导式不会走“手动写空列表、逐轮调用append方法”的通用执行路径。解释器会为列表推导式生成专用的LIST_APPEND字节码，直接在解释器内部的执行栈上完成元素追加，跳过了手写循环里每轮迭代都要重复做的冗余操作：
  • 每轮从局部作用域查找ab_list的对象引用
  • 查找该列表对象的append方法属性
  • 为append方法调用创建独立栈帧、传递参数
    这些操作每轮都要执行一次，属于固定的常数开销，不会随输入规模的增长出现量级变化。
• 列表推导式的循环跳转逻辑运行在解释器的快速路径上，没有手写循环中逐轮的作用域合法性检查、临时变量加载的冗余流程，整体执行流更短、指令密度更高。

这里很容易把两个概念混淆：

渐近时间复杂度描述的是当输入规模n趋向无穷大时，算法所需总操作量的增长趋势，不关心实现层面的常数优化带来的绝对速度差异。

哪怕列表推导式比手写嵌套循环快2~3倍，只要二者的总操作量都是随n²的比例增长，它们的时间复杂度就完全相同。举个直观的例子：当n从1000扩大到10000（规模翻10倍），两种写法的运行时间都会同步扩大100倍，增长的斜率没有任何变化，自然不存在复杂度的差异。
简单总结：

• 列表推导式更快，是因为它的常数项开销更小
• 复杂度完全一致，是因为二者的操作量增长趋势没有改变

你在LeetCode上观察到的速度差，本质是测试集规模下的常数项表现，不会影响算法的复杂度判定。如果要进一步优化常数开销，甚至可以把列表推导式替换成生成器表达式直接传给Counter，省掉提前生成完整中间列表的内存和时间开销，这依然是常数项的优化，整个算法的渐近复杂度还是O(n²)，不会变。

内容的提问来源于stack exchange，提问作者satta sunder talukder