我们知道找到列表的最小数字的简单方法是进行 n 次比较，如果我们想要第二小的数字，我们可以再次遍历它，或者在第一次迭代期间跟踪另一个变量。无论哪种方式，这都需要 2n 次比较才能找到这两个数字。
所以假设我有一个包含 n 个不同元素的列表，我想找到最小的和第二小的。是的，最优算法最多需要 n + ceiling(lg n) - 2 次比较。（虽然对最佳方式不感兴趣）
但是假设您被迫使用简单算法，即进行 2n 次比较的算法。在最坏的情况下，需要进行 2n 次比较。但是平均值呢？使用简单的蛮力算法找到最小的和第二小的平均比较次数是多少？
编辑：它必须小于 2n——（从我下面的评论中复制并粘贴）我将我所在的索引与 tmp2 变量进行比较，以跟踪第二个最小的变量。除非我当前索引处的值小于 tmp2，否则我不需要对 tmp1 变量进行另一个比较来跟踪最小值。因此，您可以从 2n 减少比较次数。尽管如此，它仍然需要超过 n 。是的，在最坏的情况下，这仍然需要 2n 次比较。但平均而言，如果所有东西都是随机放入的......
我猜这将是 n + something 比较，但我无法弄清楚第二部分。我想会有某种方式以某种方式涉及 log n ，但是关于如何证明这一点的任何想法？
（同事在午餐时问我这个问题，我被难住了。抱歉）再一次，我对最优算法不感兴趣，因为那是一种常识。