big-o - 考试答案确认 - 摊销时间

Question

以下方法 op 属于具有两个私有(private)整数值实例变量的类，n
和计数器，它们都在构造函数中初始化为零值，随后仅
由方法 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 主导值(value)观。
所以打电话后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) .