摊销分析
Amortized Analysis
我在研究这个问题时遇到了这个问题，该问题要求考虑执行一系列 n 操作的数据结构。如果第 k 个操作的成本为 k，如果它是一个完美的平方，否则成本为 1，那么操作的总成本是多少，每个操作的摊销成本是多少。
我想出一个求和公式有点困难，该求和公式提供了一个完美平方的定义，我可以在其中看到总和产生的结果。任何 thoughts/advice?
从1到n的i^2之和可以计算为n(n+1)(2n+1)/6。我在一本数学书上找到的，在网上找不到简单的公式。但是查看http://mathworld.wolfram.com/Sum.html，公式(6).
为了计算这个总和，令 n 为 k 的平方根，向下舍入。该公式与 n^3 成正比，即 sqrt(k)^3 = k^(3/2)。这给出了 O(k^(3/2)).
的摊销时间
我在研究这个问题时遇到了这个问题，该问题要求考虑执行一系列 n 操作的数据结构。如果第 k 个操作的成本为 k，如果它是一个完美的平方，否则成本为 1，那么操作的总成本是多少，每个操作的摊销成本是多少。
我想出一个求和公式有点困难，该求和公式提供了一个完美平方的定义，我可以在其中看到总和产生的结果。任何 thoughts/advice?
从1到n的i^2之和可以计算为n(n+1)(2n+1)/6。我在一本数学书上找到的，在网上找不到简单的公式。但是查看http://mathworld.wolfram.com/Sum.html，公式(6).
为了计算这个总和，令 n 为 k 的平方根，向下舍入。该公式与 n^3 成正比，即 sqrt(k)^3 = k^(3/2)。这给出了 O(k^(3/2)).