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

Question

我的老师教我 Flash 排序算法，其成本大约为 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。

我的 friend 写了这样一段代码:

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 或 f(n) = n + a，其中 a 是一个常量。

有什么想法吗？

Answer 1

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

关于序列还有其他提示吗？是均匀分布的还是这样的？