pythonlistremove复杂度_python3list时间复杂度
⼀、引题
本周在做⼒扣上的算法题(删除排序数组中的重复项)时，遇到了超出时间限制的问题，后来才知道是我设计的算法时间复杂度过⾼，于是我就对list的各个基本操作和常⽤函数的复杂度作了个了解。
⼆、背景知识
1.数组是⼀种线性表结构，其⽤⼀块连续的内存空间，来存储⼀组具有相同类型的数据
2.时间复杂度，也叫做渐进时间复杂度，通常⽤⼤O公式书写，表⽰代码的执⾏时间随数据规模增长的变化趋势，⽽⾮真正的执⾏时间。因此⼤O关注的是变化趋势。
三、列表(list)特点
1.底层基于数组实现
python list本质上是⼀个over-allocate的数组，啥叫over-allocate呢？就是当底层数组容量满了⽽需要扩充的时候，python依据规则会扩充多个位置出来。⽐如初始化列表array=[1, 2, 3, 4]，向其中添加元素23，
此时array对应的底层数组，扩充后的容量不是5，⽽是8。这就是over-allocate的意义，即扩充容量的时候会多分配⼀些存储空间。这样做的优点当然是提⾼了执⾏效率，否则每次添加元素，都要对底层数组进⾏扩充，效率是很低下的。另外，当列表存储的元素在变少时，python也会及时收缩底层的数组，避免造成内存浪费。这⾥可以通过对列表的实践，验证扩充与收缩的过程(通过 sizeof()或sizeof()查看内存变化，并推算容量值)。
2.属于引⽤数组
>>> a = [1, 2, 3, 4]
>>> a.__sizeof__()
72
>>> b = ['hello', 'world', 'mac']
>>> b.__sizeof__()
64
>>> c = [int('10'), str(8)]
>>> c.__sizeof__()
56
>>> d = 23
>>>
>>> l = []
>>> l.__sizeof__()
40
>>> l.append(a)
>>> l
[[1, 2, 3, 4]]
>>> l.__sizeof__()
72
>>> l.append(b)
>>> l.__sizeof__() 72
>>> l.append(c) >>> l.__sizeof__() 72
>>> l.append(d) >>> l.__sizeof__() 721
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
我们知道，初始列表的底层数组容量是0，第⼀次会扩充为4个元素的容量，占⽤32个字节，每个元素占⽤8个，注意这⾥就是每个元素占⽤8个字节，⽽不是平均的结果为8个字节。如果列表中存放实际的元素，那上⾯实践中列表l添加完元素列表a之后，其占⽤的字节就不会是72了。因此列表本质上存储的是对象的引⽤。
四、列表各操作时间复杂度分析
常见的时间复杂度⾼低排序：
O(1)
具体的看下表，'n’是容器中当前的元素数， 'k’是需要操作的元素个数。python 定义数组
操作
时间复杂度
index()
O(1)
append()
O(1)
extend()
O(k)
insert()
O(n)
count()
O(n)
remove()
O(n)
pop()
O(1)
pop(i)
O(n)
sort()
O(n log n)
reverse()
O(n)
len()
O(1)
max(),min()
O(n)
del(del list[i] 或者 del list[i:j])
O(n)
slice [x:y] (切⽚)
O(k)
iterration(列表迭代)
O(n)
in 关键字
O(n)
通过分析可以发现，列表不太适合做元素的遍历、删除、插⼊等操作，对应的时间复杂度为O(n)；访问某个索引的元素、尾部添加元素或删除元素这些操作⽐较适合做，对应的时间复杂度为O(1)。
其他集合内置⽅法的时间复杂度
最后简单了解⼀下空间复杂度：
空间复杂度是⽤来评估算法内存占⽤⼤⼩的⽅式。定义⼀个或多个变量，空间复杂度都是为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*21
2
3
4
5
6
7

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。