Python 切片操作的复杂度与优化

python切片时间复杂度为O(k)，k为结果长度；list/str/tuple切片均创建新对象，range切片为O(1)，自定义类由__getitem__决定，numpy切片通常为O(1)视图。

Python 切片的时间复杂度到底是多少

对 list、str、tuple 等内置序列做切片，时间复杂度是 O(k)，其中 k 是切片结果的长度，不是原序列长度。这意味着 a[1000000:1000005] 很快，但 a[:1000000] 会拷贝一百万个元素。

根本原因：Python 切片会创建新对象（浅拷贝），不是视图。即使你只取 5 个元素，解释器仍需逐个复制引用（对 list）或字节（对 str）。

• bytes 和 bytearray 切片也是 O(k)，但底层有小优化（如短切片走 memmove）
• range 对象支持切片，但返回的是新 range，不触发实际遍历，所以是 O(1)
• 自定义类实现 __getitem__ 时，切片行为完全由你控制——可能 O(1)，也可能 O(n)

什么时候切片会意外变慢

表面看是切片，实际触发隐式遍历或转换：

• 对生成器或 itertools.chain 做切片：必须先转成 list 才能索引，变成 O(n) —— itertools.islice(gen, start, stop) 才是正确选择
• 用负步长切片（如 a[::-1]）：仍为 O(k)，但无法复用原缓冲区，强制分配新内存 + 反向拷贝，比正向略慢
• 在循环中反复切片大列表（如 for i in range(len(a)): sub = a[i:i+10]）：每次都是新拷贝，累积开销明显
• 对 numpy.ndarray 做切片：返回视图（view），O(1)，但前提是没触发 copy（比如跨步太大会降级为 copy）

替代切片的低开销方案

如果只是“访问”而非“拥有”，优先避免切片：

立即学习“Python免费学习笔记（深入）”；

• 用 collections.deque 的 maxlen 维护滑动窗口，比不断切片快得多
• 需要随机访问子序列？考虑传 (seq, start, stop) 三元组，让下游按需取值
• 处理大文本时，用 memoryview 包装 bytes 后切片：仍是 O(k)，但避免了 Python 对象头开销，适合高频小切片
• 真要多次截取同一段？缓存切片结果（如 cached = a[100:200]），别重复计算

为什么 str 切片比 list 快一点

不是算法差异，而是数据结构特性：str 是不可变的紧凑字节数组（Unicode 下是 UCS-2/UCS-4 编码块），切片可直接用 memcpy；而 list 存的是指针数组，每个元素要单独增加引用计数，多一层间接和计数开销。

实测差距通常在 10%–30%，但一旦涉及超长字符串（GB 级）或极端高频调用（如解析器内部），这点差异会放大。

真正容易被忽略的是：所有这些优化都建立在“你确实需要一个新副本”的前提上。如果只是判断某段内容是否存在，用 in、str.startswith() 或正则预编译，往往比切片再比较更省。