時間和列表的空間複雜度爲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 

---

結論

假設是不正確。轉換是時間線性的。