1.4.32 #

解答 #

首先，不需要扩容数组的的操作都只需访问数组一次，$M$ 次操作就是 $M$ 次访问。

随后我们有性质， $M$ 次栈操作后额外复制访问数组的次数小于 $2M$。

这里简单证明，设 $M$ 次操作之后栈的大小为 $n$，那么额外访问数组的次数为：

$S = \frac{n}{2} + \frac{n}{4} + \frac{n}{8} +…+ 2 < n$

为了能使栈大小达到 $n$，$M$ 必须大于等于 $\frac{n}{2}$

因此 $2M \ge n > S$，得证。

因此我们可以得到 $M$ 次操作后访问数组次数的总和 $S’ = S + M < 3M$。