在 Python 中追加而不是 O(1)

Question

我正在尝试监控 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 （按照建议），结果是应有的结果。

Answer 1

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)。这称为摊余成本。