什么是恒定摊销时间？

緦唸λ蓇 2024-07-13 11:33:40

摊余时间用简单的术语解释：

如果你执行一个操作一百万次，你并不真正关心该操作的最坏情况或最好情况 - 你关心的是总共花费了多少时间您重复该操作一百万次。

因此，即使操作偶尔很慢也没关系，只要“偶尔”足够少，足以冲淡缓慢的情况即可。摊销时间本质上是指“如果执行多次操作，则每次操作所花费的平均时间”。摊余时间不必是常数；你可以有线性和对数摊销时间或其他任何东西。

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

因此，每次放大所花费的时间大约是上次放大的两倍。但你在这样做之前也等待了两倍的时间！因此，每次扩展的成本可以在插入之间“分摊”。这意味着从长远来看，向数组添加 m 个项目所需的总时间为 O(m)，因此摊余时间（即每次插入的时间）是O(1)。

回复收藏 0 原文

长发绾君心 2024-07-13 11:33:40

这意味着随着时间的推移，最坏的情况将默认为 O(1) 或恒定时间。一个常见的例子是动态数组。如果我们已经为新条目分配了内存，则添加它的时间复杂度为 O(1)。如果我们尚未分配，我们将通过分配（例如，当前金额的两倍）来分配。这个特定的插入不是时间复杂度为O(1)，而是其他东西。

重要的是，该算法保证在一系列操作之后，昂贵的操作将被分摊，从而使整个操作呈现为 O(1)。

或者更严格地说，

有一个常数 c，使得对于
每个操作序列（也以昂贵的操作结束）
长度L，时间不大于
c*L（感谢Rafał Dowgird）

回复收藏 0 原文

情痴 2024-07-13 11:33:40

要开发一种直观的思考方式，请考虑在动态数组中插入元素（例如 < C++ 中的代码>std::vector）。让我们绘制一个图表，显示在数组中插入 N 个元素所需的操作数 (Y) 的依赖性：

黑色图的垂直部分对应于为了扩展数组而重新分配内存。在这里我们可以看到，这种依赖关系可以粗略地表示为一条线。该直线方程为 Y=C*N + b（C 是常数，在我们的例子中 b = 0）。因此，我们可以说，我们平均需要花费 C*N 次操作来向数组添加 N 个元素，或者平均花费 C*1 次操作来添加一个元素（摊销常数时间）。

回复收藏 0 原文

思慕 2024-07-13 11:33:40

重复阅读 3 次后，我发现下面的维基百科解释很有用：

来源：https://en.wikipedia .org/wiki/Amortized_analysis#Dynamic_Array

“动态数组
动态数组的 Push 操作的摊销分析
考虑一个动态数组，其大小随着添加更多元素而增大
比如Java中的ArrayList。如果我们从动态数组开始
如果尺寸为 4，则将四个元素推入其上需要恒定的时间。
然而，将第五个元素推入该数组将花费更长的时间，因为
array 必须创建一个当前大小双倍的新数组 (8)，
将旧元素复制到新数组中，然后添加新元素
元素。接下来的三个推送操作同样需要恒定的时间
时间，然后随后的添加将需要另一个缓慢的
数组大小加倍。
一般来说，如果我们考虑将任意数量的 n 推送到数组
大小为 n 时，我们注意到推送操作需要恒定的时间，除了
最后一个需要 O(n) 时间来执行大小加倍
手术。由于总共有 n 次操作，我们可以取平均值
并找到将元素推入动态数组的方法
需要：O(n/n)=O(1)，常数时间。”

据我理解，这是一个简单的故事：

假设你有很多钱。
而且，你想把它们堆放在一个房间里。
而且，你的手和腿很长，现在或将来需要多长就多长。
而且，你必须把所有的东西都填在一个房间里，所以很容易锁上它。

因此，您直接走到房间的尽头/角落并开始堆放它们。
当你堆放它们时，房间会慢慢地耗尽空间。
然而，当你填满时，很容易将它们堆叠起来。钱拿了，就放钱。简单的。是 O(1)。我们不需要转移之前的任何资金。

一旦房间空间不足。
我们需要另一个更大的房间。
这里有一个问题，因为我们只能有 1 个房间，所以我们只能有 1 把锁，我们需要将该房间中所有现有的钱转移到新的更大的房间中。
所以，把所有的钱从小房间转移到更大的房间。也就是说，将它们全部重新堆叠起来。
所以，我们确实需要转移之前所有的钱。
所以，它是 O(N)。（假设N是之前钱的总数）

