相关疑难解决方法(0)

它与渐近分析有什么不同？你什么时候使用它,为什么？

我读过一些似乎写得很好的文章,比如:

• http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf

• http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

但我还是没有充分理解这些概念.

所以,有人可以为我简化吗？

是ArrayListjava中的数组还是列表？get操作的时间复杂度是什么,是O(n)或者O(1)？

假设我有一个例程,扫描n个项目的整个列表3次,根据大小进行排序,然后bsearches排序列表n次.扫描是O(n)时间,我将调用O(n log(n)),n次bsearch是O(n log(n)).如果我们将所有3加在一起,它是否只是给我们3的最坏情况 - n log(n)值或者语义是否允许增加时间？

很确定,现在我输入的答案是n log(n),但我现在也可以确认我输入了:)

众所周知，通过索引访问数组的时间复杂度是 O(1)。

ArrayList由数组支持的 Java 的文档对其get操作也有相同的说法：

size、isEmpty、get、set、iterator 和 listIterator 操作在恒定时间内运行。

查找是通过获取给定索引处元素的内存地址来完成的，该地址与数组的大小无关（类似于start_address + element_size * index）。我的理解是数组的元素必须在内存中并排存储，这样查找机制才能成为可能。

但是，从这个问题，我了解到 Java 中的数组不能保证其元素连续存储在内存中。如果是这样，它怎么可能总是 O(1)？

编辑：我很清楚 a 是如何ArrayList工作的。我的观点是，如果 JVM 规范不保证数组的连续存储，则其元素可能位于内存中的不同区域。尽管这种情况不太可能发生，但它会使上面提到的查找机制变得不可能，并且 JVM 将有另一种方法来进行查找，不再是 O(1)。在这一点上，这既违反了这个问题顶部所述的常识，也违反了ArrayList关于其的文件get操作。

谢谢大家的回答。

编辑：最后，我认为这是一个特定于 JVM 的事情，但大多数（如果不是全部）JVM 仍然坚持数组元素的连续存储，即使没有保证，以便可以使用上面的查找机制。它简单、高效且具有成本效益。

据我所知，将元素存储在所有地方然后必须采用不同的方法进行查找是愚蠢的。

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

我遇到了这个代码片段的Big O时间复杂度的问题:保证以下代码的时间复杂度为O(n ^ 4).

ArrayList<Integer> list = new ArrayList<Integer>();

for(int i = n; i>=1; i--)           //n 
    for(int j = 1; j<=i; j++)       //n     
        if(!list.contains(i*j))     //n?    
            list.add(i*j);          //1?

我的问题:为什么是O(n ^ 4)而不是O(n ^ 3)？

我刚开始学习数据结构,在进行数组插入时,我想知道为什么数组插入O(n)的时间复杂度而不是O(n + 1)？

在最好的情况下,当插入位于最后位置时,时间复杂度为O(1).我想我们正在考虑1插入元素,因为这里没有移动任何元素.在最坏的情况下,鉴于我们必须移动n个元素然后插入新元素,时间复杂度不应该是O(n + 1)吗？n用于移动元素,1用于插入.

非常感谢帮助.谢谢.