1

设 x 为空数组的大小。如果数组变满，将创建一个长度为 k > x 的新数组。旧数组的内容将被复制到新数组中，新元素也将被存储。

  • 在 k 步中创建一个长度为 k 的数组
  • 复制一个元素需要固定的时间。

问题：如何选择 k 使得每个插入操作都有摊销的常数时间，并且插入 n 个元素需要 Θ(n)？通过摊销分析证明您的选择会导致每次插入操作的摊销时间恒定。

我的直觉说 k = 2*n 是个好主意，但我不知道如何证明它。我认为我根本不了解摊销分析。有什么建议么？

4

1 回答 1

0

成倍增长优于持续增长。但无论是增长 2 倍还是 2.1 倍，都没有硬性规定。请查看以下网址了解更多详情。

动态分配数组的理想增长率是多少？

于 2016-04-30T03:59:10.710 回答