换句话说，直到N为止很容易，只需要1次操作，但是当我们需要移动到更大的房间时，我们就进行了N次操作。因此，换句话说，如果我们进行平均，则在开始时会插入 1 次，而在移动到另一个房间时会再进行 1 次移动。
总共2次操作，1次插入，1次移动。

假设即使在小房间中 N 也很大，如 100 万，那么与 N（100 万）相比的 2 次操作实际上并不是一个可比较的数字，因此它被认为是常数或 O(1)。

假设当我们在另一个更大的房间里完成上述所有操作时，并且再次需要移动。
还是一样。
比如说，N2（比如说，10亿）是大房间里新的钱数

所以，我们有N2（包括之前的N，因为我们把所有的东西从小房间搬到大房间）

我们仍然只需要2个操作，一个是插入更大的房间，然后另一个移动操作移动到更大的房间。

因此，即使对于 N2（10 亿），每个操作也需要 2 次。这又没什么了。所以，它是常数，或者 O(1)

因此，当 N 从 N 增加到 N2 或其他时，它并不重要。它仍然是常数，或者 N 中的每一个都需要 O(1) 次操作。

现在假设，您的 N 为 1，非常小，钱数也很少，并且您有一个非常小的房间，只能容纳 1 块钱。

只要你把钱塞满房间，房间就满了。

当你去到更大的房间时，假设它只能再容纳一张钱，总共 2 枚钱。这意味着，之前的钱又转移了 1 笔。又被填满了。

这样，N 增长缓慢，并且不再是恒定的 O(1)，因为我们将所有钱从前一个房间移走，但只能再容纳 1 个钱。

100 次后，新房间可容纳 100 枚先前的钱币，并可再容纳 1 枚钱币。这是 O(N)，因为 O(N+1) 是 O(N)，即 100 或 101 的次数相同，都是数百，而不是之前的故事，个到百万，个到数十亿。

因此，这是为我们的钱（变量）分配房间（或内存/RAM）的低效方式。

因此，一个好方法是分配更多的空间，其幂为 2。

第一个房间大小 = 适合 1 笔钱
第二个房间大小 = 适合 4 块钱
第三个房间大小 = 适合 8 枚钱
第四个房间大小 = 适合 16 枚钱
第 5 个房间大小 = 适合 32 枚钱
第 6 个房间大小 = 适合 64 枚钱
第 7 个房间尺寸 = 适合 128 枚钱
第 8 个房间大小 = 适合 256 枚钱
第 9 个房间大小 = 适合 512 钱
第10个房间大小=适合1024张钱
第 11 个房间大小 = 可容纳 2,048 枚钱
...
第 16 个房间大小 = 适合 65,536 钱
...
第32个房间大小= 4,294,967,296 钱
...
第 64 个房间大小= 适合 18,446,744,073,709,551,616 数钱

为什么这个更好？因为与 RAM 中的内存量相比，它看起来一开始增长缓慢，后来增长得更快。

这是有帮助的，因为在第一种情况下，虽然它很好，但每笔钱要做的总工作量是固定的（2）并且与房间大小（N）不可比较，我们在初始阶段占用的房间可能太大大（100万），我们可能无法完全使用，这取决于我们在第一种情况下是否可以节省那么多钱。

然而，在最后一种情况下，即 2 的幂，它会在 RAM 的限制内增长。因此，增加 2 的幂后，Armotized 分析保持不变，并且对于我们目前拥有的有限 RAM 来说是友好的。

I found below Wikipedia explanation useful, after repeat reading for 3 times:

Source: https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array

"Dynamic Array
Amortized Analysis of the Push operation for a Dynamic Array
Consider a dynamic array that grows in size as more elements are added to it
such as an ArrayList in Java. If we started out with a dynamic array
of size 4, it would take constant time to push four elements onto it.
Yet pushing a fifth element onto that array would take longer as the
array would have to create a new array of double the current size (8),
copy the old elements onto the new array, and then add the new
element. The next three push operations would similarly take constant
time, and then the subsequent addition would require another slow
doubling of the array size.
In general if we consider an arbitrary number of pushes n to an array
of size n, we notice that push operations take constant time except
for the last one which takes O(n) time to perform the size doubling
operation. Since there were n operations total we can take the average
of this and find that for pushing elements onto the dynamic array
takes: O(n/n)=O(1), constant time."

To my understanding as a simple story:

Assume you have a lot of money.
And, you want to stack them up in a room.
And, you have long hands and legs, as much long as you need now or in future.
And, you have to fill all in one room, so it is easy to lock it.

So, you go right to the end/ corner of the room and start stacking them.
As you stack them, slowly the room will run out of space.
However, as you fill it was easy to stack them. Got the money, put the money. Easy. It's O(1). We don't need to move any previous money.

