Python中[0]*n创建全零列表的时间复杂度是O(1)还是O(n)？

首先先厘清两种写法的执行逻辑差异：

• 你给出的列表推导式l = [0 for i in range(n)]，本质是在Python虚拟机层面循环执行n次操作：每次迭代生成一个0对象、将对象引用追加到列表中，整个过程需要执行n轮Python字节码，时间复杂度确实是O(n)。
• 面试官提到的[0]*n的O(1)时间复杂度，是相对于Python字节码执行层面的开销定义的，并非说完全没有和n相关的资源消耗，具体底层实现逻辑如下：

补充说明：实际内存分配的物理开销仍然和n的大小正相关，但整个操作不需要在Python层面逐次循环，所有核心逻辑都在C语言层面完成，因此从Python代码执行的耗时维度看，开销几乎不随n的增长线性提升。

Python的列表本质是C语言实现的动态数组，存储的是元素对象的引用指针，[0]*n的执行流程是：

1. 先计算新列表需要的总内存：列表结构体固定开销 + n个指针的存储容量
2. 直接调用C层面的内存分配接口，向操作系统申请一块连续的对应大小的内存，这一步是系统级调用，跳过了Python虚拟机的指令调度
3. 因为0是Python的小整数常驻对象（单例），直接把申请到的内存块里的n个指针位置，批量赋值为0对象的内存地址，这一步是C层面的内存批量赋值操作，不需要逐次处理
4. 把初始化好的内存块挂载到列表结构体中，直接返回完整的列表对象

整个过程只有固定次数的C层面调用，不需要执行n次Python字节码，因此被定义为O(1)时间复杂度，实际运行速度远快于列表推导式，n越大性能差异越明显。

额外注意：该实现仅在元素为不可变对象时不会有逻辑问题，如果用[[]]*n这类写法创建可变对象的列表，会得到n个指向同一个可变对象的引用，修改任意一个都会同步修改所有元素，这是该实现的固有特性，使用时需要注意规避。

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