为什么在动态数组 O（n） 末尾删除项目的时间复杂度很高？

首先，让我们来看看这些书对“动态数组”的含义：

动态数组（也称为可增长数组、可调整大小的数组、动态表或数组列表）是一种随机访问、大小可变的列表数据结构，允许添加或删除元素。[...]
注意：我们将在堆栈、队列和哈希章节中看到动态数组的实现。

从中我们了解到数组列表是本书作者定义的“动态数组”的示例。

但进一步看，这本书提到：

一旦该数组已满，请立即创建大小为原始数组两倍的新数组。同样，如果数组中的元素小于一半，则将数组大小减小到一半。

（着重号由我补充）

Java不会这样做 - 当元素被删除时，它不会减少存储空间。但作者正在谈论（或认为确实）减小了数组大小。在这种情况下，从最坏情况的角度来看，可以说复杂性是因为减小大小涉及将元素复制到缩小的数组。ArrayListArrayListO(n)n

结论：

尽管对于Java实现来说并非如此，但是当本书的作者谈到“动态数组”时，在必要时删除时“减小数组大小”，那么在数组末尾删除的最坏情况复杂性确实是 。ArrayListO(n)

该条目似乎要么是

1. 不正确，或
2. 没错，但具有误导性。

您绝对正确，您可以在动态数组中的最后一个位置销毁对象，然后减小大小以删除最后一个元素。在许多动态数组的实现中，有时需要执行调整大小操作，以确保分配的数组的大小在元素数量的某个常量因子内。如果发生这种情况，那么是的，您需要创建一个新数组，复制旧元素并释放以前的数组，这确实需要时间O（n）。但是，您可以证明这些调整大小的频率非常低，从末尾执行删除的平均成本为 O（1）。（在更技术意义上，我们说从末尾删除元素的摊销成本是O（1））。也就是说，只要您只关心执行一系列操作的总成本，而不是任何单个操作的成本，那么假装每个操作的成本都是O（1）的，这就不会错。

我想说的是，你很可能在材料中看到一个错别字。查看他们附加到末尾的条目，这区分了不完整和完整的情况，我认为这可能是复制/粘贴错误。在表的引导下，这应该说一些大意是“O（1）如果数组不是'太空'，否则O（n）”。但同样，请记住，每个操作的摊销效率是O（1），这意味着这些可怕的O（n）项实际上不太可能在实践中烧毁你，除非你处于一个专门的环境中，每个操作都需要非常快速地工作。