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

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。

我的朋友写了这样的代码：

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 是一个常数。

有什么好的想法吗？

- Le Duong Tuan Anh

---

你的解决方案可以通过在第一个if语句中使用else来稍微加快速度。但主要要学习O-符号表示法，它告诉你忽略常数因素，请参见https://dev59.com/-HRB5IYBdhLWcg3w3K0J。 - Gerriet

@Gerriet，你能详细描述一下吗？我的老师想要计算for循环中的操作次数，而不仅仅是大O:D - Le Duong Tuan Anh

阅读我在第一条评论中放置的链接，也许考虑找一位更好的老师... - Gerriet

此外，在这个链接中https://stackoverflow.com/questions/16764207/find-both-min-and-max-together-algorithm-should-be-faster-but-isnt，两种变体都有更详细的讨论。 - Gerriet

嗯...我认为运行时间在这里并不重要。我的老师只想要减少for循环中的操作次数，以找到最小值和最大值。换句话说，有没有一种解决方案可以使用1个for循环包括1个if-else语句来找出最小值和最大值？ - Le Duong Tuan Anh

Answer 1

不。在恰好n（或n+a）次比较中找到最大值和最小值是不可能的。至少需要3n/2 - 2次比较。请参见 this proof 和 this proof。也许你可以向老师展示这些证明......

有关该序列的其他提示吗？比如说它是否均匀分布等？

- TsReaper

---

这是关于编程的内容，请将其翻译成中文。请仅返回已翻译的文本：没有任何关于顺序的提示。这就是我要找的！非常感谢！ - Le Duong Tuan Anh

Answer 2

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

然而，似乎你需要找到最小值和最大值一次，所以你的算法时间复杂度为 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的第二项仍将主导总时间复杂度。

---

如果你必须更快地完成这个任务，你可以构建一个数据结构，称为线段树，它：

使用O(n log n)的存储空间，并且可以在O(n log n)的时间内构建。线段树支持在O(log n + k)的时间内搜索包含查询点的所有区间或段，其中k是检索到的区间或段的数量。

- gsamaras

---

在这个部分，我的老师不关心大O的时间复杂度。他要求我们改进 for 循环来查找数组中的最小和最大元素。换句话说，我只需要减少 f(n)。 - Le Duong Tuan Anh