考试答案确认-摊销时间

Question

下面的方法op属于一个具有两个私有整数值实例变量的类，n和counter，这两个值在构造函数中都初始化为零，随后仅通过操作方法修改

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)。