相关疑难解决方法(0)

我试图列出常见数据结构的操作的时间复杂性,如数组,二进制搜索树,堆,链表等,尤其是我指的是Java.它们很常见,但我想我们中的一些人对确切的答案并不是100%有信心.任何帮助,特别是参考,非常感谢.

例如,对于单链表:更改内部元素是O(1).你怎么能这样做？你HAVE更改它之前要搜索的元素.另外,对于Vector,添加内部元素为O(n).但是为什么我们不能在使用索引的摊销常数时间内做到这一点？如果我错过了什么,请纠正我.

我发布我的发现/猜测作为第一个答案.

我正在研究数据结构：单链表。

该网站称单向链表的插入和删除时间复杂度为O(1). 我错过了什么吗？

网站链接

我用 C++ 做这个，我只有一个root pointer. 如果我想在最后插入，那么我必须一直走到后面，这意味着O(n).