Improved search for Min and Max in an array
my teacher taught me Flash Sort Algorithms, which costs about O (n). Before running this view, I have to figure out which elements are the maximum and minimum in the array.
This is my decision:
//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];
}
Let f (n) be the number of the conditional statement in this for-loop (excluding the comparison of variable i). So it's worth it:
- n time to compare _max with [i]
- n time to compare _min with [i]
So f (n) = 2n.
My friend wrote code like this:
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];
}
It is easy to get f '(n) = 3n / 2 + 3. It seems like f' (n) f (n) when n is big enough.
But my teacher requires that f (n) = n or f (n) = n + a, a - const.
Any ideas?
source to share
Not. There is no way to find the maximum and minimum value in an exact comparison of n (or n + a). This will require at least 3n / 2 - 2 comparisons. See this proof and this proof . Perhaps you can show this evidence to your teacher ...
Are there any other hints of consistency? How is it evenly distributed or like that?
source to share
When n
large, f '(n) = f (n), since both have O (n) time complexity.
However, you feel like you need to find min and max once, so your algorithm with O (n) time complexity is fine, since Flash Sort costs O (n), so the total time complexity will be O (n).
In other words:
OverallTime = FindMinMax + FlashSort
OverallTime = O(n) + O(n)
OverallTime = 2*O(n)
OverallTime = O(n)
Even if FindMinMax was faster, the second term Flash Sort will continue to dominate the total time.
If you must do it faster, you can create a data structure called Segment Tree that:
uses O (n log n) memory and can be built in O (n log n) time. segment trees support searching for all intervals containing the query point in O (log n + k), k is the number of received intervals or segments.
source to share