成本在使用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中的列表被實現爲動態分配指向所包含值的指針數組。

用另一個替換元素只是指針調整和引用計數調整，並需要一個恆定的時間（獨立於列表的大小）。