查找最小和次小元素的比较次数

最小比较次数C = n + ceiling(log2(n)) - 2
具体的方法是：
最小元素
选择floor(n/2) * 2个元素，平均分成两组，进行一对一的比较，比较次数为floor(n/2)，选择较小的一部分，元素个数为ceiling(n/2)。然后对着ceiling(n/2)个元素进行相应的处理，直到剩下最后一个，则可以证明这个元素是最小的。由于每次比较会淘汰1个元素，最后留下一个元素需要淘汰的元素数也就是比较次数，为n-1.
次小元素
在上述过程中记录所有和最小的元素比较过的元素，则总共需要n-1个记录单元。这些元素中必然包括次小的元素，原因是次小的元素必须通过最小的元素才能被淘汰。因此，这也是上述"组比较"的次数。这个次数的上限可以这样考虑：定义C(n) = ceiling(n/2)，并且定义C*(n) = min{k | C...C(k个)(n) = 1}。容易证明C*(n)是个不减函数。对任意n=2^m，C*(n) = m。由于n = 2^(log2(n)) <= 2^ceiling(log2(n))，于是C*(n) <= ceiling(log2(n))。容易证明C*(n) > floor(log2(n))。因此C*(n) = ceiling(log2(n))。在这 ceiling(log2(n))个元素中进行 ceiling(log2(n)) - 1次比较可以得到最小元素。
因此总比较次数为C = n + ceiling(log2(n)) - 2。