改进查找数组中的最小值和最大值

Question

我的老师教我快速排序算法，其成本约为 O(n)。在运行那种排序之前，我必须找出数组中哪些元素是最大的和最小的。

这是我的解决方案：

//n is a size of array a[]
for(int i = 0; i < n ; i++){
  if (_max < a[i]) _max = a[i];
  if (_min > a[i]) _min = a[i];
}

令 f(n) 是该 for 循环中的多个条件运算符（比较变量 i 除外）。所以费用：

n 次比较 _max 与 a[i]
n 比较 _min 与 a[i] 的时间

所以，f(n) = 2n。

我朋友写了这样一段代码：

for(int i = 0; i < n-1; i+=2)
  if (a[i] < a[i+1]){
    if (_max < a[i+1]) _max = a[i+1];
    if (_min > a[i]) _min = a[i];
  }
  else{
    if (_max < a[i]) _max = a[i];
      if (_min > a[i+1]) _min = a[i+1];
  }
// Compare one more time if n is odd
if (n % 2 == 1){
  if (_min > a[n-1]) _min = a[n-1];
  if (_max < a[n-1]) _max = a[n-1];
}

我们很容易得到f'(n) = 3n/2 + 3。似乎当n足够大时f'(n) < f(n)。

但是老师要求f(n) = n or f(n) = n + a, a是const

有什么想法吗？

Answer 1

当n很大时，f'(n) = f(n)，因为两者都是O(n)的时间复杂度。

不过，貌似你只需要求一次min和max，所以你的算法时间复杂度O(n)是可以的，因为Flash Sort也是O(n)的，所以总的时间复杂度是由 O(n) 支配。

换句话说：

OverallTime = FindMinMax + FlashSort
OverallTime = O(n) + O(n)
OverallTime = 2*O(n)
OverallTime = O(n)

即使 FindMinMax 更快，Flash Sort 的第二项仍然会支配整体时间复杂度。

如果您必须更快地做到这一点，您可以构建一个名为 Segment Tree 的数据结构，其中：

uses O(n log n) storage and can be built in O(n log n) time. Segment trees support searching for all the intervals that contain a query point in O(log n + k), k being the number of retrieved intervals or segments.

Answer 2

没有。不可能在恰好 n（或 n+a）次比较中同时找到最大值和最小值。它至少需要 3n/2 - 2 次比较。参见 this proof and this proof。也许你可以把这些证明拿给你的老师看...

关于序列还有其他提示吗？比如均匀分布之类的？

改进查找数组中的最小值和最大值

Improving finding Min and Max in Array

sorting

algorithm

max

min