这里解析均摊复杂度的计算过程不太对！

这里每次数组扩容，是每次扩容两倍，也就是 2n，4n，8n, 16n这种，按照上图的计算逻辑，我们假设进行4n+1次操作，实际触发了3次resize(第n+1, 2n+1,4n+1) 总共进行了 n+2n+4n+(4n+1)=11n +平均，每次就是2.75 ,而且随着次数的增加，会一直增加，复杂度符合nlogn。

武当王也 2021-12-27

源自：数据结构基础：动态数组，栈和队列 1-10 均摊复杂度和防止复杂度的震荡

收起

1回答

liuyubobobo 回答被采纳获得+3积分 2021-12-28 02:25:51

如果做累计计算，这个上界是 3.

我们以最坏情况为例，假设执行到 2^k·n + 1 个 add 操作。那么，执行的 resize 操作数是 (n + 2n + 4n + ... + 2^k·n)

所以，总操作数是： (n + 2n + 4n + ... + 2^k·n) + (2^k·n + 1)

这个式子的前半部分，是小于 2 * 2^k·n 的。

(1 + 2 + 4 < 8, 1 + 2 + 4 + 8 < 16，能看出来你数学底子不错，这个结论我不证明了，实际上，课程后续讲 segment tree 一类的结构时会使用这个结论，这个结论也是很多搜索算法的基础，比如迭代加深搜索。)

所以，上面这个总操作数的式子的“上界”是：2 * 2^k·n + (2^k·n + 1) = 3 * 2^k·n + 1

而我们执行了 2^k·n + 1 个 add 操作。所以 (3 * 2^k·n + 1) / (2^k·n + 1) = O(3) = O(1)

===========

调和级数和的算法可以推出一个 logn，但这里没有调和级数，而是一个几何级数。

继续加油！：）

收起回答

武当王也提问者 #1

我用等比数列来验证这个逻辑，跟老师的一致，感谢老师的深夜解惑：）

最坏的情况：执行到 2^k*n + 1个addLast操作，执行resize的数量是(n, 2n, 4n ...2^k*n)
总的操作数（n+2n+4n+...2^k*n) + (2^k*n + 1)
等比公式
Sn = a1* (1-q^n)/(1-q) 其中 a1为首项，q为等比值，n为相加的数据个数
q*Sn = a1*q + a2 * q + a3*q + ... an*q=a2 + a3 +..+ a(n+1)
Sn - q*Sn = (a1 + a2 + ... an) - (a2 + a3 +..+ a(n+1)) = a1 - a(n+1)
Sn(1-q) = a1(1-q^n)
Sn = a1*(1-q^n)/(1-q)
套上去
n(1+2+4+...2^k) + (2^k*n + 1)
=2^(k+1)*n -n + (2^k*n + 1) = 3*2^k*n -n + 1
上面就是总的操作次数，addLast操作为2^k*n +1 当k足够大的时候，可以忽略n的影响所以复杂度为 O(3) = O(1)

2021-12-28 10:30:40
liuyubobobo 回复提问者武当王也 #2

赞！使用等比数列求和公式就可以轻松得到 n + 2n + 4n + ... + 2^k·n < 2 * 2^k·n 这个结论：）继续加油！：）

2021-12-28 12:38:38