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

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



  相关讨论

有nonetype的list怎么转str

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

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

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

re 不能在list 或者dataframe查找?

python报错:'list' object has no attribute 'Angle',求教

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

beam search是什么意思?

NP-hard是什么意思

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

  随便看看

行数很多的pandas DataFrame如何在jupyter中完整显示?

单一变量下的异常检测该怎么做?

怎么让DataFrame按照某一列绝对值从小到按排列?

支持向量机(SVM)里的支持向量是什么意思

sklearn模型当中的verbose是什么意思?