您现在的位置是：首页 > 后端

当前栏目

Python常见操作的时间复杂度

Python 操作时间常见复杂度

2023-09-11 14:19:30 时间

Python常见操作的时间复杂度

本文整理了Python中常见数据结构操作的时间复杂度，旨在帮助大家了解Python操作的性能，协助大家写出更快的代码。

文章目录

标注方法

程序时间复杂度一般用"大O表示法（Big-O notation）"来表示。假如有如下代码：

def list_check(to_check, the_list):
	for item in the_list:
		if to_check == item:
			return True
	return False

上面代码功能很简单，就是检查to_check是否在列表the_list中。我们称这个函数的时间复杂度为 $O (n)$ ，其中 $n$ 指列表the_list中的元素个数， $O (n)$ 的意思是算法所需时间的上限随列表中的元素个数线性增长。

在我们描述时间复杂度时，通常会涉及2个数量：

$O (n)$ 中的 $n$ 通常表示容器中元素个数
$O (k)$ 中的 $k$ 通常表示参数或传入容器中元素个数

常见复杂度表

Big-O	复杂度	解释
$O (1)$	常量复杂度	无论输入的大小，运行时间始终保持一个常数。例如从哈希表中取值的时间复杂度就是 $O (1)$ 。
$O (n)$	线性复杂度	运行时间随输入大小线性增长。遍历列表就是一个时间复杂度为 $O (n)$ 的操作。
$O(n^{2})$	平方复杂度	运行时间与输入大小呈平方关系。比如冒泡排序、插入排序的时间复杂度为 $O(n^2)$ 。
$O(2^{n})$	指数复杂度	运行时间与输入大小呈指数关系。指数复杂度的算法性能非常低。例如图论中的三色问题就是指数复杂度。
$O(\log_{n})$	对数复杂度	当输入呈指数增长是，运行时间按线性增长。二分法查找就是典型的对数复杂度。

常见复杂度的图像展示

在这里插入图片描述

List操作

List是Python中使用最多的数据结构，熟悉List中各操作的时间复杂度对我们优化程序性能有很大帮助

操作	时间复杂度（平均情况）
追加 `append()`	$O (1)$
拷贝 `copy()`	$O (n)$
删除元素 `remove()`	$O (n)$
删除切片 `del lst[2:4]`	$O (n)$
插入 `insert()`	$O (n)$
获取元素 `lst[0]`	$O (1)$
设置元素 `lst[0] = 1`	$O (1)$
迭代	$O (n)$
获取切片 `lst[0:3]`	$O (k)$
设置切片 `lst[0:3] = [4, 5]`	$O (n + k)$
扩展 `extend()`	$O (k)$
排序 `lst.sort()`	$O(n \log_n)$
获取长度 `len()`	$O (1)$
`in`	$O (n)$
min()``max()	$O (n)$

Set操作

操作	时间复杂度（平均情况）	时间复杂度(最差情况)
`in`	$O (1)$
差集 `s-t`	$O(\text{len}(s))$
交集 `s&t`	$O(\text{min}(\text{len}(s), \text{len}(t)))$	$O(\text{len}(s) \times \text{len}(t))$
并集 `s\\|t`	$O(\text{len}(s) + \text{len}(t))$
对称差集 `s^t`	$O(\text{len}(s))$	$O(\text{len}(s) \times \text{len}(t))$
多重交集 `s1&s2&s3&...&sn`		$(n - 1) * O (l)$ 其中 $\text{max}( \text{len}(s_1),\dots,\text{len}(s_n))$
`s.difference_update(t)`	$O(\text{len}(t) \times \text{len}(s))$
`s.symetric_difference_update(t)`	$O(\text{len}(t))$

Deque操作

deque是python标准库提供的双向队列

操作	时间复杂度（平均情况）
队尾追加 `append()`	$O (1)$
队首追加 `appendleft()`	$O (1)$
队尾扩展 `extend()`	$O (k)$
队首扩展 `extendleft()`	$O (k)$
队尾移除 `pop()`	$O (1)$
队首移除 `popleft()`	$O (1)$
拷贝 `copy()`	$O (n)$
删除 `remove()`	$O (n)$
轮转 `rotate(k)`	$O (k)$

猜你喜欢

确保VDI顺利部署试点项目是关键
系统论是大尺度的还原论的时空思考-系统论是宏观上的还原论
Java笔记12：Java对象排序
【C语言】不使用strcat(字符串连接函数)将两个字符串连接起来。
朋友圈看不起？！热文随便看不花钱！
[LeetCode] Duplicate Emails 重复的邮箱
微信小程序实现视频功能（二）：视频列表与下载
开涛spring3(6.9) - AOP 之 6.9 代理机制
[LeetCode] 834. Sum of Distances in Tree 树中距离之和
【BZOJ1914】数三角形（组合数，极角排序）
Python 爬虫之根据图片网址爬取图片

相关主题

python人脸检测
Python入门实例
python ----split()
Python-Python入门
python 乱码
Python练习4
Python 操作 redis
Python: super
python 杨辉三角
[ python ] 继承
Python中cPickle
jupyter python
h5 Python_python做h5网站
python数据分析与可视化
Python keras
[Python]装饰器
python_6_if
python--集合
Python——函数
python做http请求

zl程序教程

当前栏目

Python常见操作的时间复杂度

Python常见操作的时间复杂度

文章目录

标注方法

List操作

Set操作

Deque操作

相关文章