Home 零对冲(ZeroHedge)每日HackerNews

Python 内置类型操作的时间复杂度
Time complexity of operations on Python's built-in types

原始链接: https://docs.python.org/3.16/library/time-complexity.html

本文档使用大 O 表示法概述了标准 CPython 内置类型的操作时间复杂度，其中 *n* 代表容器大小，*k* 代表输入参数。 * **列表 (Lists)：** 访问和追加操作为 $O(1)$。由于元素位移，在列表开头进行插入和删除的操作复杂度为 $O(n)$。排序为 $O(n \log n)$。 * **元组 (Tuples)：** 由于不可变，复制操作为 $O(1)$。大多数访问操作与列表类似，但没有修改成本。 * **字典 (Dictionaries) 和集合 (Sets)：** 在假设哈希高效的前提下，查找、插入和删除的平均性能为 $O(1)$。在最坏情况下（哈希冲突），性能可能降至 $O(n)$。 * **字符串 (Strings) 和字节串 (Bytes)：** 这些不可变序列的长度获取和索引操作为 $O(1)$，搜索和拼接操作为 $O(n)$。`bytearray` 在修改操作上的复杂度与列表类似。 * **内存视图 (Memoryviews)：** 允许在不复制的情况下高效访问数据；切片操作为 $O(1)$。 * **范围 (Ranges)：** 按需计算值，因此包括索引和成员测试在内的大多数操作复杂度均为 $O(1)$。 **注意：** 这些基准测试专门适用于 CPython。其他实现或对象子类化可能会导致不同的性能情况。性能假设字典和集合键的哈希处理是最佳的。

Hacker News最新 | 过往 | 评论 | 提问 | 展示 | 招聘 | 提交登录Python内置类型操作的时间复杂度 (python.org)9分，由theanonymousone于2小时前发布 | 隐藏 | 过往 | 收藏 | 讨论 帮助 指南 | 常见问题 | 列表 | API | 安全 | 法律 | 申请YC | 联系 搜索：
相关文章
原文

This page documents the time complexity of various operations on built-in types in CPython. Other Python implementations may have different performance characteristics. Additionally, the listed costs assume exact built-in types, as instances of subclasses may have different costs.

We use Big O notation to describe how the running time of an operation grows with the size of its inputs. Unless stated otherwise, n denotes the number of elements currently in the container, and k is the value of a numeric parameter, such as an index or a repeat count.

list

Lists are mutable sequences; for more detail on the implementation see How are lists implemented in CPython?. The largest costs come from growing beyond the current allocation size (because everything must move), or from inserting or deleting somewhere near the beginning (because everything after that must move). If you need to add or remove at both ends, consider using a collections.deque instead.

Operation

Complexity

Copy (l.copy())

O(n)

Append (l.append(x))

O(1)

Pop (l.pop(k))

O(n - k)

Insert (l.insert(k, x))

O(n - k)

Get item (l[k])

O(1)

Set item (l[k] = x)

O(1)

Delete item (del l[k])

O(n - k)

Iteration

O(n)

Get slice (l[i:j])

O(j - i)

Set slice (l[i:j] = t)

O(j - i) if len(t) == j - i, otherwise O(n - i + len(t))

Delete slice (del l[i:j])

O(n - i)

Extend (l.extend(t))

O(len(t))

Sort (l.sort())

O(n log n)

Concatenate (l1 + l2)

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

Multiply (l * k)

O(nk)

x in l

O(n)

min(l), max(l)

O(n)

Get length (len(l))

O(1)

tuple

A tuple is an immutable sequence. Because a tuple can never change, there are no insertion or deletion costs, and making a copy simply returns the same object, so is constant time (O(1)).

Operation

Complexity

Copy (tuple(t))

O(1)

Get item (t[k])

O(1)

Get slice (t[i:j])

O(j - i)

Concatenate (t1 + t2)

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

Multiply (t * k)

O(nk)

Iteration

O(n)

x in t

O(n)

min(t), max(t)

O(n)

Get length (len(t))

O(1)

dict, frozendict

The times listed for dict objects are average-case times, as they assume the hash function for the objects is sufficiently robust to make collisions uncommon. They also assume the keys are well-distributed among the set of possible keys. In the worst case, when every key hashes to the same value, each of the O(1) operations below instead takes O(n) time. They also assume that hashing and comparing a key is O(1). For more detail on the implementation, see How are dictionaries implemented in CPython?.

A frozendict is immutable, so it does not support setting, deleting, or updating items. The other operations below apply to it at the same costs.

Operation

Complexity

key in d

O(1)

Copy (d.copy())

O(n)

Get item (d[key], d.get(key))

O(1)

Set item (d[key] = value)

O(1)

Delete item (del d[key], d.pop(key))

O(1)

Update (d.update(t), d |= t)

O(len(t))

Iteration

O(n)

Get length (len(d))

O(1)

set, frozenset

See dict as the set and frozenset implementations are similar, and the same caveats apply. In the worst case, O(1) operations instead take O(n) time, and operations that look up every element degrade accordingly.

A frozenset is immutable, so it does not support adding, discarding, or the in-place update operations. The others below apply to it at the same costs.

Operation

Complexity

x in s

O(1)

Copy (s.copy())

O(n)

Add (s.add(x))

O(1)

Discard (s.discard(x), s.remove(x))

O(1)

Union (s1 | s2, s1.union(s2))

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

Update (s1 |= s2, s1.update(s2))

O(len(s2))

Intersection (s1 & s2, s1.intersection(s2))

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

Intersection update (s1 &= s2, s1.intersection_update(s2))

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

Difference (s1 - s2, s1.difference(s2))

O(len(s1))

Difference update (s1 -= s2, s1.difference_update(s2))

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

Symmetric difference (s1 ^ s2, s1.symmetric_difference(s2))

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

Symmetric difference update (s1 ^= s2, s1.symmetric_difference_update(s2))

O(len(s2))

Get length (len(s))

O(1)

str, bytes, bytearray

str and bytes objects are immutable sequences of characters and bytes, respectively. As with tuples, copying one returns the original object. A bytearray is mutable, and additionally supports the mutating operations of list (except sort()), at the same costs. However, deleting at the front with del (del b[0], del b[:k]) only advances the start of the buffer instead of moving the remaining bytes, and is amortized O(1).

Operation

Complexity

Get item (s[k])

O(1)

Get slice (s[i:j])

O(j - i)

Concatenate (s + t)

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

Multiply (s * k)

O(nk)

Substring search (x in s, s.find(x), s.index(x))

O(n)

Reverse substring search (s.rfind(x), s.rindex(x))

O(n × len(x))

Encode or decode

O(n)

Iteration

O(n)

Get length (len(s))

O(1)

memoryview

memoryview objects allow Python code to access the internal data of an object that supports the buffer protocol without copying. In particular, slicing a memory view returns a new view onto the same buffer.

Operation

Complexity

Create (memoryview(obj))

O(1)

Get item (v[k])

O(1)

Get slice (v[i:j])

O(1)

Index (v.index(x))

O(n)

Count (v.count(x))

O(n)

Convert to bytes (v.tobytes(), bytes(v))

O(n)

Get length (len(v))

O(1)

range

A range object computes its items on demand from its start, stop and step values, so most operations do not depend on the length of the range.

Operation

Complexity

Get item (r[k])

O(1)

Get slice (r[i:j])

O(1)

x in r

O(1)

Index and count (r.index(x), r.count(x))

O(1)

Iteration

O(n)

min(r), max(r)

O(n)

Get length (len(r))

O(1)

Notes

联系我们 contact @ memedata.com