堆栈的动态数组实现

Question

程序员希望创建一个堆栈的动态数组实现，在这里，当数组不能容纳更多的元素时，就会创建一个大小为n+10的新数组，而不是重复加倍。

例如，为了插入第一个元素，将创建大小为0+10=10的数组。插入10元素后，为了插入11元素，将创建一个大小为10+10=20的新数组，并将前面的数组元素复制到这个新数组中。

这个堆栈实现的时间复杂度是什么？

Answer 1

在n个插入之后，数组将是O(n)大小的，介于n-10到n+10之间。假设数组的大小为n+10，则计算如下：

尺寸更改-> 10插入->大小更改-> 10插入.

n+10 -> 10插入-> n -> 10插入-> n 10 -> 10插入-> . -> n-n =0

到目前为止，对于n个插入项，我们总共有：

Σ(n-10*i)操作，Σ从i=-1到n

我们得到n*n个总运行时间，现在除以n得到每个插入的运行时间，因此它变成O(n)，对每个操作进行摊销。

Answer 2

为了容纳n*10元素，数组必须增长n时间，所以这可能是O(n)。但是，增长数组需要将其元素复制到新数组，这需要第一次10复制操作，第二次20复制操作，等等，直到n*10 nth。所以我认为这是O(n^2)。