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

Question

我正在尝试监控 Python 列表中的复杂性。因此，我编写了上面的脚本，认为在末尾插入一个项目的复杂度为 O(1)，在开头插入的复杂度为 O(n)，如下所示

import time

for 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 ms

Time for insertion at the beginning : 0.001 ms

n = 10000 :

Time for insertion at the end : 0.003 ms

Time for insertion at the beginning : 0.007 ms

n = 100000 :

Time for insertion at the end : 0.036 ms

Time for insertion at the beginning : 0.098 ms

n = 1000000 :

Time for insertion at the end : 0.05 ms

Time for insertion at the beginning : 1.001 ms

n = 10000000 :

Time for insertion at the end : 0.257 ms

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