Once room runs out of space.
We need another room, which is bigger.
Here there is a problem, since we can have only 1 room so we can have only 1 lock, we need to move all the existing money in that room into the new bigger room.
So, move all money, from small room, to bigger room. That is, stack all of them again.
So, We DO need to move all the previous money.
So, it is O(N). (assuming N is total count of money of previous money)

In other words, it was easy till N, only 1 operation, but when we need to move to a bigger room, we did N operations. So, in other words, if we average out, it is 1 insert in the begin, and 1 more move while moving to another room.
Total of 2 operations, one insert, one move.

Assuming N is large like 1 million even in the small room, the 2 operations compared to N (1 million) is not really a comparable number, so it is considered constant or O(1).

Assuming when we do all the above in another bigger room, and again need to move.
It is still the same.
say, N2 (say, 1 billion) is new amount of count of money in the bigger room

So, we have N2 (which includes N of previous since we move all from small to bigger room)

We still need only 2 operations, one is insert into bigger room, then another move operation to move to a even bigger room.

So, even for N2 (1 billion), it is 2 operations for each. which is nothing again. So, it is constant, or O(1)

So, as the N increases from N to N2, or other, it does not matter much. It is still constant, or O(1) operations required for each of the N .

Now assume, you have N as 1, very small, the count of money is small, and you have a very small room, which will fit only 1 count of money.

As soon as you fill the money in the room, the room is filled.

When you go to the bigger room, assume it can only fit one more money in it, total of 2 count of money. That means, the previous moved money and 1 more. And again it is filled.

This way, the N is growing slowly, and it is no more constant O(1), since we are moving all money from previous room, but can only fit only 1 more money.

After 100 times, the new room fits 100 count of money from previous and 1 more money it can accommodate. This is O(N), since O(N+1) is O(N), that is, the degree of 100 or 101 is same, both are hundreds, as opposed to previous story of, ones to millions and ones to billions.

So, this is inefficient way of allocating rooms (or memory/ RAM) for our money (variables).

So, a good way is allocating more room, with powers of 2.

1st room size = fits 1 count of money
2nd room size = fits 4 count of money
3rd room size = fits 8 count of money
4th room size = fits 16 count of money
5th room size = fits 32 count of money
6th room size = fits 64 count of money
7th room size = fits 128 count of money
8th room size = fits 256 count of money
9th room size = fits 512 count of money
10th room size= fits 1024 count of money
11th room size= fits 2,048 count of money
...
16th room size= fits 65,536 count of money
...
32th room size= fits 4,294,967,296 count of money
...
64th room size= fits 18,446,744,073,709,551,616 count of money

Why is this better? Because it looks to grow slowly in the begin, and faster later, that is, compared to the amount of memory in our RAM.

This is helpful because, in the first case though it is good, total amount of work to be done per money is fixed (2) and not comparable to room size (N), the room that we took in the initial stages might be too big (1 million) that we may not use fully depending on if we may get that much money to save at all in first case.

However, in the last case, powers of 2, it grows in the limits of our RAM. And so, increasing in powers of 2, both the Armotized analysis remains constant and it is friendly for the limited RAM that we have as of today.

回复收藏 0 原文

嘿嘿嘿 2024-07-13 11:33:40

我创建了这个简单的 python 脚本来演示 python 列表中追加操作的摊销复杂性。我们不断向列表中添加元素并为每个操作计时。在此过程中，我们注意到某些特定的追加操作需要更长的时间。这些峰值是由于执行新的内存分配造成的。需要注意的重要一点是，随着追加操作数量的增加，峰值会变得更高，但间距也会增加。间距的增加是因为每次初始内存溢出时都会保留更大的内存（通常是之前的两倍）。希望这会有所帮助，我可以根据建议进一步改进它。

import matplotlib.pyplot as plt
import time


a = []
N = 1000000

totalTimeList = [0]*N
timeForThisIterationList = [0]*N
for i in range(1, N):
    startTime = time.time()
    a.append([0]*500) # every iteartion, we append a value(which is a list so that it takes more time)
    timeForThisIterationList[i] = time.time() - startTime
    totalTimeList[i] = totalTimeList[i-1] + timeForThisIterationList[i]
max_1 = max(totalTimeList)
max_2 = max(timeForThisIterationList)

plt.plot(totalTimeList, label='cumulative time')
plt.plot(timeForThisIterationList, label='time taken per append')
plt.legend()
plt.title('List-append time per operation showing amortised linear complexity')
plt.show()

这会产生以下图

