python数组时间复杂度？

Question

array.array 和 np.array 的.append 时间复杂度是多少？

我在 python_wiki 中看到 list、collections.deque、set 和 dict 的时间复杂度，但我找不到array.array 和np.array 的时间复杂度。我在哪里可以找到它们？

Answer 1

因此，为了链接您提供的(也是TLDR) list 在内部“表示为数组” _link 它应该是 O(1)，底部有一个注释:

"These operations rely on the "Amortized" part of "Amortized Worst Case". Individual actions may take surprisingly long, depending on the history of the container." _link

---

更多详情

它没有在文档中详细介绍，但如果您查看 source code你会真正看到发生了什么。 Python array 具有内部缓冲区，可以快速调整自身大小，并会在其增长/收缩时重新分配。

array.append 使用 arraymodule.array_array_append这叫arraymodule.ins打电话arraymodule.ins1这是操作的重点。顺便说一句，array.extend 也使用了它，但它只是将它提供给 Py_SIZE(self) 作为插入索引。

因此，如果我们阅读 arraymodule.ins1 中的注释，它开始于:

Bypass realloc() when a previous overallocation is large enough
to accommodate the newsize.  If the newsize is 16 smaller than the
current size, then proceed with the realloc() to shrink the array.

^link

...

This over-allocates proportional to the array size, making room
for additional growth.  The over-allocation is mild, but is
enough to give linear-time amortized behavior over a long
sequence of appends() in the presence of a poorly-performing
system realloc().
The growth pattern is:  0, 4, 8, 16, 25, 34, 46, 56, 67, 79, ...
Note, the pattern starts out the same as for lists but then
grows at a smaller rate so that larger arrays only overallocate
by about 1/16th -- this is done because arrays are presumed to be more
memory critical.

^link