有人可以澄清摊销常数时间（加倍数组向量）吗？
Can Someone Clarify Amortized Constant Time (doubling array vectors)?
我想我理解了这个概念。让我根据它在 doubling array vectors 上的应用来解释我是如何理解它的。
The rate of copying items to an array remains constant. While the growth of the array is exponential, the rate at which the array needs to double in size is logarithmic. Because of this, the decreased occurrence of doubling the array size 'sort of' cancels out the resources required to double the array and copy it's elements, as this only happens O(n Log N) times throughout the life of the array. Thus, the O(n^2) for the rate of growth combined with O(n Log N) for the frequency at which the array grows resolves to somewhere around O(n).
这是正确的吗？如果不是，那是哪些部分出错了？我无法解决这个问题。我很确定我给出的 Big Oh 符号不正确。
谢谢
假设您在数组达到 2 个元素时加倍，4、8、16、32、...、2^k.
这意味着 O(log n) 对大小为 n 的数组进行加倍运算。很想说这就是事情 O(n log n)，但事实并非如此。
为所有 这些加倍操作执行的操作数受限于：
1 + 2 + 4 + ... + 2^k = (2^k - 1) (sum of geometric series)
但是请注意 k = number of doubling ops = O(log n)，因此我们将加倍所需的操作数限制为 2^(log n) = n
所以，整个事情仍然是 O(n)：虽然你在加倍数组时做了很多操作，但考虑到那些 "a lot of operations" 与整个数组大小的关系以及你执行了多少次他们，他们不再是"a lot"，只是O(n)。
摊销基本上意味着您要着眼大局：当然，我今天可能需要工作很多，但这意味着我可以在本周剩下的时间里呆在家里。这是否意味着我这周会工作很多？不，我实际上工作很少。
我认为你的解释并不完全准确而且过于复杂。没有任何类型，也没有 O(n^2) 增长率。如您所见，数学加起来就是 O(n)。
总的来说，我的建议是忽略摊销这个词，只做数学运算。我已经看到它无缘无故地引起了很多混乱。当然，这可能是此类分析中涉及的正式内容，但大多数时候它只会引发对所发生情况的困惑。问问自己："ok, how many operations will this algorithm perform?"。通常情况下，你不需要任何花哨的东西来回答这个问题。
不讨论您如何计算 "amortised" 时间，而是讨论它的用途：您可能有一个算法，您可以重复使用该算法从状态 1 到状态 2 再到状态 3 ... 等等。从一个状态到另一个状态的成本可能相差很大，从一个状态到另一个状态的最大成本可能非常高。但是，有时您可以证明从状态 1 到状态 n 的总成本远小于最大值的 n 倍。所以 "amortised" 成本是从状态 1 到状态 n 的平均成本。
有时最大成本可能很重要。例如在音乐播放应用中，输出下一个音乐样本的时间必须总是低，否则声音会断断续续，这是不可接受的。然而，在其他情况下，重要的是遍历所有状态的总时间，只要平均值合适就可以了。
请注意，摊销时间与平均时间不同。根据给定的数据，算法可能需要不同的时间。如果某些输入 X 花费的时间比平均时间长得多，则可能是您使用该算法一百万次来处理相同的输入 X，并且总时间很长。
我想我理解了这个概念。让我根据它在 doubling array vectors 上的应用来解释我是如何理解它的。
The rate of copying items to an array remains constant. While the growth of the array is exponential, the rate at which the array needs to double in size is logarithmic. Because of this, the decreased occurrence of doubling the array size 'sort of' cancels out the resources required to double the array and copy it's elements, as this only happens
O(n Log N)times throughout the life of the array. Thus, theO(n^2)for the rate of growth combined withO(n Log N)for the frequency at which the array grows resolves to somewhere aroundO(n).
这是正确的吗？如果不是，那是哪些部分出错了？我无法解决这个问题。我很确定我给出的 Big Oh 符号不正确。
谢谢
假设您在数组达到 2 个元素时加倍，4、8、16、32、...、2^k.
这意味着 O(log n) 对大小为 n 的数组进行加倍运算。很想说这就是事情 O(n log n)，但事实并非如此。
为所有 这些加倍操作执行的操作数受限于：
1 + 2 + 4 + ... + 2^k = (2^k - 1) (sum of geometric series)
但是请注意 k = number of doubling ops = O(log n)，因此我们将加倍所需的操作数限制为 2^(log n) = n
所以，整个事情仍然是 O(n)：虽然你在加倍数组时做了很多操作，但考虑到那些 "a lot of operations" 与整个数组大小的关系以及你执行了多少次他们，他们不再是"a lot"，只是O(n)。
摊销基本上意味着您要着眼大局：当然，我今天可能需要工作很多，但这意味着我可以在本周剩下的时间里呆在家里。这是否意味着我这周会工作很多？不，我实际上工作很少。
我认为你的解释并不完全准确而且过于复杂。没有任何类型，也没有 O(n^2) 增长率。如您所见，数学加起来就是 O(n)。
总的来说，我的建议是忽略摊销这个词，只做数学运算。我已经看到它无缘无故地引起了很多混乱。当然，这可能是此类分析中涉及的正式内容，但大多数时候它只会引发对所发生情况的困惑。问问自己："ok, how many operations will this algorithm perform?"。通常情况下，你不需要任何花哨的东西来回答这个问题。
不讨论您如何计算 "amortised" 时间，而是讨论它的用途：您可能有一个算法，您可以重复使用该算法从状态 1 到状态 2 再到状态 3 ... 等等。从一个状态到另一个状态的成本可能相差很大，从一个状态到另一个状态的最大成本可能非常高。但是，有时您可以证明从状态 1 到状态 n 的总成本远小于最大值的 n 倍。所以 "amortised" 成本是从状态 1 到状态 n 的平均成本。
有时最大成本可能很重要。例如在音乐播放应用中，输出下一个音乐样本的时间必须总是低，否则声音会断断续续，这是不可接受的。然而，在其他情况下，重要的是遍历所有状态的总时间，只要平均值合适就可以了。
请注意，摊销时间与平均时间不同。根据给定的数据，算法可能需要不同的时间。如果某些输入 X 花费的时间比平均时间长得多，则可能是您使用该算法一百万次来处理相同的输入 X，并且总时间很长。