一组元素中的同时最大值和最小值
问题描述:
在Sec-9.1中提到的书“Intro to algorithm-by CLRS”中,可以在运行时间3 * floor(n/2)中同时执行最大值&最小查找。同样也是下界。一组元素中的同时最大值和最小值
我写了下面的算法(从CLRS获得帮助),它的下界是2 * floor(n/2)。 [这是错误的---由于瑞奇·鲍比]
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]
}
}
}
感谢瑞奇·鲍比指出我的错误 - 我们不能做2查找同时最大&最小*地板(N/2)运行时间。
答
告诉我,如果我错了,但你不看情况:最大> A [1]>分钟
if max>A[i]>min :
if A[i+1] > max
max =A[i+1]
if A[i+1] <min
min = A[i+1]
那么你的算法是错误的一般情况。
降序或升序它可能工作,但它是相当无用的,因为对于一个排序列表,你可以找到的最小值和最大值此espression:
(min,max) = (A[0],A[n]).sort()
所以在O(获得(A [0 ])+ get(A [n]))
答
如果数组已排序,则可以在数组[0]处找到最小值,并在数组[n-1]处找到最小值。或者反过来降序排列。
我绝对没错。我错过了检查。所以我必须添加这个检查。因此该算法将进行3 * floor(n/2)比较。非常感谢你纠正我。 – Dibyendu
很高兴我能帮上忙 –