更合适的说法是分摊 O(1) vs O(n) 插入未排序的动态数组？

Question

这属于 Whosebug 的“软件算法”。com/help/on-topic，在本例中，是一种将项目添加到动态未排序数组的软件算法

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

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

 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) 时间提出论据(What is amortized analysis of algorithms?)，因为每次调整大小时，都必须等待特定的时间才能进行下一次调整？

在那张图表中，O(1) 是否也有意义？

Answer 1

没有

"Amortized O(1) time" 表示非常具体的事情 - 它表示一次插入 n 项的成本是 O(n)。仅仅说 "the things that take a long time don't happen very often" 是不够的 - 您实际上必须从数学上分析算法。

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

更合适的说法是分摊 O(1) vs O(n) 插入未排序的动态数组？

More appropriate to say Amortized O(1) vs O(n) for insertion into unsorted dynamic array?

java

algorithm

arraylist

time-complexity

amortized-analysis