4

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

4

1 回答 1

9

在谈论摊销运行时，您无法计算大部分时间会发生什么。首先，您如何定义大多数时间？操作的摊销运行时间可以看作是操作的平均运行时间。

现在解决您的问题：

为简单起见，我假设您写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.
现在让我们忘记那些99or 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)。

于 2012-10-09T20:21:10.963 回答