I created this simple python script to demonstrate the amortized complexity of append operation in a python list. We keep adding elements to the list and time every operation. During this process, we notice that some specific append operations take much longer time. These spikes are due to the new memory allocation being performed. The important point to note is that as the number of append operations increases, the spikes become higher but increase in spacing. The increase in spacing is because a larger memory (usually double the previous) is reserved every time the initial memory hits an overflow. Hope this helps, I can improve it further based on suggestions.

import matplotlib.pyplot as plt
import time


a = []
N = 1000000

totalTimeList = [0]*N
timeForThisIterationList = [0]*N
for i in range(1, N):
    startTime = time.time()
    a.append([0]*500) # every iteartion, we append a value(which is a list so that it takes more time)
    timeForThisIterationList[i] = time.time() - startTime
    totalTimeList[i] = totalTimeList[i-1] + timeForThisIterationList[i]
max_1 = max(totalTimeList)
max_2 = max(timeForThisIterationList)

plt.plot(totalTimeList, label='cumulative time')
plt.plot(timeForThisIterationList, label='time taken per append')
plt.legend()
plt.title('List-append time per operation showing amortised linear complexity')
plt.show()

This produces the following plot

回复收藏 0 原文

江湖彼岸 2024-07-13 11:33:40

任何函数的性能都可以通过将“函数调用总数”除以“所有这些调用所花费的总时间”来平均。即使每次调用花费的时间越来越长的函数，仍然可以通过这种方式进行平均。

因此，以恒定摊销时间执行的函数的本质是，这个“平均时间”达到一个上限，并且随着调用次数的持续增加而不会超过该上限。任何特定的调用的性能可能会有所不同，但从长远来看，这个平均时间不会变得越来越大。

这是在恒定摊销时间下执行的东西的基本优点。

回复收藏 0 原文

泪冰清 2024-07-13 11:33:40

上述解释适用于聚合分析，即对多个操作进行“平均”的想法。
我不确定它们如何应用于银行家方法或物理学家摊销分析方法。

现在。我不太确定正确答案。
但这与物理学家+银行家方法的原则条件有关：（

运营的摊余成本之和）>=（运营的实际成本之和）。

我面临的主要困难是，鉴于运营的摊余渐近成本与正常渐近成本不同，我不确定如何评估摊余成本的重要性。

也就是说，当有人给我一个摊余成本时，我知道它与正常渐近成本不同，那么我可以从摊余成本中得出什么结论呢？

由于我们遇到某些业务收费过高而其他业务收费不足的情况，一种假设可能是引用单个业务的摊余成本是没有意义的。

例如：对于斐波那契堆，引用递减键的摊余成本为 O(1) 是没有意义的，因为成本是通过“早期操作在增加堆潜力方面所做的工作”来降低的。

或者

我们可以有另一个假设，对摊余成本进行如下推理：

我知道昂贵的操作将先于多个低成本操作。
为了分析的目的，我将对一些低成本操作收取过高的费用，这样它们的渐近成本就不会改变。
为了分析的目的
通过这些增加的低成本操作，我可以证明昂贵的操作具有较小的渐近成本。
通过这些增加的低成本操作，
因此，我改进/降低了 n 次操作的成本的渐近界限。

因此，摊余成本分析+摊余成本界限现在仅适用于昂贵的操作。廉价操作具有与其正常渐近成本相同的渐近摊销成本。

回复收藏 0 原文

你怎么这么可爱啊 2024-07-13 11:33:40

摊销运行时间：
这是指以每个操作使用的时间或内存来计算算法复杂性。
它在大多数情况下运算速度很快但有时算法运算速度很慢时使用。
因此，研究操作序列以了解有关摊销时间的更多信息。

回复收藏 0 原文

好久不见√ 2024-07-13 11:33:40

进一步以动态数组为例，假设我们可以在数组中容纳 N 个项目，然后进行加倍。

成本分解可总结如下：

通常，向数组添加一个项目需要常数时间（即 O(1)）。因此，添加 N 个项目的成本 = N * O(1)
添加 N 个项目后，为了添加下一个元素，我们需要分配两倍的空间并将数据复制到新数组。添加第 (N+1) 个元素的成本 = O(N)
总成本 = N*O(1) + O(N)，即 O(N)
每次操作的摊余成本 = O(N) / (N+1 ) = O(1)

希望这有帮助！

回复收藏 0 原文

什么是恒定摊销时间？

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（9）

关于作者

相关话题

热门标签

推荐作者

不再见

真是无聊啊

樱娆

浅语花开

烛光

绻影浮沉

友情链接

什么是恒定摊销时间？

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（9）

关于作者

相关话题

热门标签

推荐作者

不再见

真是无聊啊

樱娆

浅语花开

烛光

绻影浮沉

友情链接

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。