因此，当每次添加元素时动态数组的大小都加倍时，我理解扩展的时间复杂度是 O(n( n 是元素。如果将数组复制并移动到一个在已满时仅大 1 大小的新数组，该怎么办？(而不是加倍(当我们按某个常数 C 调整大小时，时间复杂度总是 O(n(？
如果你增长一些固定的常数 C，那么不，运行时不会是 O(n(。 相反，它将是 Θ(n2(。
要看到这一点，请考虑一下如果执行一系列 C 连续操作会发生什么。 在这些操作中，其中 C-1 将花费时间 O(1(，因为空间已经存在。 最后一个操作将花费时间 O(n(，因为它需要重新分配数组、添加空间并复制所有内容。 因此，任何 C 操作序列都将花费时间 O(n + c(。
因此，现在考虑一下如果执行一系列 n 个操作会发生什么。 将这些操作分解为大小为 C 的块;将有其中的n/C。 执行这些操作所需的总工时将是
(c + c( + (2c + c( + (3c + c( +... + (n + c(
= cn/c + (c +2c + 3c + ... + nc/c(
= n + c(1 + 2 + 3 + ... + n/c(
= n + c(n/c((n/c + 1(/2
= n + n(n/c + 1(/2
= n + n 2/c + n/2
= Θ(n2(
与此形成对比的是，当您需要更多空间时将数组大小加倍时：完成的总工作量为
1 + 2 + 4 + 8 + 16 + 32 + ... + n
= 1 + 2 +4 + 8 + ... + 2log n
= 2log n + 1 - 1
= 2n - 1
= Θ(n(
移植自 SO 文档。
2 的幂和 — 1 + 2 + 4 + 8 + 16 + ...
总和
2 0 + 2 1 + 2 2+ ... +2n-1
简化为 2n - 1。这就解释了为什么可以存储在无符号 32 位整数中的最大值是 232 - 1。