我正在嘗試監控 Python 列表中的復雜性。因此，我編寫了上面的腳本，認為在末尾插入一個項目的復雜度為 O(1)，在開頭插入的復雜度為 O(n)，如下所示import timefor p in [3,4,5,6,7]: n = 10**p print("n =", n, ":") # Creation of a list [0, 1, ..., n] li = list(range(n)) start = time.perf_counter() # Adding item at the end li.append('a') stop = time.perf_counter() duration = round((stop - start)*1000, 3) print("Time for insertion at the end :", duration, "ms") start = time.perf_counter() # Adding item at the beginning li.insert(0,'a') stop = time.perf_counter() duration = round((stop - start)*1000, 3) print("Time for insertion at the beginning :", duration, "ms") print()結果是：n = 1000 :Time for insertion at the end : 0.001 msTime for insertion at the beginning : 0.001 msn = 10000 :Time for insertion at the end : 0.003 msTime for insertion at the beginning : 0.007 msn = 100000 :Time for insertion at the end : 0.036 msTime for insertion at the beginning : 0.098 msn = 1000000 :Time for insertion at the end : 0.05 msTime for insertion at the beginning : 1.001 msn = 10000000 :Time for insertion at the end : 0.257 msTime for insertion at the beginning : 11.453 ms因此，開頭的插入顯然是 O(n)，但末尾的插入顯然不是 O(1)。有人可以向我解釋一下嗎？配置：Ubuntu 20.04.1 LTS 上的 Python 3.8.5因此，我嘗試使用 timeit （按照建議），結果是應有的結果。
1 回答
尚方寶劍之說
TA貢獻1788條經驗 獲得超4個贊
Python 中列表的大小是動態的。但由于動態列表的工作方式，并非所有追加都具有相同的成本。
最初為列表分配固定空間。當分配的空間已滿并且我們想要追加一個元素時，會為列表分配一個兩倍于先前空間的新空間，并將所有列表項復制到新位置。因此，如果分配的空間未滿，則追加需要 O(1)，但如果分配的空間已滿，則需要 O(n)（因為我們需要先復制）。
追加 n 個項目的成本（假設最初分配了兩個單位的空間）：
(1) + (1) # costs of appending the first two items
+ (2+1) + (1) # costs of appending the next two items
+ (4+1) + (1) + (1) + (1) # costs of appending the next four items
+ (8+1) + (1) + (1) + (1) + (1) + (1) + (1) + (1) # costs of appending the next eight items
+ (16+1) + (1) + (1) + (1) + (1) + (1) + (1) + (1) + (1) + (1) + (1) + (1) + (1) + (1) + (1) + (1)
+ (32+1) + ...
...
這2 + 4 + 8 + 16 + ... + n大約等于 2n。所以nappend次操作總共花費了2n。所以平均每項費用O(1)。這稱為攤余成本。
添加回答
舉報
0/150
提交
取消