在《数据结构和算法》一书的第290页中提到，arraylist的remove(i(复杂度为O(1(。我的第一个问题是为什么不是O(n(？还提到链表的add(i，e(是O(n(，所以我的第二个问题是为什么不是O(min(i，n-i((？
最后，我的第三个问题是复杂性被称为O(min(i，n-i((的原因是由于它是一个双向链表，这意味着我们可以从开头(i(或结束(n-i(遍历？
第一个是值得商榷的。删除 ArrayList 中的最后一个元素时，它是常量，但对于中间元素，您需要将所有后续元素向左移动。Java使用System.arrayCopy((来做到这一点，这是一个非常快速的复制数组的本机例程，但即使是这种方法也显然是O(n(，而不是常量，所以我倾向于同意你的看法。对于插入，这是不同的，其中调整数组大小到所需索引的摊销成本平均为常量因子，因此 add(( 为 O(1(。
第二个可以这样实现，但事实并非如此。仅从头开始删除。我猜选择是为了减少不同步访问的事故。
最后，在 Big-O 复杂度的符号中，不太重要的因子被丢弃，因此 O(min(i，n-i(( 实际上等价于 O(n(，尽管现实世界告诉我们前者肯定是一种优化。