0%

如何降低 Python 程序的时间复杂度

时间复杂度使用大 O 标记法,这个大家应该都清楚,下面是常见的增长量级:

增长量级 名称
$O(1)$ 常量级
$O(log_bn)$ 对数级
$O(n)$ 线性级
$O(nlog_bn)$ $nlogn$
$O(n^2)$ 平方级
$O(n^3)$ 立方级
$O(c^n)$ 指数级

Python 中基本操作分析

常量时间

算术操作大部分都是常量时间,除法 > 乘法 > 加法和减法;

索引操作(下标访问)和 len 函数也是常量时间;

假如一个字符串只包含一个字符,所有的操作都是常量的;

在列表结尾添加和删除一个元素是常量的;

大部分字典操作都是常量的,但是 update 方法的运行时间和传入的字典大小成正比,keys、values 和 items 都是常量时间,因为它们返回的是迭代器,但是如果循环遍历这个迭代器,则循环是线性的。

线性时间

使用 for 循环遍历一个序列或字典是线性的;

字符串和元组的大部分操作都是线性的;

min 和 max 函数也是线性的;

切片操作的运行时间与输出的长度成正比,而与输入的长度无关;

内置函数 sum 也是线性的,但速度更快;

字符串拼接是线性的,运行时间与操作数的长度的总和有关,所有的字符串方法都是线性的。

其他时间

大多数列表方法是线性的,但是除非空间不足时复制到另一个更大的空间,排序是 $nlogn$;

如果循环体的增长量级是 $O(n^a)$ 则整个循环是 $O(n^{a+1})$,如果不论 $n$ 是多少,循环只最多运行 $k$ 次,则及时对很大的 $k$ 来说,整个循环的增长量级还是 $O(n^a)$。

搜索算法的分析

遍历操作是线性的,二分查找是对数级的,散列表是常量时间。