1.4.32

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

首先,不需要扩容数组的的操作都只需访问数组一次,$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$。

上一题 下一题