c++ - 这些时间复杂性正确吗？

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

在动态数组的末尾插入O(1)并在
O(n)(因为可能需要复制和移动元素)(类似于std::vector)

由于它是线性的，因此搜索单个链接列表为O(n)。

在单个链接列表中的插入和删除可以是O(1)或
上)。如果该节点的地址可用，则为O(1)
它的O(n)，因为需要进行线性搜索。

我希望能对此提供反馈

最佳答案

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



是



是的，如果链接列表的节点按其地址索引，则可以得到O(1)，否则将必须搜索列表O(n)。还有其他变体，例如跳过列表，其搜索是对数的，O(log n)。
http://en.wikipedia.org/wiki/Skip_list