一组元素的同时最大值和最小值

Question

在"Intro to algorithm - by CLRS"一书中，Sec-9.1中提到同时最大值&最小的查找可以在运行时间3*层(n/2)内完成。下界也是一样。

我在CLRS的帮助下编写了以下算法，其下界为2*floor(n/2)。[这是错误的——感谢Ricky Bobby]

I m using the variables: 'max' & 'min' to denote maximum & minimum elements, 'i' as indexing variable.
Simultaneous_Maximum_&_Minimum (A, n)  // Array A[1...n]
{
  1. If n is even, compare the first two elements and assign the larger to max and
      smaller to min. Set StartIndex = 3.
  2. If n is odd, set both max & min to the first element. Set StartIndex = 2.
  3. for (i = StartIndex; i <= n; i = i+2 ) {  // Processing elements in pair
         if (max < A[i]) {          // Compare max with A[i]
               if (A[i] < A[i+1])   // Compare max with A[i+1]
                     max = A[i+1];  // we sure that A[i] or A[i+1] can't be min
               else {                 // When max less than A[i] but A[i] not less than A[i+1]
                     max = A[i];        // Set A[i] as max
                     if (min > A[i+1])  // Possible that A[i+1] can be min
                          min = A[i+1]; // if yes, set A[i+1] as min
               }
         }
            // When max is not less than A[i]
         else if (min > A[i]) {        // Compare min with A[i]
                     if (A[i] > A[i+1])  // Compare min with A[i+1]
                           min = A[i+1]; // we sure that A[i] or A[i+1] can't be max
                     else {             // When min is greater than A[i] but A[i] not greater than A[i+1]
                           min = A[i];       // Set A[i] as min
                           if (max < A[i+1]) // Possible that A[i+1] can be max
                                max = A[i+1] // if yes, set A[i+1] as max
                     }
                }                    
         }
         else {  // max > A[i] and min < A[i] -- so A[i] can't be max or min
              if (max < A[i+1])
                  max = A[i+1]
              if (min > A[i+1])
                  min = A[i+1] 
         }
     }
}

感谢Ricky Bobby指出我的错误——我们无法找到同时最大值&

Answer 1

如果我错了请告诉我，但你不是在看情况:max>A[i]>min

if max>A[i]>min :
   if A[i+1] > max 
       max =A[i+1]
   if A[i+1] <min 
       min = A[i+1]

所以你的算法在一般情况下是错误的。

在递减顺序或递增顺序中可能有效，但它非常无用，因为对于排序列表，您可以使用此表达式找到最小和最大:

(min,max) = (A[0],A[n]).sort()

so in O(get(A[0]) + get(A[n]))

Answer 2

我认为如果对数组进行排序，可以在数组[0]处找到最小值，在数组[n-1]处找到最大值。