对于插入未排序的动态数组,更适合使用Amortized O(1)vs O(n)？

Question

这属于stackoverflow.com/help/on-topic的"软件算法",在这种情况下,是一个将项添加到动态未排序数组的软件算法

这是我们在课堂上关于不同数据结构上的操作的运行时间的图表

我的问题是关于将值插入(或添加)到动态未排序数组中的运行时.这是我们执行此操作的代码

 public void insert(E value) {
    ensureCapacity(size + 1);
    elementData[size] = value;
    size++;
}
  private void ensureCapacity(int capacity) {
    if (capacity > elementData.length) {
        int newCapacity = elementData.length + 100;
        if (capacity > newCapacity) {
            newCapacity = capacity;
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

我理解这可以解释为O(n).ensureCapacity函数在技术上是由插入和运行时分析组成的操作的一部分,https://academics.tjhsst.edu/compsci/CS2C/U2/bigoh.html,你会说这两个分支的最坏情况是将原始数组的每个元素复制到新数组中,这是一个O(n)操作.所以整个函数的最坏情况或大哦是O(n)

是否可以对摊销的O(1)时间进行争论(算法的摊销分析是什么？)因为每次调整大小时,你必须在下一次调整大小之前等待一段特定的时间？

在那张图表中,O(1)也会有意义吗？

Answer 1

没有.

"摊销的O(1)时间"意味着一个非常具体的事情 - 它意味着一次一个地插入n个项目的成本是O(n).仅仅说"需要很长时间的事情并不经常发生"是不够的 - 你实际上必须以数学方式分析算法.

这种特殊情况(将项目插入数组,或者如果已满,则调整大小)是众所周知的.事实证明,如果你通过一个常数因子调整数组的大小(例如每次加满时将其加倍),那么这个操作就是摊销O(1).如果添加固定数量的元素(例如,每次加满时加100),那么它仍然会分摊O(n),因为单独添加n个元素需要O(n ²)时间.