如何证明在最坏情况下，找到 n 个元素中第二小的元素需要 n + lgn - 2 次比较

Question

问题是如何证明在最坏情况下，找到 n 个元素中第二小的元素需要 n + lgn - 2 次比较。

我思考了很久，还是看了网上的答案 Answer in page 6 / 8，有一点启发，但是具体有几个地方不明白

Answer in page 6 / 8

1. We select a winner in n−1 matches. 这个是为什么呢，能不能在仔细解释下？

2.At this point, we know that the second smallest element is one of the lg n elements
lgn是怎么来的呢？

3.In another lgn − 1 comparisons we can find the smallest element out of those. 这个又是为什么，为什么是lgn − 1 次比较？

4.The list has lgn elements? 为什么呢？

Answer 1

1. 找最小值当然只需要 n-1 次比较

2. 应该是 log₂n

3. 考虑左树的全部元素都比右树小的情况

Answer 2

就是锦标赛的每个节点存储的不仅仅是一个数字，还连带有所有这个数字的“手下败将”。每次比较得到winner的同时，把这次的loser加入晋级winner的loser list。那么第二名就是在总冠军的loser list里面矬子拔将军就好了。矬子有ceil(lg n)个。