小编Mik*_*ike的帖子

以下方法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)？