首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >向列表追加列表的时间复杂度

问向列表追加列表的时间复杂度
EN

Stack Overflow用户
提问于 2021-01-31 12:01:09
回答 4查看 219关注 0票数 1

我知道将元素追加到列表的分期复杂性是O(1),但是将列表追加到列表的时间复杂度是多少?

需要澄清的是:

将元素追加到列表

代码语言:javascript
复制
list_ = []  
for _ in range(0,n):  
    list_.append(1)

将列表追加到列表

代码语言:javascript
复制
list_ = []
list_.append([_ for _ in range(0,n)])
EN

回答 4

Stack Overflow用户

回答已采纳

发布于 2021-01-31 12:10:34

再次引用我的评论,将一个列表“附加”到一个列表仍然是O(1),您只是添加了对列表的引用,“扩展”一个大小为m的列表将耗费O(m),因为它必须遍历另一个大小为m的列表来附加每个元素。

代码语言:javascript
复制
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)。

票数 2
EN

Stack Overflow用户

发布于 2021-01-31 12:08:41

由于.extend的实现实际上只比就地添加慢一点点,您可以查看.extend实现的源代码以获得答案,如下所示:https://github.com/python/cpython/blob/master/Objects/listobject.c

正如您所看到的,有一些恒定的时间开销,设置具有足够内存的结果列表等等。然后,用于扩展列表的迭代器将线性耗尽,这意味着时间复杂度为O(n)。

票数 1
EN

Stack Overflow用户

发布于 2021-01-31 12:07:40

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/65975611

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档