相关疑难解决方法(0)

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

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

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

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

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

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

我不能很好地算出算法成本，所以我在这里问。

这是一个初始使用1000个元素初始化的向量：

vector<unsigned int> mFreeIndexes(1000);

我将持续将pop_back / push_back元素添加到向量中，但绝不会将push_back超过1000个（因此绝不要强迫向量重新分配）。

在这种情况下，pop_back / push_back操作是O（1）还是O（n）？

以下方法op属于具有两个私有整数值实例变量n和counter的类,这两个实例变量在构造函数中初始化为零值,并且随后仅由方法op修改.

public void op()
{
    if(counter<100)
    {
        op1(); //method with O(1) time complexity
        counter++;
    }else {
        op2(); //method with O(n^2) time complexity
        counter = 0;
    }
    n++;
}

假设方法op1具有时间复杂度O(1),并且方法op2具有时间复杂度O(n ^ 2),以下哪个最好地表示方法op的分摊时间复杂度？

A)O(n)

B)O(n log n)

C)O(1)

D)O(n ^ 2)

E)O(n3)

考试的答案是D.我认为从我对摊销时间的理解应该是C,你算一下大部分时间会发生什么.在这种情况下,最坏的情况是O(n ^ 2),但是大多数时候算法将在O(1)中运行.为什么是O(n ^ 2)？

我目前正在阅读摊销分析.我无法完全理解它与我们为计算算法的平均或最差情况行为而执行的常规分析有何不同.有人可以用排序的例子来解释它吗？