1.4.32

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$。