-2
$\begingroup$

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.

  • 1
    well, considering the form of the question, i was :)2010-12-26

4 Answers 4

5

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
4
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)

  • 0
    Oh: and why >= instead of > ? You're just making more work for yourself :-)2010-12-26
2

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.

  • 1
    I 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
1

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.

  • 1
    A heap of two elements would be a big pessimisation!2010-12-26