The most efficient way to get the largest number from a set of integers

Question

Question: The most efficient way to get the highest number from a set of integers

I recently discussed this issue, I had 2 solutions. 1) Iterate through the collection and search for the highest number (code below) 2) Use the sorting algorithm.

The first method will have an efficiency of O (n)

int getHighestNumber(ArrayList<Integer> list) { if(list != null && list.size() > 0) { if(list.size() == 1) return list.get(0); int maxNum = list.get(0); for(int item:list) { if(item > maxNum) maxNum = item; } return maxNum; } return null; } 

My question is: "Can any sorting algorithm beat it (on the timeline) at any given input, for example, if the collection is already sorted or not?" Is there any other way better than this?

Answer 1

If the collection is already sorted, you can find the largest element in O(1) (assuming Collection supports random access or O(1) access to the end of the Collection containing the largest element - if the largest element is the first, any collections give you O(1) access to it through its Iterator ). In this case, you do not need to sort it.

Any sorting takes at least O(n) when the input is sorted (and at least O(nlog(n)) when it is not), since you cannot verify that the input is sorted without iterating over all the elements. Therefore, sorting algorithms cannot beat your O(n) solution.

Answer 2

Your question suggests his own answer. It depends on the source of the collection itself. That is, the more you know about the dataset, the faster you can come up with heuristics to get the answer you need.

So, if your list is already sorted, list [0] or list [len-1] will be the highest ...

The secondary answer also depends on "How often will the list be viewed?". If this is a one-time search, then simply repeating the list for the highest will be the fastest. If you do this multiple times (for example, collecting various indicators), sorting first using Quick Sort might be best.

Answer 3

There are two ways in your question to find the maximum value of an unsorted list.

Option 1: using the method mentioned in the getHighestNumber question

Option 2: sort the list using the most efficient sorting algorithm around the world, and then take the last value of the list.

So the best option in terms of efficiency.

My answer: Option 1, if the array is not sorted, the sorting algorithm cannot exceed option 1.

Answer 4

With Java 8, you can find max using the Stream API, but this does not solve the O (n) problem. However, access to an element is less computationally expensive than a regular iterator;

 list.stream().mapToInt(i -> i).max().getAsInt(); 

Answer 5

Here is my favorite argument that I always use to quickly judge such a question:

You should use at least O(N) just to view all the items that I / O time.

Without thinking too much, he can convince himself that no algorithms can beat any O(N) algorithms in terms of complexity. Hope this makes sense.