成本在使用python字符串列表蟒蛇

Question

更换列表的元素，为恩：

list_str = ['aa', 'bb', 'abc']. 

什么是替换列表的元素的成本/复杂性，如下所示：

list_str[i] = 'xyz' 

（假设该列表的长度为ñ，和一个字符串的长度至多为米）

Answer 1

使用简单的测试，这似乎是恒定的时间 -

In [1]: list_str = ['aaa' for _ in range(100000)] 

In [2]: %timeit list_str[0] = 'aab' 
10000000 loops, best of 3: 77.7 ns per loop 

In [3]: %timeit list_str[9999] = 'aab' 
10000000 loops, best of 3: 77.2 ns per loop 

In [4]: %timeit list_str[99999] = 'aab' 
10000000 loops, best of 3: 78.7 ns per loop 

In [5]: %timeit list_str[9] = 'aab' 
10000000 loops, best of 3: 77.7 ns per loop 

Answer 2

替换元素的代价与列表的长度无关，而与字符串的长度无关。在Python列表中只包含对象的引用。所以基本上，替换元素是覆盖大小指针的内存部分。

Answer 3

由于CPython将列表作为数组实现，因此像l[i] = x这样的操作将采用常量（O（1））时间。

见行动，这里的表：https://wiki.python.org/moin/TimeComplexity

Answer 4

O（1）的时间复杂度由指数列表中的

来替换元素

Answer 5

Python中的列表被实现为动态分配指向所包含值的指针数组。

用另一个替换元素只是指针调整和引用计数调整，并需要一个恒定的时间（独立于列表的大小）。