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