考试答案确认-摊销时间

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对数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 time之后，总的运行时将类似于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)。