考试答案确认-摊销时间 [英] Exam answer confirmation - Amortized time

问题描述

以下方法op属于具有两个私有整数值实例变量n的类 和计数器，它们都在构造函数中初始化为零，随后仅 通过方法op修改.

The following method op belongs to a class with two private integer-valued instance variables, n and counter, both of which are initialised to the value zero in the constructor, and subsequently only modified by method 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的摊余时间复杂度?

Assuming that method op1 has time complexity O(1) , and method op2 has time complexity O(n^2), which of the following best represents the amortized time complexity of method op?

A)O(n)

B)O(n log 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)?

where the answer to the exam was D. I think it should have been C as from my understanding of amortized time, you count what will occur most of the time. In this situation, the worst case is O(n^2), however most of the time the algorithm will run in O(1). Why is it O(n^2)?

推荐答案

在谈论摊销的运行时时，您可以不计算最次的时间. 首先，您怎么甚至在大多数时间定义 ? 一项操作的摊销运行时间可以视为该操作的平均运行时间.

When talking about amortized runtime, you can not count what will occur most of the time. To start, how do you even define most of the time? The amortized runtime of an operation can be seen as the average runtime of the operation.

为简单起见，我将假设您编写的是if (counter < 99)而不是if (counter < 100).这样，操作将在100个周期之后而不是101个周期之后重复自身.

For simplicity, I will assume that you wrote if (counter < 99) instead of if (counter < 100). This way, the operation repeats itself after 100 cycles instead of after 101 cycles.

在下文中，当写O(...)时，我实际上是指Θ(...)，因为否则您的问题的答案将是微不足道的，因为所有O(1)也是O(n^2).

When writing O(...), in the following, I will actually mean Θ(...), because otherwise the answer to your question would be trivial, as everything which is O(1) is also 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整除).

After calling op() 100 times, the total run time would be 99 + 100^2.
After calling op() 200 times, the total run time would be 2 * 99 + 100^2 + 200^2.
Now let's just forget about those 99 or 2 * 99, as they are dominated by the n^2 values.
So after calling op() n times, the total run time would be something like 100^2 + 200^2 + ... + n^2 (for simplicity, let's assume that n is divisible by 100).

现在，我将显示它在O(n^3)中.

Now I will show that this is in 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).

So finally, the average runtime of op() is O(n^3 / n) = O(n^2). Therefore, the amortized runtime of op() is O(n^2).

这篇关于考试答案确认-摊销时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！