在动态数组中删除

Question

任何人都可以解释时间复杂度（在动态数组结束时删除）？

我认为答案是O（1）

但在书中提到了O（n）。

Answer 1

由于我们讨论的是动态数组，即能够向/从中添加/删除元素的数组，因此实现动态数组有两种可能的解决方案：

1. 您可以分配足够的内存来容纳所有当前和未来的元素。此外，您需要知道最后一个可能的索引。使用此设置，删除最后一个元素的复杂性为O（1），因为您只是递减最后一个索引。但是，删除非最后一个元素具有线性复杂性，因为在递减最后一个索引之前需要将所有后面的元素复制到上一个元素。此外，您可能难以在分配时确定最大可能的大小，可能导致溢出问题或内存浪费。
2. 您可以使用列表实现它。这样你就不会知道最后一个元素的地址是什么，所以你需要迭代你的列表直到倒数第二个项目然后释放最后一个项目的内存并将倒数第二个项目的下一个设置为nil。由于本书提到了删除最后一个元素的O（n）的复杂性，我们可以安全地假设通过动态数组，本书意味着第二个选项。