algorithm - 使用最多 3/2n 次比较查找数组中两个元素之间的最大差异

Question

这个问题在这里已经有了答案:





How to find max. and min. in array using minimum comparisons?

(14 个回答)


8 个月前关闭。




我正在处理给定一个带有整数元素的未排序数组，

A={a_1,a_2,...,a_n}

找到数组中两个元素之间的最大差异( max|a_i-a_j|)，在最坏的情况下最多使用 3/2n 比较。(运行时间无关紧要，我们不能使用诸如 max 或 min 之类的操作)。
我真的怀疑这是否可能:要找到两个元素的最大差异，在最坏的情况下，我们不应该总是需要大约 2n比较，因为我们需要使用大约 n 次比较来找到数组的最大元素，再使用 n 次比较来找到数组的最小元素？我不知道在哪里可以减少操作。
我也考虑过分而治之。假设我将这个数组分成 2 个长度为 n/2 的子数组，但后来我遇到了同样的问题，在每个子数组中找到最大值和最小值，大约需要 n比较所以会有 2n总比较。
将非常感谢有关如何执行此操作的提示。

Answer 1

cppreference 提出了一个实现 std::minmax_element 的例子复杂度为 3/2 n。基本思想是通过2个元素处理2个元素。

If A[i+1] > A[i]
    A[i+1] is compared with Max
    A[i] is compared with Min
Else
    A[i] is compared with Max
    A[i+1] is compared with Min
    

考虑了 2 个元素，3 次比较 -> 复杂性 O(3/2 n)注意:在 n是奇数，最后一个元素必须单独考虑。