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

  算法/数据结构/数据库 Python 计算复杂度    浏览次数:1644        分享
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个回答 
4

就我知道的 :

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

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

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

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

SofaSofa数据科学社区DS面试题库 DS面经

R   2019-01-31 17:55



  相关主题

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

python字符串形式的数值转成单个整数的list,怎么操作?   2回答

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

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

re 不能在list 或者dataframe查找?   1回答

怎么把字符串形式的list转成真的list   2回答

python如何把list中的item作为变量的后缀 从而产生for中的动态变量名   2回答

有nonetype的list怎么转str   1回答

python中怎么对list中元素进行有放回抽样?   1回答

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

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

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



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

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

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

我们谢绝答非所问。

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

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