3

这属于 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) 也有意义吗？

4

1 回答 1

8

不。

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

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

于 2015-02-07T01:39:29.570 回答