我是摊销分析的新手。我注意到，动态数组的常见做法是在空间不足时将其大小加倍。我们选择加倍尺寸是否有特定原因？为什么不三重或四重？对于使用摊余分析加倍的选择是否有具体解释？还是选择是任意的？
通过按任何常数因子进行缩放来增大数组大小将足以使运行时为O（n）。要看到这一点，请注意，如果最终数组的大小最终为n，并且在每个步骤中我们将比例缩放为m，那么完成数组增长的总工作量将为
1 + m + m 2 + ... + m 1 + log m n。
要了解为什么会这样，请注意（如果数组从大小1开始），则数组将以大小1，m，m 2 ... ...增长，直到达到大小n。最后一个增长步骤在m k = n时发生，而在k = log m n时发生。考虑到另外一个增长步骤来超调n个，因此这里的+1。
上面的总和是一个几何级数的总和
（m 2 + log m n -1）/（m-1）
=（m 2 n-1）/（m-1）
≤n·（m 2 /（m-1））
因此，基本上任何大于1的指数都起作用，但是前导系数取决于我们选择m的方式。对于大的m，该系数大约等于m，我们最终浪费了大量的精力和空间来增加阵列。如果m接近于1，分母将变得越来越大，并且越来越令人担忧。
选取m = 2可获得4的超前系数，该系数非常低。选择1.5可得出4.5的超前系数。那是更高的，但不是很多。但是，选择1.5还有其他一些优点：
size + (size >> 1)与乘法相比，在处理器上非常便宜。希望这可以帮助！
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句