c++ - 这些时间复杂度是否正确

Question

我想知道我关于以下几点的时间复杂度以及推理是否正确。

1. 在动态数组的末尾插入是 O(1)，而在其他任何地方O(n)(因为元素可能需要复制和移动)(类似于 std::vector)
2. 搜索单个链接列表的时间复杂度为 O(n)，因为它是线性的。
3. 单个链接列表中的插入和删除可以是 O(1) 或在)。如果节点的地址可用则为 O(1) 否则它的 O(n)，因为需要线性搜索。

我会很感激对此的反馈

Answer 1

Insertion at the end of a dynamic array is O(1) and anywhere else in O(n) (since elements might >need to copied and moved) (resembling a std::vector)

动态数组的分摊时间复杂度为 O(1)。 https://stackoverflow.com/a/249695/1866301

Searching through a single link list is O(n) since its linear.

是

Insertion and deletion in a single link list could either be O(1) or O(n). It is O(1) if the address to the node is available otherwise its O(n) since a linear search would be required.

是的，如果链表的节点由它们的地址索引，您可以获得 O(1)，否则您将不得不搜索整个列表，即 O(n)。还有其他变体，例如跳跃列表，其搜索是对数的，O(log n)。 http://en.wikipedia.org/wiki/Skip_list