python里list的remove和pop方法的时间复杂度是多少?

  算法/数据结构 Python 计算复杂度    浏览次数: 152
0

python里list的remove和pop方法的时间复杂度是多少?

remove是用来删除指定数值的元素

my_list.remove(val)

pop是用来删除指定位置的元素,比如下面就是删除第一个

my_list.pop(0)

它们都是$O(n)$的吗?还是$O(1)$的?

 

Erin   2019-01-30 14:54



   1个回答 
3

就我知道的 :

.remove(value)  --> O(n)

.pop(index) --> O(n-index)

说明下, O(pop())可能一开始由于index查找的原因会误以为是O(1),但其实在完成删除这个步骤之后,所有在这个被删除位置之后的元素的index都会被向前移一位, 或者说向前补充。 并且pop()最后会返回被删除的元素值。  

remove()就很直接了, 从第0个元素找起, 直到找到第一个match的元素并删除(不会像pop一样返回被删掉元素的值), 然后剩余元素向前补充。 

SofaSofa数据科学社区 DS面经 问答 实战

R   2019-01-31 17:55



  相关主题

返回python list里各个元素的大小排序?   1回答

python怎么对list中的元素做连乘?   1回答

python里怎么把中文字符串转化为成list   1回答

如何把一个pandas的dataframe的columns转换成list   2回答

怎么把pandas dataframe中的一列转成一个list?   3回答

二维numpy.array转为一维的numpy.array或者list   2回答

NP-hard是什么意思   1回答

在python中获取模型运行的时间   3回答

kNN进行预测时计算复杂度是多少?   1回答

朴素贝叶斯的训练/预测效率如何?快吗?   1回答

用python生成一个取值在a到b之间的随机矩阵   1回答

python怎么读取txt格式的数据文件?   1回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!