How do you find the maximum of n numbers?

It’s easy to imagine that you could do it in a loop.

int find_max(int arr[n]){

int max = -infinite;

for(int i=0; i<n; i++)

if(arr[i]>max)

max=arr[i];

return max;

}

Here, n-1 comparisons are required.

How do I find the maximum and minimum of n numbers?

It’s easy to imagine that a loop to find a maximum and a minimum would do the trick.

(int, int) find_max_min(int arr[n]){

int max = -infinite;

int min = infinite;

for(int i=0; i<n; i++){

if(arr[i]>max)

max=arr[i];

if(arr[i]<min)

min=arr[i];

}

return (max, min);

}

Here, we need to perform 2 times (n-1)=2n-2 comparisons.

Is there a faster way?

Divide-and-conquer might come in handy, and the idea is:

(1) break large-scale into small-scale;

(2) Small-scale solutions;

(3) After small-scale solution, large-scale solution is integrated;

See if you can apply it to this example:

(1) Divide ARR [0,n] into ARR [0,n/2] and ARR [N /2,n];

(2) The maximum and minimum values of each subarray are solved respectively;

(3) Taking the maximum value from the maximum value of the two subarrays and the minimum value from the minimum value of the two subarrays is the final solution;

The pseudocode looks something like this:

(int, int) find_max_min(int arr[0,n]){

// The left half of the recursion

(max1, min1) = find_max_min(arr[0, n/2]);

// Recurse to the right half

(max2, min2) = find_max_min(arr[n/2, n]);

// Count twice

max = max1>max2? max1:max2;

min = min1<min2? min1:min2;

return (max, min);

}

Voiceover, actual recursive code to note:

(1) The input parameters are not 0 and n, but the lower and upper limits of the array;

(2) Recursion to convergence, when the difference between the upper and lower limits of the array is 1, only a comparison, directly return Max and min, without recursion again;

What’s the time complexity after divide-and-conquer?

If you are a regular reader of “The Architect’s Path”, the article “Getting All the Time Complexity Calculations done”, can easily solve the divide-and-conquer time complexity analysis:

  • When there are only two elements, it only takes one calculation to figure out the maximum and minimum

  • When I have n elements,

(1) Recursive left half region;

(2) Recursive right half region;

(3) Perform two more calculations;

f(2)=1; [Equation A]

f(n)=2*f(n/2)+2; [Equation B]

Solve the recursive formula, and get:

F (n) = 1.5 n – 2;

Voiceover, the proof process is as follows:

[Equation B] Can be obtained by continuous expansion:

f(n)=2*f(n/2)+2; [Formula 1]

f(n/2)=2*f(n/4)+2; [Equation 2]

f(n/4)=2*f(n/8)+2; [Equation 3]

.

f(n/2^(m-1))=2*f(2^m)+2; [Equation M]

Through continuous substitution of these M expressions, we get:

f(n)=(2^m)*f(n/2^m)+2^(m+1)-2; [Equation C]

F (2)=1;

When n/2^m=2, f(n/2^m)= 1;

So n is equal to 2 to the m plus 1.

That is, f(n)=n/2 + n-2 = 1.5n-2;

The proof is rigorous, but I know you don’t get it.

It is recommended to read again.All the time complexity calculations are done”__.

In summary, n numbers:

  • To get the maximum, to traverse, it takes n minus 1 calculations

  • It takes 2n minus 2 computations to get the maximum and minimum, to traverse

  • Max and min, divide and conquer, time 1.5n minus 2

Voice-over: Don’t jump out, there’s homework at the end.

Thinking is more important than conclusion, I hope you have a harvest.

The Architect’s Path – Share practical technical articles

Problem set, n numbers:

(1) Is it the fastest way to get the maximum, n minus one calculation?

(2) Is it the fastest way to find the maximum and minimum value, 1.5n-2?