阵列中求最小值和最大值的改进

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除外).因此，它的成本：

• 比较_max和ai的时间
• 比较_min和ai的时间

因此，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是const。

有什么想法吗？

Answer 1

不是的。在精确的n(或n+a)比较中不可能同时找到最大值和最小值。它至少需要3n/2-2的比较。见这个证据和这个证据。也许你可以把这些证据给你的老师看..。

关于这个序列还有什么其他的暗示吗？好像是均匀分布的？

Answer 2

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

然而，似乎您需要找到最小和最大一次，所以您的算法的时间复杂度O(n)是好的，因为Flash排序成本O(n)也是如此，因此整个时间复杂度将由O(n)主导。

换言之：

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

即使FindMinMax速度更快，Flash的第二个术语，仍然会在整个时间复杂度中占据的主导地位。

如果您必须更快地这样做，您可以构建一个名为段树的数据结构，它：

使用O(n log n)存储，可以在O(n log n)时间内生成。段树支持搜索O(log + k)中包含查询点的所有间隔，k是检索到的间隔或段的数目。