-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
    You said a 'series' not a sequence or a list. Are there any known properties of this series?2010-12-26
  • 1
    If you mean `series`,please state whether we can assume that it have some specific properties,if it is sequence then change the question accordingly.2010-12-26
  • 2
    does the algorithm need to perform in a specific way? Does it need to be < O(n lg n)? If not, just sort it the list and pick the last 2 elements.2010-12-26
  • 0
    @Sev: you're joking, right? Tell me you're joking...2010-12-26
  • 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.

  • 0
    And what would be the complexity for this approach ?2010-12-26
  • 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
    If you're worried about running time, why don't you check the second condition first? If it fails, you can skip the first condition.2010-12-26
  • 0
    @TonyK: Because if the number you are checking is larger than the largest it will by definition be larger than the second largest. So say the `largest` is $10$ and the `secondlargest` is $9$, if you check against $11$ and do the second check first you would have `largest` as $10$ and `secondlargest` as $11$. Therefore to make it work properly, you would have to do another check within that one, which would defeat the point of the speedup (unless you could say that the data isn't really 'random', but was usually decreasing, such that the larger values would be found earlier).2010-12-26
  • 0
    Most of the data (if it's random) will be smaller than secondlargest. You can check this with one comparison. Your code uses two comparisons in these cases.2010-12-26
  • 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
    This is overkill if you want to find just the largest two.2010-12-26
  • 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