i am trying to figure a algorithm problem that determines the two largest number of the a series of random 10 numbers. Thanks to your help.
algorithm of determines the two largest of a series
-
1well, considering the form of the question, i was :) – 2010-12-26
4 Answers
Just go through the list and keep track of the two largest numbers, that is have two variables that are the the two largest elements so far while going through.
-
2@Debanjan, well there is constant work on each element (update two variables), so O(n), I guess you want to point out that the complexity rises when when we try to find the k largest element, then the complexity becomes O(k*n). However, the numbers where quite explicit here, 2 largest numbers among 10 elements, I guess the problem is that the question doesn't describe which one he wants. – 2010-12-26
list = [random, random, random, ..., random] largest := (list[0] > list[1]) ? list[0] : list[1] secondlargest := (list[0] <= list[1]) ? list[0] : list[1] for each num in list: if num >= largest: secondlargest := largest largest := num elseif num >= secondlargest: secondlargest := num return {largest, secondlargest}
You aren't going to be able to avoid iterating across the entire list because it is not sorted, and therefore you are going to have to search in $O(n)$ time. If the list is sorted, it becomes pretty much a non-problem, but there is no sense in sorting it if all you want is the two largest (if you have to do other things it might be worth it though)
-
0Oh: and why >= instead of > ? You're just making more work for yourself :-) – 2010-12-26
What you are looking for can be solved in $O(n)$.
This is called finding the k-th order statistic.The Wikipedia entry of Selection algorithm provides some insight.But probably a better discussion is presented in Chapter 9, Medians and Other statistics from Introduction to Algorithms, 2nd Ed.
Here is a well described randomized $O(n)$ approach : QuickSelect.
-
1I know but I can make tasks that will TLE any naive algorithm :-), in other cases I would rather do `sort(v.rbegin().v.rend());` then display the `v[0]` and `v[1]` .In some cases say in interviews,most often we are supposed to present $O(n)$ algorithm since that is what that makes this task somewhat interesting. – 2010-12-27
It might be worth noting that the naive way to find the $k$ largest elements requires $O(nk)$ operations, since updating the list of $k$ largest elements could take $O(k)$ operations. However, if these are stored in a heap then we get the better complexity $O(n \log k)$; this method is practical (i.e. actually outperforms the naive algorithm) for moderately sized $k$.
Edit: Debanjan's method shows how to solve this using $O(n + k\log k)$ operations, or $O(n)$ if we're not interested in the relative order of the $k$ largest elements. First you find the $k$th largest element using the classical $O(n)$ algorithm, and then you collect all elements at least as large as it is; if required, you then sort them.
-
1A heap of two elements would be a big pessimisation! – 2010-12-26