algorithm - 摊销分析

Question

我在研究要求考虑执行一系列 n 操作的数据结构时遇到了这个问题。如果第 k 个操作的成本为 k，如果它是完全平方，则成本为 1，那么操作的总成本是多少，每个操作的摊销成本是多少。

我想出一个求和公式有点困难，该公式提供了一个完美平方的定义，我可以在其中看到总和的结果。有什么想法/建议吗？

Answer 1

i^2 从 1 到 n 的总和可以计算为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))。