• 常见的时间复杂度高低排序

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n²logn)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)

列表(list)

  • python的列表内部实现是数组(具体实现要看解析器)
  • 拥有数组的特点,超过容量会增加更多的容量,set, get 是O(1),但del,insert,,in的性能是O(n)
  • 'n'是容器中当前的元素数'k'是需要操作的元素个数
操作平均情况最坏情况
复制O(n)O(n)
append[注1]O(1)O(1)
插入O(n)O(n)
取元素popO(1)O(1)
取元素pop[1]O(n)O(n)
更改元素O(1)O(1)
删除元素O(n)O(n)
遍历O(n)O(n)
取切片O(k)O(k)
删除切片O(n)O(n)
更改切片O(k+n)O(k+n)
extend[注1]O(k)O(k)
排序O(n log n)O(n log n)
列表乘法O(nk)O(nk)
x in sO(n)
min(s), max(s)O(n)
计算长度O(1)O(1)

双向队列(collections.deque):

  • double-ended queue,双向队列,是以双向链表的形式实现的
  • 双向队列的两端都是可达的但查找队列中间的元素较为缓慢,增删元素就更慢了
操作平均情况最坏情况
复制O(n)O(n)
appendO(1)O(1)
appendleftO(1)O(1)
popO(1)O(1)
popleftO(1)O(1)
extendO(k)O(k)
extendleftO(k)O(k)
rotateO(k)O(k)
removeO(n)O(n)

字典(dict):

  • 关于字典需要了解的是hash函数和哈希桶
  • 一个好的hash函数使用到的哈希桶中的值只有一个,若多个key hash到了同一个哈希桶中,称之为哈希冲突
  • 查找值时,会先定位到哈希桶中,再遍历hash桶,在hash基本没有冲突的情况下get,set,delete, in方面都是O(1)。
操作平均情况最坏情况
复制[注2]O(n)O(n)
取元素O(1)O(n)
更改元素[注1]O(1)O(n)
删除元素O(1)O(n)
遍历[注2]O(n)O(n)

集合(set):

  • 内部实现是dict的,在in操作上是O(1),这一点比list要强
操作平均情况最坏情况
x in sO(1)O(n)
并集 s\tO(len(s)+len(t))
交集 s&tO(min(len(s), len(t))O(len(s) * len(t))
差集 s-tO(len(s))
s.difference_update(t)O(len(t))
对称差集 s^tO(len(s))O(len(s) * len(t))
s.symmetric_difference_update(t)O(len(t))O(len(t) * len(s))

空间复杂度

  • 是用来评估算法内存占用大小的方式,定义一个或多个变量,空间复杂度都是为1,列表的空间复杂度为列表的长度
a = 'Python'                                                                      #空间复杂度为1
b = 'PHP'
c = 'Java'
num = [1, 2, 3, 4, 5]                                                              #空间复杂度为5
num = [[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]]      #空间复杂度为5*4
num = [[[1, 2], [1, 2]], [[1, 2], [1, 2]] , [[1, 2], [1, 2]]]                      #空间复杂度为3*2*2
Last modification:May 7th, 2020 at 07:19 pm
安安,亲觉得有用, 请随意打赏嗷