摊销通俗地说的复杂性？ [英] Amortized complexity in layman's terms?

问题描述

有人能解释一下摊销的复杂性？我一直有一个很难在网上找到一个precise定义，我不知道它是如何完全涉及算法分析。有用的东西，即使外部引用，将是非常美联社preciated。

Can someone explain amortized complexity in layman's terms? I've been having a hard time finding a precise definition online and I don't know how it entirely relates to the analysis of algorithms. Anything useful, even if externally referenced, would be highly appreciated.

推荐答案

摊销复杂度是每个操作的总费用，评估了操作序列。这样做是为了保证整个序列的总费用，同时允许各个操作要大大高于平均更昂贵。

Amortized complexity is the total expense per operation, evaluated over a sequence of operations. The idea is to guarantee the total expense of the entire sequence, while permitting individual operations to be much more expensive than the average.

一个简单的例子是C的行为++ 的std ::矢量＆lt;＆GT; 。当的push_back（）增加了矢量大小高于pre-分配值，双打分配的长度。这意味着的单一通话的push_back（）可能需要O（N）的时间来执行（作为数组的内容复制到新的内存分配）。但是，因为分配的规模增加了一倍，在未来的N-1调用的push_back（）将每一个需要O（1）的时间来执行。所以，N运营总还是需要O（N）的时间 - 让的push_back（） 0的摊余成本（1）每个操作

One simple example is the behavior of C++ std::vector<>. When push_back() increases the vector size above its pre-allocated value, it doubles the allocated length. This means that a single call of push_back() may take O(N) time to execute (as the contents of the array are copied to the new memory allocation). However, because the size of the allocation was doubled, the next N-1 calls to push_back() will each take O(1) time to execute. So, the total of N operations will still take O(N) time -- giving push_back() an amortized cost of O(1) per operation.

这篇关于摊销通俗地说的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！