推回具有完美平方整数大小的动态大小容器的复杂性成本是多少？

Question

这是在一次考试中出现的，该问题询问了自定义动态大小容器的最坏情况和摊销复杂性成本。容器的大小是下一个完全平方整数，只有在超过其容量时才会改变，因此它可以从 1 到 4、4 到 9、9 到 16、16 到 25…

我假设大小为 n 和 n+1，差异为 (n+1)^2-(n)^2，等于 (2n+1) 并且我认为它的时间复杂度为 O(n)但显然这是假的

Answer 1

对于单个

push_back

来说，最坏的情况显然是在调整大小时。由于分配通常被认为是 O(1)，因此对于 N 个元素，我们只需移动所有 N 个现有元素，因此时间为 O(N)。

要估计摊余复杂度，您需要执行 N=M²

push_back()

并平均时间。将有 √N=M 次重新分配，移动 1²+2²+...+M² = O(M³) 个元素。除以 N 时，平均值将为 O(M) = O(√N)。