【习题解答】 平摊分析

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ## 18.1 ### (1) 首先所有元素都要进栈一次，而出栈的元素，都是因为不满足海景房的条件，那么现在问题就从证明返回的栈中的元素就是所有海景房，变成证明，返回的栈中的每个元素都是海景房，也就是说都比自己东边的元素高。

那么我们找的循环不变式就是，每次外循环第次结束时，栈中元素从栈底到栈顶高度递减，且每个元素都比的所有元素高，只要证明了这个不变式，那么取循环结束时的情况，就证得了原命题。

这个不变式的证明用类似于数学归纳法的思想，但是为有穷步的归纳推理： + 起始情况：栈中只有一个元素，显然成立$ + 归纳推理：假设第次循环结束，栈中元素递减，且栈中的任意元素比的元素都高，那么对于下一次循环k+1，如果大于栈顶则把栈顶弹出，然后再把压入栈顶，这保证了第次循环结束时，栈中元素从底到顶是递减的；同时由栈顶是栈中最小的元素，这保证了栈顶的进入后，依然有栈中任意元素比大。 + 故循环不变式得证

故原命题得证。

###(2) 由于每个元素都进行了且只进行了一次，故算法一共进行了次，而的次数必然不超过的次数，故算法复杂度为

18.3

为了更好地理解题目，我们这样思考： + 把集合合并问题的这个过程，转化为二进制串的自增过程，例如自增后变成 + 自增的开销，按题干的要求，则取决于以多少个1结尾，例如自增后变成，开销是 + 对于个结尾的二进制串，自增的开销是 + 考虑二进制串从的过程(个)，自增次 + 以个结尾的串()的自增发生了次，以个1结尾的串，自增发生了一次，即最后一次。 + 故整个过程的开销是 + 故自增次(插入元素次)时，整个过程开销是，平摊到单次的开销是

以上思路站在二进制串的自增的角度考虑的，也可以站在集合合并的角度考虑，假设插入元素n次 + 创建大小为的新集合次，每次的开销是 + 合并两个大小为的集合次，每次开销是 + 合并两个大小为的集合，每次开销是 + 合并两个大小为的集合，每次开销是 + 故总开销是 + 平摊到单次的开销是

18.5

• 实现的结构可以是数组
• ：直接把放到数组末尾，开销是
• ：先找到第大的元素，然后再遍历一遍保留比该元素小的即可，开销是线性的，不妨设开销不超过，是常数
• 那么对于，我们除了计算大小为的开销以外，再额外计算大小为的开销，这个开销是相当于为将来攒的(记账开销)，等到将来操作删除了个元素后，就能用此大小为的攒的记账开销来作为需要的实际开销。
• 因此，可以认为的开销是，开销是0，平摊代价是常数级别