我知道将元素追加到列表的分期复杂性是O(1),但是将列表追加到列表的时间复杂度是多少?
需要澄清的是:
将元素追加到列表
list_ = []
for _ in range(0,n):
list_.append(1)将列表追加到列表
list_ = []
list_.append([_ for _ in range(0,n)])发布于 2021-01-31 12:10:34
再次引用我的评论,将一个列表“附加”到一个列表仍然是O(1),您只是添加了对列表的引用,“扩展”一个大小为m的列表将耗费O(m),因为它必须遍历另一个大小为m的列表来附加每个元素。
seq = [1, 2, 3]
new_seq = [4, 5, 6]
# Appending is O(1)
seq.append(new_seq)
print(seq) # [1, 2, 3, [4, 5, 6]]
seq = [1, 2, 3]
new_seq = [4, 5, 6]
# Extending is O(m), m = len(new_seq)
seq.extend(new_seq)
print(seq) #[1, 2, 3, 4, 5, 6]
list_ = []
list_.append([_ for _ in range(0,n)])创建列表[_ for _ in range(0,n)]的时间为O(n),将该列表的引用添加到list_的时间为O(1)。对于行list_.append([_ for _ in range(0,n)]),总共是O(n)。
发布于 2021-01-31 12:08:41
由于.extend的实现实际上只比就地添加慢一点点,您可以查看.extend实现的源代码以获得答案,如下所示:https://github.com/python/cpython/blob/master/Objects/listobject.c
正如您所看到的,有一些恒定的时间开销,设置具有足够内存的结果列表等等。然后,用于扩展列表的迭代器将线性耗尽,这意味着时间复杂度为O(n)。
发布于 2021-01-31 12:07:40
https://stackoverflow.com/questions/65975611
复制相似问题