常见的大 $O$ 函数

$f(n)$	名称
$1$	常数
$\log{n}$	对数
$n$	线性
$n\log{n}$	对数线性
$n^{2}$	平方
$n^{3}$	立方
$2^{n}$	指数

Python 列表操作的大 $O$ 效率

操作	大 $O$ 效率
索引	$O(1)$
索引赋值	$O(1)$
追加	$O(1)$
pop()	$O(1)$
pop(i)	$O(n)$
insert(i, item)	$O(n)$
删除	$O(n)$
遍历	$O(n)$
包含	$O(n)$
切片	$O(k)$
删除切片	$O(n)$
设置切片	$O(n+k)$
反转	$O(n)$
连接	$O(k)$
排序	$O(n \log n)$
乘法	$O(nk)$

Python 字典操作的大 $O$ 效率

操作	大 $O$ 效率
复制	$O(n)$
取值	$O(1)$
赋值	$O(1)$
删除	$O(1)$
包含	$O(1)$
遍历	$O(n)$

注意：表中给出的效率针对的是普通情况。在某些特殊情况下，包含、取值、赋值等操作的时间复杂度可能变成 $O(n)$。

• 算法分析是一种独立于实现的算法度量方法。

• 大 $O$ 记法使得算法可以根据随问题规模增长而起主导作用的部分进行归类。