什么是恒分期时间，当谈到时间的算法的复杂度是什么意思？

深入浅出的摊余时间解释：

如果你做一个操作说万次，你真的不关心最坏情况或最好的情况是操作的 - 你关心的是有多少时间是在拍摄总在重复操作一百万次。

因此​​，它并不重要，如果操作很慢在一段时间一次，只要过一段时间是够罕见的缓慢被摊薄了。从本质上讲分期时间的意思是每个操作的平均时间服用，如果你做很多操作。摊余时间不必是恒定的;你可以有线性和对数摊销时间或任何其他人。

让我们以动态数组的垫例如，你反复地添加新项目。一般情况下增加一个项目时间是固定的（即 O（1））。但每次的数组已满，您分配两倍的空间，将数据复制到新的区域，并释放旧的空间。假设分配和释放运行在固定时间内，这个扩大过程需要 O（N）时间，其中n是阵列的电流大小。

所以，每次你放大的时候，你需要大约两倍的时间作为最后的放大。但是，你也已经等了两倍的时间做这件事之前！因此，每个放大的成本可能是S $ P $垫出来的插入之一。这意味着，从长期来看，总时间采取添加的 M 的项目到数组 O（M）等的分期时间（即每次插入时间） O（1）。

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.

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.

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).