Python常用操作的复杂度

Stella981
• 阅读 441

  我们前面讲过list、deque、堆、字典树等高性能计算的技巧,这一节我们来整理一下Python中常用操作的时间复杂度。本文中的N表示容器的元素数量,K表示参数中元素的数量或参数的值。

  • list

    lst = list(range(10,20))l1 = list(range(100,105))

操作

时间复杂度

描述

lst[2]

O(1)

访问元素

lst.pop()

O(1)

弹出最后一个值

lst.append(l1)

O(1)

在末尾添加元素

lst.extend(l1)

O(K)

在末尾逐个添加元素

lst.clear()

O(1)

清空list

lst.copy()

O(N)

列表拷贝

lst.count(15)

O(N)

元素计数

lst.remove(15)

O(N)

删除一个元素

lst.reverse()

O(N)

反序

lst.sort()

O(N*log(N))

排序

lst.insert(1,200)

O(N)

在某一位置插入元素

del lst[0]

O(N)

删除某个位置的元素

lst.index(15)

O(N)

查找元素,并返回元素位置

bisect.bisect_left(lst, 15)

O(log(N))

有序列表使用bisect查找元素

  • tuple

tuple因为不可写,因此操作相对较少

tpl = tuple(range(10))

操作

时间复杂度

描述

tpl[2]

O(1)

访问元素

tpl.count(2)

O(N)

元素计数

tpl.index(2)

O(N)

查找元素,并返回元素位置

  • set

    ss1 = set(range(10))ss2 = set(range(5,15))

操作

时间复杂度

描述

5 in ss1

O(N)

判断元素是否在set中

ss1 | ss2

O(len(ss1)+len(ss2))

取并集,等同于ss1.union(ss2)

ss1 & ss2

O(len(s)*len(t))

取交集,等同于ss1.intersection(ss2)

ss1 - ss2

O(len(ss1))

取差集,等同于ss1.difference(ss2)

ss1 ^ ss2

O(len(ss1)*len(ss2))

取异或集,等同于

ss1.add(11)

O(1)

增加元素

ss1.pop()

O(1)

弹出一个元素

ss1.remove(5)

O(1)

删除指定元素

  • dict

    dd = {'a':10,'b':20,'c':30,'d':40}

操作

时间复杂度

描述

dd['e'] = 50

O(1)

插入元素

dd['a']

O(1)

访问元素,等同于dd.get('a')

del dd['a']

O(1)

删除元素

dd['b'] = 100

O(1)

修改元素

dd.pop('b')

O(1)

弹出一个元素

dd.clear()

O(1)

清空字典

  • deque

双端队列需要我们手动导入后才能使用,也是Python中一种常用的类型

from collections import dequedeq = deque(range(10))ll = list(range(10))

操作

时间复杂度

描述

deq.pop()

O(1)

弹出最右侧的元素

deq.popleft()

O(1)

弹出最左侧的元素

deq.append(1)

O(1)

在右侧增加一个元素

deq.appendleft(1)

O(1)

在左侧增加一个元素

deq.extend(ll)

O(K)

在右侧逐个添加元素

deq.extendleft(ll)

O(K)

在左侧逐个添加元素

deq.rotate(K)

O(K)

旋转

deq.remove(5)

O(N)

删除指定元素

deq[0]

O(1)

访问第一个元素

deq[N-1]

O(1)

访问最后一个元素

deq[N/2]

O(N)

访问中间元素

Python高性能系列文章

  1. Python高性能计算之列表

  2. Python高性能计算之字典

  3. Python高性能计算之堆

欢迎关注微信公众号:Quant_TimesPython常用操作的复杂度

本文分享自微信公众号 - 科学计算Tech(Quant_Times)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录 问题 用navicat导入数据时,报错: 原因这是因为当前的MySQL不支持datetime为0的情况。 解决修改sql\mode: sql\mode:SQL Mode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。 全局s
Karen110 Karen110
1年前
​一篇文章总结一下Python库中关于时间的常见操作
前言本次来总结一下关于Python时间的相关操作,有一个有趣的问题。如果你的业务用不到时间相关的操作,你的业务基本上会一直用不到。但是如果你的业务一旦用到了时间操作,你就会发现,淦,到处都是时间操作。。。所以思来想去,还是总结一下吧,本次会采用类型注解方式。 time包import time 时间戳 从1970年1月1日00:00:00标准时区诞生到现在
Stella981 Stella981
11个月前
List的Select 和Select().tolist()
List<Person> delp = new List<Person> { new Person{ Id=1,Name="小明1",Age=11,Sign=0 }, new Person{ Id=2,Name="小明2",Age=12 ,
Stella981 Stella981
11个月前
Python之time模块的时间戳、时间字符串格式化与转换
Python处理时间和时间戳的内置模块就有`time`,和`datetime`两个,本文先说`time`模块。 ### 关于时间戳的几个概念 * 时间戳,根据1970年1月1日00:00:00开始按秒计算的偏移量。 * 时间元组(`struct_time`),包含9个元素。  `time.struct_time(tm_y
Easter79 Easter79
11个月前
Twitter的分布式自增ID算法snowflake (Java版)
概述 == 分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。 有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。 而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
11个月前
java常用类(2)
三、时间处理相关类 Date类:计算机世界把1970年1月1号定为基准时间,每个度量单位是毫秒(1秒的千分之一),用long类型的变量表示时间。 Date分配Date对象并初始化对象,以表示自从标准基准时间(称为“历元”(epoch),即1970年1月1日08:00:00GMT)以来的指定毫秒数。 示例: package cn.tanjian
Stella981 Stella981
11个月前
Django中Admin中的一些参数配置
### **设置在列表中显示的字段,id为django模型默认的主键** list_display = ('id', 'name', 'sex', 'profession', 'email', 'qq', 'phone', 'status', 'create_time') ### **设置在列表可编辑字段** list_editable
Wesley13 Wesley13
11个月前
PHP中的NOW()函数
是否有一个PHP函数以与MySQL函数`NOW()`相同的格式返回日期和时间? 我知道如何使用`date()`做到这一点,但是我问是否有一个仅用于此的函数。 例如,返回: 2009-12-01 00:00:00 * * * ### #1楼 使用此功能: function getDatetimeNow() {
Wesley13 Wesley13
11个月前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
#### 背景描述 # Time: 2019-01-24T00:08:14.705724+08:00 # User@Host: **[**] @ [**] Id: ** # Schema: sentrymeta Last_errno: 0 Killed: 0 # Query_time: 0.315758 Lock_
helloworld_34035044 helloworld_34035044
2个月前
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。 uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid() 或 uuid(sep)参数说明:sep 布尔值,生成的uuid中是否包含分隔符'',缺省为