我正在使用堆栈的数组实现，如果堆栈已满而不是抛出错误，我将数组大小加倍，复制元素，更改堆栈引用并将新元素添加到堆栈中。（我正在按照一本书自学这些东西）。
我不完全明白的是为什么要加倍，为什么不按固定数量增加，为什么不增加3倍。
我认为这与时间复杂度有关吗？
一个解释将不胜感激！
问问题
1871 次
4 回答
3
加倍刚刚成为诸如数组列表（“动态”大小的数组，实际上只是在后台执行您正在执行的操作）和由数组支持的最动态大小的数据类型之类的通用实现的标准。如果您知道您的场景并且有时间和意志力来编写自定义堆栈/数组列表实现，那么您当然可以编写一个更优化的解决方案。
如果您在软件中知道在构建初始数组后很少会添加项目，则可以使用特定大小对其进行初始化，然后仅将其增加为保留内存的添加内容的大小。
另一方面，如果您知道列表会非常频繁地扩展，您可能会选择在空间不足时将列表大小增加 3 倍或更多。
对于作为公共库一部分的通用实现，您的实现细节和要求是未知的，因此加倍只是一个快乐的媒介。
于 2012-05-02T18:10:53.193 回答
3
从理论上讲，您确实达到了不同的时间复杂度。如果你增加一个常数大小，你将重新分配的数量（因此 O(n) 个副本）除以一个常数，但你仍然会得到 O(n) 的附加时间复杂度。如果将它们加倍，则追加的时间复杂度会更高（平均化 O(1) IIRC），并且由于最多消耗两倍于所需的内存，因此空间复杂度仍然相同。
在实践中，它不那么严重，但仍然可行。副本很昂贵，而一些内存通常不会受到伤害。这是一个折衷方案，但您必须非常低的内存才能选择另一种策略。通常，您事先不知道（或由于 API 限制而无法让堆栈知道）您实际需要多少空间。例如，如果你从一个元素开始构建一个 1024 个元素的堆栈，你会从 1024/K 开始（我可能会偏离一个）10 次重新分配——假设 K=3，这大约是 34 倍许多重新分配，只是为了节省一点内存。
任何其他因素也是如此。2 很好，因为你永远不会得到非整数大小，而且它仍然很小，将浪费的空间限制在 50%。其他因素可能会更好地服务于特定用例，但通常投资回报率太小，无法证明重新实现和优化某些库中已有的内容是合理的。
于 2012-05-02T18:14:51.907 回答
1
固定数量的问题在于选择该固定数量 - 如果您（例如）选择 100 个项目作为您的固定数量，那么如果您的堆栈当前大小约为 100 个项目，这是有道理的。但是，如果您的堆栈已经有 10,000 个项目，它可能会增长到 11,000 个项目。您不想进行 10 次重新分配/移动以将堆栈大小增加 10%。
至于 2x 与 3x，那是相当随意的——选择 3x 没有错；哪个“更好”取决于您的确切用例以及您如何定义“更好”。
于 2012-05-02T18:10:12.973 回答
0
按 2 倍缩放很容易，并且将确保平均复制项目不超过两次 [扩展将第一次复制一半的项目，第二次复制四分之一，第三次复制八分之一，等等。] 如果事情相反增长了一个固定的数量，然后当例如执行第二十次扩展时，将有一半的项目将被复制第十次。
增长超过 2 倍将增加平均“永久”闲置空间；以较小的因子增长将增加分配和放弃的存储量。根据永久分配和放弃分配的相对感知“成本”，最佳增长因子可能更大或更小，但任何接近最佳的增长因子通常不会比最佳增长因子表现得差太多。无论最佳增长因子是多少，2 倍的增长因子都将足够接近以产生良好的性能。
于 2014-06-08T20:19:35.950 回答