更适合说 Amortized O(1) vs O(n) 插入未排序的动态数组? [英] More appropriate to say Amortized O(1) vs O(n) for insertion into unsorted dynamic array?

问题描述

这属于软件算法"来自 stackoverflow.com/help/on-topic，在本例中，是一种将项目添加到动态未排序数组的软件算法

This falls under "a software algorithm" from stackoverflow.com/help/on-topic, in this case, a software algorithm to add an item to a dynamic unsorted array

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

This is chart we made in class about the runtimes of operations on different data structures

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

The question I have is about the runtime for inserting(or adding) a value into the dynamic unsorted array. Here is our code for doing this

 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) 操作.所以整个函数的最坏情况或大 oh 是 O(n)

I understand how this could be interpreted as O(n). The ensureCapacity function is technically apart of the operations that consist of insert and then with runtime analysis, https://academics.tjhsst.edu/compsci/CS2C/U2/bigoh.html, you would say that the worst case of the two branches is when every element of the original array is copied into the new array which is an O(n) operation. So the worst case or big oh of the whole function is O(n)

是否也可以为摊销的 O(1) 时间进行论证(什么是算法的摊销分析?)因为每次调整大小时，您都必须等待特定的时间才能进行下一次调整大小?

Could an argument be made for amortized O(1) time as well(What is amortized analysis of algorithms?) because each time you resize, you have to wait a specific amount of time before the next resize?

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

In that chart, would O(1) also make sense then?

推荐答案

没有

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

"Amortized O(1) time" means a very specific thing - it means that the cost of inserting n items, one at a time, is O(n). It is not enough to say that "the things that take a long time don't happen very often" - you do actually have to analyze the algorithm mathematically.

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

This particular case (inserting an item into an array, or resizing it if full) is a well-known one. As it turns out, if you resize the array by a constant factor (e.g. doubling it each time it's full) then this operation is amortized O(1). If you add a fixed number of elements (e.g. adding 100 each time it's full) then it's still amortized O(n), because it takes O(n²) time to add n elements individually.

这篇关于更适合说 Amortized O(1) vs O(n) 插入未排序的动态数组?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！