考试答案确认 - 摊还时间

Question

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

Answer 1

在谈论摊销的运行时,你不能计算大多数时候会发生什么.首先,你如何定义大部分时间？操作的分摊运行时间可以视为操作的平均运行时间.

现在你的问题:

为简单起见,我假设你写的if (counter < 99)而不是if (counter < 100).这样,操作在100个循环之后而不是在101个循环之后重复.

写作时O(...),在下文中,我实际上是指?(...),因为否则你的问题的答案将是微不足道的,因为一切O(1)都是O(n^2).

调用op()100次后,总运行时间为99 + 100^2.
调用op()200次后,总运行时间将为2 * 99 + 100^2 + 200^2.
现在让我们忘记那些,99或者2 * 99因为它们被n^2价值观所支配.
因此,在调用op() n次数之后,总运行时间将类似于100^2 + 200^2 + ... + n^2(为简单起见,我们假设它可n被整除100).

现在我将证明这是在O(n^3).

Let k = n/100

100^2 + 200^2 + ... + n^2
= 100^2 * (1^2 + 2^2 + ... + k^2)
=(*) O(100^2 * k * k^2)
= O(k^3)
= O(n^3)

(*): sum from 1 to k of i^2 is k (k+1) (2k+1) / 6 = O(k^3)

所以最后,平均运行时间op()是O(n^3 / n) = O(n^2).因此,摊销运行时op()是O(n^2).