初始化指定大小列表的时间复杂度：[None]*n的复杂度与常数级实现方式

嘿，这个问题问得很精准！我来给你一步步拆解：

一、lst = [None] * n的时间复杂度 #

这段代码的时间复杂度是线性级O(n)。

原因是：在CPython（Python的主流实现）中，当你执行[None] * n时，底层会先创建一个长度为n的列表对象，然后逐个将每个位置的元素设置为None的引用。虽然所有元素指向的是同一个None对象，但这个“填充n个位置”的过程需要遍历n次，时间消耗和n的大小成正比，因此是O(n)复杂度。

你可以简单测试一下：创建n=10^6的列表和n=10^3的列表，前者的耗时会明显更长，这也能佐证它是线性级的。

二、有没有常数级O(1)的实现方法？ #

严格来说，Python的内置list类型本身是动态数组结构，必须预先分配足够的内存来存储n个元素的引用，因此无法在O(1)时间内创建一个真正的、长度为n的list对象。但如果你的需求是拥有一个可以按索引访问、逻辑上长度为n的“空容器”，可以用以下两种思路实现常数级初始化：

1. 自定义延迟初始化的“懒列表” #

这种方式不会预先分配所有元素的空间，而是在实际访问元素时才存储对应的值，初始化时只记录容器大小和默认值，时间复杂度是O(1)：

class LazyList:
    def __init__(self, size, default=None):
        self._size = size
        self._default = default
        self._data = {}  # 只存储被修改过的元素
    
    def __getitem__(self, idx):
        if not 0 <= idx < self._size:
            raise IndexError("list index out of range")
        return self._data.get(idx, self._default)
    
    def __setitem__(self, idx, value):
        if not 0 <= idx < self._size:
            raise IndexError("list index out of range")
        self._data[idx] = value
    
    def __len__(self):
        return self._size

使用示例：

lst = LazyList(1000)  # O(1)初始化
print(lst[500])  # 输出None
lst[500] = "hello"
print(lst[500])  # 输出hello

2. 使用collections.deque（限定长度） #

如果你不需要严格的list类型，只是需要一个固定大小的可索引容器，可以用deque(maxlen=n)。它的初始化是O(1)的，因为它不会预先填充元素，只是设定了最大长度：

from collections import deque

dq = deque(maxlen=1000)  # O(1)初始化
# 注意：此时deque的长度是0，当你append元素时，会自动维护长度不超过1000
# 如果需要逻辑上的"空元素"，可以先append默认值，但那会回到O(n)
# 所以这种方式适合后续逐步填充元素的场景，初始化本身是常数级

不过要注意：这两种方式都不是真正的list，如果你的代码必须依赖list的所有内置方法（比如切片、排序等），那还是得回到O(n)的初始化方式。

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