Python 内置的数据结构，如 列表、集合 和 字典，提供了大量的操作，使我们能够编写简洁的代码。然而，如果不了解这些操作的复杂度，有时会导致程序运行速度低于预期。
这份速查表旨在帮助开发者理解这些数据结构常见操作的平均时间复杂度和最坏情况复杂度，从而帮助大家在 Python 中编写出经过优化、高效的代码。
列表时间复杂度
Python 中的 列表 是一个有序的、可变的序列，通常被实现为动态数组。以下是常见列表操作的时间复杂度：
示例
摊销最坏情况
—
—
l.append(item)
O(1) (resize)
l.clear()
O(1)
item in/not in l
O(N)
l.copy()
O(N)
del l[i]
O(N)
l.extend(…)
O(N)
l1==l2, l1!=l2
O(N)
l[i]
O(1)
for item in l:
O(N)
len(l)
O(1)
kl
O(kN)
min(l), max(l)
O(N)
l.pop(-1)
O(1)
l.pop(item)
O(N)
l.remove(…)
O(N)
l.reverse()
O(N)
l[x:y]
O(y-x)
l.sort()
O(N log N)
l[i]=item
O(1)> 注意：* 元组具有相同的操作（不可变）和复杂度。
字典时间复杂度
Python 中的 字典 是作为哈希表实现的，这使得基于键的操作非常高效。以下是各项操作的复杂度：
示例
摊销最坏情况
—
—
d.clear()
O(1)
dict(…)
O(len(d))
del d[k]
O(N)
d.get()
O(N)
for item in d:
O(N)
len(d)
O(1)
d.pop(item)
O(N)
d.popitem()
O(1)
d.values()
O(1)
d.keys()
O(1)
d.fromkeys(seq)
O(len(seq))> 注意： Defaultdict 与 dict 拥有相同的操作和时间复杂度，因为它继承自 dict。
集合时间复杂度
Python 的 集合 是另一个基于哈希的集合，针对成员检查和集合运算进行了优化：
示例
摊销最坏情况
—
—
s.add(item)
O(N)
s.clear()
O(1)
s.copy()
O(N)
item in/not in s
O(N)
set(…)
O(len(s))
s.discard(item)
O(N)
s1-s2
O(len(s1))
s1.difference_update(s2)
–
s1==s2, s1!=s2
O(min(len(s1), len(s2)))
s1 & s2
O(min(len(s1), len(s2)))
for item in s:
O(N)
s1<=s2
O(len(s1))
s1>=s2
O(len(s1))
s.pop()
O(N)
s1\
O(len(s1)+len(s2))
s1^s2
O(len(s1)*len(s2))## 元组时间复杂度
元组 是不可变序列，这使得它们比列表更轻量，但操作也相对有限：
示例
最坏情况
—
—
(e.g., t[i])
O(1)
(e.g., x in t)
O(n)
(e.g., for x in t)
O(n)## 字符串时间复杂度
字符串 是不可变的，在时间复杂度方面与元组类似：
示例
最坏情况
—
—
(e.g., s[i])
O(1)
(e.g., s1 + s2)
O(n)
(e.g., x in s)
O(n)
(e.g., len(s))
O(1)
(e.g., s[start:end])
O(k)
(e.g., for c in s)
O(n)> ### 核心要点 –
>
> 列表 (Lists):
>
> – 摊销复杂度 适用于 append()，因为调整大小只是偶尔发生。
> – 在任意位置的插入和删除操作效率较低（O(N)），因为可能需要移动后续元素。