固定摊销时间 [英] Constant Amortized Time

问题描述

在谈论算法的时间复杂度时，Constant Amortized Time"是什么意思?

What is meant by "Constant Amortized Time" when talking about time complexity of an algorithm?

推荐答案

用简单的术语解释摊销时间:

Amortised time explained in simple terms:

如果你做了一百万次的操作，你并不真正关心那个操作的最坏情况或最好情况——你关心的是当你重复这个操作时总共花费了多少时间一百万次.

If you do an operation say a million times, you don't really care about the worst-case or the best-case of that operation - what you care about is how much time is taken in total when you repeat the operation a million times.

所以如果操作偶尔很慢也没关系，只要偶尔"很少见，足以稀释缓慢.基本上摊销时间意味着如果您进行多次操作，则每次操作所花费的平均时间".摊销时间不一定是常数；你可以有线性和对数摊销时间或其他任何东西.

So it doesn't matter if the operation is very slow once in a while, as long as "once in a while" is rare enough for the slowness to be diluted away. Essentially amortised time means "average time taken per operation, if you do many operations". Amortised time doesn't have to be constant; you can have linear and logarithmic amortised time or whatever else.

让我们以 mats 的动态数组为例，您可以反复向其中添加新项目.通常添加一个项目需要恒定的时间(即 O(1)).但是每次数组已满时，您分配两倍的空间，将数据复制到新区域，并释放旧空间.假设分配和释放在恒定时间内运行，这个扩大过程需要 O(n) 时间，其中 n 是数组的当前大小.

Let's take mats' example of a dynamic array, to which you repeatedly add new items. Normally adding an item takes constant time (that is, O(1)). But each time the array is full, you allocate twice as much space, copy your data into the new region, and free the old space. Assuming allocates and frees run in constant time, this enlargement process takes O(n) time where n is the current size of the array.

因此，每次放大所需的时间大约是上次放大的两倍.但是你也等了两倍的时间才这样做！因此，每次扩大的成本可以在插入之间分摊".这意味着从长远来看，将 m 项添加到数组所花费的总时间为 O(m)，因此分摊时间(即每次插入的时间)是 O(1).

So each time you enlarge, you take about twice as much time as the last enlarge. But you've also waited twice as long before doing it! The cost of each enlargement can thus be "spread out" among the insertions. This means that in the long term, the total time taken for adding m items to the array is O(m), and so the amortised time (i.e. time per insertion) is O(1).

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