algorithm - 列表的最大和最小元素

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 个和第 n 个元素并移动到表“更大”和“更低”

在 n/2 步之后，您知道，最小值在“较低”表中，最大值在“较大”表中。在这两个表中找到 min 和 max 是 (n/2) * 2，所以你有 (3/2) * n