参考文献： [MS18] Micciancio D, Sorrell J. Ring packing and amortized FHEW bootstrapping. ICALP 2018: 100:1-100:14.[GPV23] Guimarães A, Pereira H V L, Van Leeuwen B. Amortized bootstrapping revisited: Sim

参考文献： [AP13] Alperin-Sheriff J, Peikert C. Practical bootstrapping in quasilinear time[C]//Annual Cryptology Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013: 1-20.[MS18] Micciancio D

在算法导论随笔(一): 操作计数与复杂度Big（O）中，我简单介绍了计算一个算法的时间复杂度的方法。该方法的计算结果虽然都是正确的，但有时不一定特别准确地代表复杂度函数的渐进上界。因此，人们创建了一个分析方式，可以更精确地表示一个复杂度函数的渐进上界。这个分析方式就是我今天要介绍的摊还分析。 1.为什么要引入摊还分析 前文说到，使用分析操作计数的方法来计算时间复杂度时，有的时候求出的渐进上限并

Amortized Analysis 摊还分析考察一个操作序列中所执行的所有操作的平均时间，来评价操作的代价。这个操作序列中也许某一操作的代价很高，但因为还有其他操作，所以这些操作的平均代价并没有那么高。 本文将首先将这种代价分析方式与最坏情况时间复杂度和平均时间复杂度两种方式进行区分，然后通过一篇其他人的博文说明摊还分析的三种方法，并对三种方法进行简要总结，最后对摊还分析方法进行实践。