我们知道找到列表中最小的数的简单方法就是n次比较，如果我们想要第二个最小的数，我们可以再遍历一次，或者在第一次迭代中跟踪另一个变量。无论哪种方法，都需要进行2n次比较才能找到两个数字。
假设我有一个包含n个不同元素的列表，我想找出最小的和第二小的元素。是的，最优算法最多需要n + ceiling(lgn) - 2次比较。(但对最佳方式不感兴趣)
但是假设你被迫使用简单的算法，需要进行2n次比较的算法。在最坏的情况下，需要进行2n次比较。但是平均数是多少呢?使用简单的蛮力算法找到最小和第二小的平均比较次数是多少?
编辑:它必须小于2n——(从我下面的评论中复制和粘贴)我将我所处的索引与tmp2变量进行比较，以跟踪第二小。除非当前索引处的值小于tmp2，否则我不需要再与跟踪最小值的tmp1变量进行比较。所以你可以减少比较的次数从2n。但它仍然需要多于n。是的，在最坏的情况下，这仍然需要进行2n次比较。但平均而言，如果所有东西都随机放入…
我猜应该是n +一些比较，但我不知道第二部分是什么。我想肯定会有某种方式涉及到log n，但有什么办法证明吗?
同事在午餐时问我这个问题，我被难住了。抱歉)再一次，我对最优算法不感兴趣，因为这是常识。正如您在评论中指出的那样，如果迭代中的当前元素大于迄今为止找到的第二小元素，则不需要进行第二次比较。如果我们看第k个元素，第二次比较的概率是多少?
我认为这可以改写为"第k个元素在包含前k个元素中最小的2个元素的子集中的概率是多少?"对于均匀分布的元素，这应该是2/k，因为如果我们把前k个元素看作一个有序列表，每个位置对于第k个元素的概率都是1/k，但是只有两个位置，最小和第二小的位置，会引起第二次比较。所以第二次比较的次数应该是sum_k=1^n (2/k) = 2h_n (n次谐波数)这实际上是对第二次比较的期望值的计算，其中随机数表示必须进行第二次比较的事件，如果必须进行第二次比较，则为1，如果只进行一次比较，则为0。
如果这是正确的，在平均情况下，总的比较次数是C(n) = n + 2 H_n和afaik H_n = theta(log(n))， C(n) = theta(n + log(n)) = theta(n)