动态数组中每次插入操作的平均时间为 a/(a-1)
在关于动态数组的维基百科文章中，它提到（除了关于摊销插入时间的正常部分）：
这个比例的值a[我们增加容量的常数因子]导致时空权衡：每次插入操作的平均时间约为a/(a−1) ，而浪费细胞的数量以 (a−1)n 为界。
我可以看到浪费细胞的 (a-1)n 来自哪里，但有人可以向我解释为什么平均时间是 a/(a-1) 吗？
On the wikipedia article on Dynamic Arrays it mentions (apart from the normal section on amortised insertion time) that:
The value of this proportion a [the constant factor by which we increase the capacity] leads to a time-space tradeoff: the average time per insertion operation is about a/(a−1), while the number of wasted cells is bounded above by (a−1)n.
I can see where the (a-1)n for wasted cells comes from but can anyone explain to me why the average time is a/(a-1)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
设 S 为插入 n 个元素的时间。
因此 a/(a-1) 是插入元素的平均复杂度。
Let S be the time to insert n elements.
Therefore a/(a-1) is the average complexity to insert an element.