Python常用操作的复杂度

  我们前面讲过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_Times

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

评论

暂无评论