时间和列表的空间复杂度为str转换在Python

Question

试图找出什么是铸造字符串的时间复杂度

str([1,2,6,...,3,6]) 

肯定它的O（1） 不知道如何验证。

编辑： 关于空间复杂性，这应该不是线性列表大小， 想O（​​1）因为字符串有最大尺寸。

Answer 1

假说

str列表的转换是在复杂性是恒定的。

---

实验

创建不同大小的列表：

In [67]: list10 = np.random.choice(100, 10).tolist() 

In [68]: list100 = np.random.choice(100, 100).tolist() 

In [69]: list10000 = np.random.choice(100, 10000).tolist() 

In [70]: list1000000 = np.random.choice(100, 1000000).tolist() 

---

观察

使用timeit和时间conversi每个列表上的过程：

In [71]: %timeit str(list10) 
1000000 loops, best of 3: 1.69 µs per loop 

In [72]: %timeit str(list100) 
100000 loops, best of 3: 10.6 µs per loop 

In [73]: %timeit str(list10000) 
1000 loops, best of 3: 958 µs per loop 

In [74]: %timeit str(list1000000) 
10 loops, best of 3: 96.8 ms per loop 

---

结论

假设是不正确。转换是时间线性的。