Python 列表切片的时间复杂度分析

Python列表切片时间复杂度为O(k)而非O(n)，因只复制索引范围内k个元素，不遍历整个原列表；负索引换算、空切片等均为O(1)，步长切片仍为O(k)；浅拷贝导致可变对象修改影响原列表。

Python 列表切片操作的时间复杂度是 O(k)，其中 k 是切片结果的长度（即新列表中元素个数），而不是原列表长度 n。

为什么不是 O(n)？

切片会创建一个新列表，并逐个复制选中的元素。它不会遍历整个原列表，只访问索引范围内的元素。例如：

• lst[1000:1005] —— 即使 lst 有 100 万个元素，也只复制 5 个，耗时与 100 万无关；
• lst[:] 或 lst[0:len(lst)] —— 复制全部元素，此时 k = n，退化为 O(n)；
• lst[::2] —— 步长不为 1 时，仍需访问约 k 个位置并复制对应元素，仍是 O(k)。

切片不改变原列表，但内存开销不可忽略

切片生成的是浅拷贝：新列表对象独立，但其中的元素引用与原列表相同。这意味着：

• 数值、字符串等不可变对象无额外风险；
• 若列表含可变对象（如子列表、字典），修改切片中的子对象会影响原列表对应位置；
• 即使只取一个元素（如 lst[5:6]），也会分配新列表对象并复制引用，存在常数级开销。

常见误区提醒

以下操作看似“轻量”，实则未必：

• lst[i:j] 当 i > j 时返回空列表，时间复杂度为 O(1)（仅创建空列表，不遍历）；
• lst[i:j:k]（带步长）的时间复杂度仍是 O(k)，因为内部循环执行约 ⌈(j−i)/k⌉ 次；
• 负索引（如 lst[-3:]）需先换算为正索引，但换算为 O(1)，不影响整体复杂度。

替代方案：需要“视图”时考虑其他结构

如果只是想遍历某段而不复制数据，切片不是最优解：

• 用 for item in lst[i:j]: ... —— Python 内部对切片迭

  

  代做了优化，可能避免完整构建中间列表（尤其在 CPython 3.11+ 中）；
• 处理超大列表时，可改用 itertools.islice(lst, i, j)，返回迭代器，空间复杂度 O(1)，时间上按需取值；
• 科学计算场景推荐 numpy.ndarray，其切片是真正的视图（view），O(1) 时间 + 零复制。