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

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

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


"list"
======

Lists are mutable sequences; for more detail on the implementation see
列表是如何在 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.

+----------------------------------------------------+----------------------------------------------------+
| 运算                                               | 复杂度                                             |
|====================================================|====================================================|
| 拷贝 ("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"
=======

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)).

+----------------------------------------------------+----------------------------------------------------+
| 运算                                               | 复杂度                                             |
|====================================================|====================================================|
| 拷贝 ("tuple(t)")                                  | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| 获取条目 ("t[k]")                                  | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| 获取切片 ("t[i:j]")                                | *O*(*j* - *i*)                                     |
+----------------------------------------------------+----------------------------------------------------+
| 拼接 ("t1 + t2")                                   | *O*(len(*t1*) + len(*t2*))                         |
+----------------------------------------------------+----------------------------------------------------+
| Multiply ("t * k")                                 | *O*(*nk*)                                          |
+----------------------------------------------------+----------------------------------------------------+
| 迭代                                               | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| "x in t"                                           | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| "min(t)", "max(t)"                                 | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Get length ("len(t)") [5]                          | *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
字典是如何在 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.

+----------------------------------------------------+----------------------------------------------------+
| 运算                                               | 复杂度                                             |
|====================================================|====================================================|
| "key in d"                                         | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Copy ("d.copy()") [6] [7]                          | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Get item ("d[key]", "d.get(key)")                  | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Set item ("d[key] = value") [1]                    | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Delete item ("del d[key]", "d.pop(key)")           | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Update ("d.update(t)", "d |= t") [1] [3] [7]       | *O*(len(*t*))                                      |
+----------------------------------------------------+----------------------------------------------------+
| Iteration [7]                                      | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Get length ("len(d)") [5]                          | *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.

+----------------------------------------------------+----------------------------------------------------+
| 运算                                               | 复杂度                                             |
|====================================================|====================================================|
| "x in s"                                           | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Copy ("s.copy()") [6] [7]                          | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Add ("s.add(x)") [1]                               | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Discard ("s.discard(x)", "s.remove(x)")            | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Union ("s1 | s2", "s1.union(s2)") [7]              | *O*(len(*s1*) + len(*s2*))                         |
+----------------------------------------------------+----------------------------------------------------+
| Update ("s1 |= s2", "s1.update(s2)") [1] [7]       | *O*(len(*s2*))                                     |
+----------------------------------------------------+----------------------------------------------------+
| Intersection ("s1 & s2", "s1.intersection(s2)")    | *O*(min(len(*s1*), len(*s2*)))                     |
| [7] [8]                                            |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| Intersection update ("s1 &= s2",                   | *O*(min(len(*s1*), len(*s2*)))                     |
| "s1.intersection_update(s2)") [1] [7] [8]          |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| Difference ("s1 - s2", "s1.difference(s2)") [7]    | *O*(len(*s1*))                                     |
| [9]                                                |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| Difference update ("s1 -= s2",                     | *O*(min(len(*s1*), len(*s2*)))                     |
| "s1.difference_update(s2)") [1] [7] [8]            |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| Symmetric difference ("s1 ^ s2",                   | *O*(len(*s1*) + len(*s2*))                         |
| "s1.symmetric_difference(s2)") [7]                 |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| Symmetric difference update ("s1 ^= s2",           | *O*(len(*s2*))                                     |
| "s1.symmetric_difference_update(s2)") [1] [7]      |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| Get length ("len(s)") [5]                          | *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).

+----------------------------------------------------+----------------------------------------------------+
| 运算                                               | 复杂度                                             |
|====================================================|====================================================|
| Get item ("s[k]")                                  | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Get slice ("s[i:j]")                               | *O*(*j* - *i*)                                     |
+----------------------------------------------------+----------------------------------------------------+
| Concatenate ("s + t") [10]                         | *O*(len(*s*) + len(*t*))                           |
+----------------------------------------------------+----------------------------------------------------+
| Multiply ("s * k")                                 | *O*(*nk*)                                          |
+----------------------------------------------------+----------------------------------------------------+
| Substring search ("x in s", "s.find(x)",           | *O*(*n*)                                           |
| "s.index(x)") [11]                                 |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| Reverse substring search ("s.rfind(x)",            | *O*(*n* × len(*x*))                                |
| "s.rindex(x)") [11] [12]                           |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| Encode or decode [13]                              | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| 迭代                                               | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Get length ("len(s)") [5]                          | *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.

+----------------------------------------------------+----------------------------------------------------+
| 运算                                               | 复杂度                                             |
|====================================================|====================================================|
| Create ("memoryview(obj)")                         | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Get item ("v[k]")                                  | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Get slice ("v[i:j]")                               | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Index ("v.index(x)") [11] [14]                     | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Count ("v.count(x)") [14]                          | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Convert to bytes ("v.tobytes()", "bytes(v)")       | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Get length ("len(v)") [5]                          | *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.

+----------------------------------------------------+----------------------------------------------------+
| 运算                                               | 复杂度                                             |
|====================================================|====================================================|
| Get item ("r[k]")                                  | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Get slice ("r[i:j]")                               | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| "x in r" [15]                                      | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Index and count ("r.index(x)", "r.count(x)") [15]  | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| 迭代                                               | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| "min(r)", "max(r)"                                 | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Get length ("len(r)") [5]                          | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+


备注
====

[1] Amortized. An individual operation may occasionally be *O*(*n*)
    when the underlying storage is resized, but this cost is spread
    over many operations, depending on the history of the container.

[2] Popping or deleting the element at index *k* of a list of size *n*
    shifts all elements after *k* one slot to the left, moving *n* -
    *k* - 1 elements; inserting at index *k* shifts the elements from
    *k* onwards one slot to the right, moving *n* - *k* elements. The
    worst case is index 0, where the whole rest of the list has to be
    moved; the average case, an index in the middle of the list, takes
    *O*(*n*/2) = *O*(*n*) operations; and operating at the end of the
    list moves nothing and is *O*(1).

[3] Plus the cost of iterating over *t*, which may be expensive for an
    arbitrary iterable.

[4] This is the worst case scenario. Sorting is adaptive and input
    that is already sorted or reverse-sorted takes only *O*(*n*)
    comparisons. See Objects/listsort.txt for more information.

[5] The number of elements is stored in the object, so "len()" does
    not need to count them.

[6] Copying a "frozendict" or a "frozenset" is *O*(1) as it returns
    the original object.

[7] These operations scan the container's internal hash table, which
    is not shrunk when elements are removed. After removing most
    elements, they still take time proportional to the container's
    former size, until a later insertion triggers a resize.

[8] *O*(len(*t*)) if *t* is not a set.

[9] *O*(len(*s*) + len(*t*)) if *t* is not a set.

[10] Each concatenation builds a new object, so building a string by
     concatenating many pieces in a loop is quadratic in the total
     length. See the note on concatenating immutable sequences for
     alternatives.

[11] With *start* and *end* arguments, *n* is the length of the region
     searched rather than of *s*, and unlike slicing nothing is
     copied.

[12] This is the worst case. Reverse searches are *O*(*n*) on typical
     input. Forward searches instead use a more elaborate algorithm
     with a linear worst case, described in
     Objects/stringlib/stringlib_find_two_way_notes.txt.

[13] This assumes a codec that does a constant amount of work per
     character.

[14] These unpack and compare each element individually, so they are
     much slower than the equivalent "bytes" methods.

[15] Assuming "int" or "bool" arguments. For other types, the range is
     searched like any other sequence in *O*(*n*) time.
