将一个元素插入到一个已知大小的数组中是常数时间吗？

Question

我有一个 input array of integers 正在迭代。

对于每次迭代，我都在进行一些计算，并且有可能将我正在迭代的数字添加到另一个我将维护的大小为 3 的数组中。

例如：

input array = [1,5,10,4,2,10,4]
res = [2,4,5]

for i in range(len(array)): 
    .... 
    res.append(array[i])
    res = res[:3]

如您所见，在每次插入 res 的最后，我对数组进行切片，以仅保留其中的三个元素。

我理解插入的时间复杂度是恒定时间吗？因为每次插入我最多移动右边的三个元素（即使我知道 python 数组是动态的，这是在后台完成的）。

并且只是为了确认 算法的时间复杂度因此是 O(n)？如果我的上述假设是正确的？

Answer 1

您可以使用为此优化的 collections.deque，并为您保持大小不变：

Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

如果指定maxlen，

the deque is bounded to the specified maximum length. Once a bounded length deque is full, when new items are added, a corresponding number of items are discarded from the opposite end.

所以，您的代码就变成了

from collections import deque

input array = [1,5,10,4,2,10,4]
res = deque([2,4,5], maxlen=3)

for i in range(len(array)): 
    .... 
    res.append(array[i])

并且 res 的大小保持不变。

将一个元素插入到一个已知大小的数组中是常数时间吗？

Is inserting an element into an array of known size constant time?

python

arrays

insert