列表中最大和最小的元素

Question

找到n个不同元素的未排序列表的最大和最小元素所需的最小比较次数是多少？

上述算法的最佳时间复杂度是多少？

从最小数量的比较,我打算指定最有效的算法,在最坏的情况下.

Answer 1

最优算法需要3/2*n比较.

它的工作原理如下:

5 2 6 7 3 1 10 35 4 6

1. [5] [6]
   
2. [5,2],[6,4]
   
3. [5,2,6],[6,4,35]
   
4. [5,2,6,7],[6,4,35,10]
   
5. [5,2,6,7,1],[6,4,35,10,3]
   

在每个步骤(n/2)步骤中,您比较第i个和第ni个元素并移动到表"更大"和"更低"

在n/2步之后,您知道,最小值在"较低"表中,最大值在"较大"表中.这两个表中的最小和最大值是(n/2)*2,所以你有(3/2)*n

Answer 2

它是N*(3/2).

Answer 3

下限(从记忆重建;不确定引用应该是什么)

这是一个对手,当n为偶数时强制(3/2)n - 2比较,当n为奇数时强制(3/2)n - 3/2比较.当仔细分析时,Marcin描述的算法实现了这些界限.

每个元素处于以下四种状态之一:( {min, max}从未进行过比较,因此可以是最小值或最大值),{min}(从未大于另一个元素,因此可以是最小值但不是最大值),{max}(从未小于另一个元素) ,可以是最大值但不是最大值,{}(大于另一个元素,小于另一个元素,既不是最小值也不是最大值),其中"可以......"表示存在与到目前为止算法执行的比较......保持不变.

设T是e状态基数元素e的总和.开始时,T = 2 n.最后,T = 2,否则最小值或最大值不是唯一确定的.以下对手确保每次比较时T减少最多2,并且除非首次比较两个元素,否则最多为1.所述界限如下.

对手必须防止T减少太快,同时保留至少一个一致的总顺序.对手如何确定比较结果？如果两个元素都不处于状态{min, max},那么我们就很容易了.任一状态不同,在这种情况下,我们根据解决{min}< {}< {max},和T保持不变; 或者它们是相同的,我们给出一个任意一致的答案,并且T减少1.我们通过矛盾来证明一致性是保持的.假设最近的比较创建了一个循环.循环中的所有元素现在必须处于状态{},这只有在两者都处于先前状态时才有可能{}.这与我们对同一州的元素一致回答的策略相矛盾.

否则,被比较的元素中的至少一个处于状态{min, max}.如果另一个处于状态{min},那么{min}< {min, max}.如果另一个处于状态{max},那么{min, max}< {max}.否则,任意解决.很明显,当且仅当比较是在两个{min, max}元素之间时,T减少2 .此比较不会创建循环,因为状态中的元素在{min, max}比较图中具有阶数1.