内置类型操作的时间复杂度

本页面记录了 CPython 中各种内置类型操作的时间复杂度。其他 Python 实现可能具有不同的性能表现。此外，下面列出的时间复杂度假定操作对象是内置类型本身，对于这些类型的子类的实例，相同操作的开销可能有所不同。

本页面中使用 Big O notation 来表示某个操作所需的运行时间随输入规模增长的速度。除非另有说明，n 代表当前这个容器中的元素数量，k 表示某个数值参数的值，例如索引或重复次数。

list

列表是可变的序列；有关实现的更多细节，请参阅 列表是如何在 CPython 中实现的？。最大的开销通常来自超出当前分配大小后的扩展（因为所有元素都必须移动），或来自在接近起始位置处插入或删除元素（因为该位置之后的所有元素都必须移动）。如果需要在两端同时添加或删除元素，可以考虑改用 collections.deque。

运算

复杂度

拷贝 (l.copy())

O(n)

添加 (l.append(x)) [1]

O(1)

弹出 (l.pop(k)) [1] [2]

O(n - k)

插入 (l.insert(k, x)) [1] [2]

O(n - k)

获取条目 (l[k])

O(1)

设置条目 (l[k] = x)

O(1)

删除条目 (del l[k]) [2]

O(n - k)

迭代

O(n)

获取切片 (l[i:j])

O(j - i)

设置切片 (l[i:j] = t) [1]

如果 len(t) == j - i 则为 O(j - i)，否则为 O(n - i + len(t))

删除条目 (del l[i:j])

O(n - i)

扩展 (l.extend(t)) [1] [3]

O(len(t))

排序 (l.sort()) [4]

O(n log n)

拼接 (l1 + l2)

O(len(l1) + len(l2))

相乘 (l * k)

O(nk)

x in l

O(n)

min(l), max(l)

O(n)

获取长度 (len(l)) [5]

O(1)

tuple

tuple 是一个 不可变 序列。由于元组永远不会改变，因此不存在插入或删除开销；创建副本只会返回同一个对象，因此属于常数时间操作（O(1)）。

运算

复杂度

拷贝 (tuple(t))

O(1)

获取条目 (t[k])

O(1)

获取切片 (t[i:j])

O(j - i)

拼接 (t1 + t2)

O(len(t1) + len(t2))

相乘（t * k）

O(nk)

迭代

O(n)

x in t

O(n)

min(t), max(t)

O(n)

获取长度（len(t)） [5]

O(1)

dict, frozendict

dict 对象中列出的时间均为平均情况下的时间；这些时间假设对象的哈希函数具有足够的鲁棒性，从而使得碰撞发生概率较低。同时，这些时间还假设键在可能的键集合中分布良好。在最坏情况下，当每个键哈希到相同值时，以下每项 O(1) 操作的实际耗时将变为 O(n)。此外，这些时间还假设键的哈希运算与比较操作的时间复杂度为 O(1)。有关实现的更多细节，请参阅 字典是如何在 CPython 中实现的？。

frozendict 是不可变的，因此不支持对其中条目进行设置、删除或更新。以下其他操作同样以相同的开销对其生效。

运算

复杂度

key in d

O(1)

复制（d.copy()） [6] [7]

O(n)

获取元素（d[key], d.get(key)）

O(1)

设置元素（d[key] = value） [1]

O(1)

删除元素（del d[key], d.pop(key)）

O(1)

更新（d.update(t), d |= t） [1] [3] [7]

O(len(t))

迭代 [7]

O(n)

获取长度（len(d)） [5]

O(1)

set, frozenset

可将 dict 视为参考实现，因为 set 和 frozenset 的实现方式相似，且同样存在上述注意事项。在最坏情况下，原本为 O(1) 次操作的耗时会增至 O(n)；而需要遍历每个元素的操作，其性能也会相应下降。

frozenset 即为 不可变，因此不支持添加、丢弃或就地更新操作。以下其他操作同样以相同代价适用于它。

运算

复杂度

x in s

O(1)

复制（s.copy()） [6] [7]

O(n)

添加（s.add(x)） [1]

O(1)

丢弃（s.discard(x), s.remove(x)）

O(1)

并集（s1 | s2, s1.union(s2)） [7]

O(len(s1) + len(s2))

更新（s1 |= s2, s1.update(s2)） [1] [7]

O(len(s2))

交集（s1 & s2, s1.intersection(s2)） [7] [8]

O(min(len(s1), len(s2)))

交集更新（s1 &= s2, s1.intersection_update(s2)） [1] [7] [8]

O(min(len(s1), len(s2)))

差集（s1 - s2, s1.difference(s2)） [7] [9]

O(len(s1))

差集更新（s1 -= s2, s1.difference_update(s2)） [1] [7] [8]

O(min(len(s1), len(s2)))

对称差集（s1 ^ s2, s1.symmetric_difference(s2)） [7]

O(len(s1) + len(s2))

对称差集更新（s1 ^= s2, s1.symmetric_difference_update(s2)） [1] [7]

O(len(s2))

获取长度（len(s)） [5]

O(1)

str, bytes, bytearray

str 和 bytes 对象分别是不可变的字符序列和字节序列。与元组类似，复制其中一个对象会返回原始对象。bytearray 是可变的，此外还以相同的开销支持 list 的修改操作（sort() 除外）。不过，使用 del （del b[0]、del b[:k]）从前端删除时，只会将缓冲区起始位置前移，而不会移动剩余的字节；其摊还复杂度为 O(1)。

运算

复杂度

获取元素（s[k]）

O(1)

获取切片（s[i:j]）

O(j - i)

拼接（s + t） [10]

O(len(s) + len(t))

相乘（s * k）

O(nk)

子字符串搜索 (x in s，s.find(x)，s.index(x)) [11]

O(n)

反向子串搜索（s.rfind(x), s.rindex(x)） [11] [12]

O(n × len(x))

编码或解码 [13]

O(n)

迭代

O(n)

获取长度（len(s)） [5]

O(1)

memoryview

memoryview 对象允许 Python 代码在不进行复制的情况下访问支持 buffer protocol 的对象内部数据。具体而言，对内存视图进行切片操作会返回一个指向同一缓冲区的新视图。

运算

复杂度

创建（memoryview(obj)）

O(1)

获取元素（v[k]）

O(1)

获取切片（v[i:j]）

O(1)

索引（v.index(x)） [11] [14]

O(n)

计数（v.count(x)） [14]

O(n)

转换为字节（v.tobytes()、bytes(v)）

O(n)

获取长度（len(v)） [5]

O(1)

range

range 对象会根据其 start、stop 和 step 值按需计算其中的项目，因此大多数操作并不依赖于该范围的长度。

运算

复杂度

获取元素（r[k]）

O(1)

获取切片（r[i:j]）

O(1)

x in r [15]

O(1)

索引并计数 (r.index(x)，r.count(x)) [15]

O(1)

迭代

O(n)

min(r), max(r)

O(n)

获取长度（len(r)） [5]

O(1)

备注