3 ms·

I don't know what the protocol is on HN, but I would be interested to see it. It seems to me that if you know the K'th largest, it's O(N); but otherwise, it's

• radq 15y ago
  > It seems to me that if you know the K'th largest, it's O(N); but otherwise, it's harder. Finding the kth largest element can be done in O(N) time. http://en.wikipedia.org/wiki/Selection_algorithm http://en.wikipedia.org/wiki/Selection_algorithm
• archgoon 15y ago
  The parent poster was making a joke. A simple such method is to scan the entire list, take the largest item, remove it from the list (or give it a fake value). Do this k times. k is fixed, so it's O(k*O(n))=O(n). Obviously, as k approaches n, this algorithm is in reality O(n^2)
  • veyron 15y ago
    I'd recommend you start from Sipser [http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/053494728X http://www.amazon.com/Introduction-Theory-Computation-Michae...] or Papadimitriou [http://www.amazon.com/Computational-Complexity-Christos-H-Papadimitriou/dp/0201530821/ref=sr_1_1?ie=UTF8&s=books&qid=1307258726&sr=1-1 http://www.amazon.com/Computational-Complexity-Christos-H-Pa...] to learn more about complexity theory (then we can discuss why your response is nonsense)
    • deleted 15y ago
      [deleted]
• Someone 15y ago
  http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k_smallest_or_largest_elements http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k...
• davidtgoldblatt 15y ago
  I suspect your parent poster is being facetious (if we fix k, then just keep a buffer of the k largest elements we've seen so far. For any new element we see, check if it's larger than the smallest element in the buffer and if so remove the smallest and insert the new one. This takes O(k) time, so the algorithm overall takes O(kn), which, since k is constant, is O(n)). In fact, this can be done in O(n) time even if k isn't constant: use the selection algorithm to find the k'th largest element (in O(n) time) and then go through the list again and output every number that's k or larger.
  • axman6 15y ago
    Doesn't this only work if the elements are unique? say you wanted the top three from [1,2,3,2,3,3,4,3,3,3,3,4,3], then the kth largest element would be 3, and we'd end up outputting [3,3,3,4,3,3,3,3,4,3], which is obviously not k elements.
    • davidtgoldblatt 15y ago
      For these types of problems you usually assume that every element is unique. The fix is just making two passes through the array instead of one, so it's still O(n). It's typically easy to reduce solving such a problem with duplicates allowed into a very similar one without duplicates. Just replace every element x by the ordered pair (x, the position in the array where x came from) and then use a modified comparison function that sorts according to the second element in the pair if two ordered pairs are equal in the first element.
• veyron 15y ago
  high level: you keep track of the K largest elements (call this array A). Every time you read an element (call it x), you compare it to the smallest element in A. if x is bigger than the smallest element of A, then remove the smallest element from A and add x to the list (and sort). There are N elements in the sequence, and you can arrange for the sorting to be a single-step bubble sort, so that the total cost is O(K) operations per element --> O(NK) overall. Noting that K is constant, it's O(N). Note that this really assumes K is constant. If K is depends on N, then the array A will expand