29 Apr
2007
29 Apr
'07
6:04 p.m.
Lubomir Bourdev wrote:
John,
On 4/29/07 12:41 AM, "John Femiani" <JOHN.FEMIANI@asu.edu> wrote:
Lubomir, Regarding your comment:
I haven't thought much about this, but this is k-order statistic (in an array of numbers, find the K-th smallest one). There is an algorithm to do this in O(N). This would be rather useful, perhaps someone should put it in Boost?
It is part of the stl already: std::nth_element in the <algorithm> header.
My understanding is that std::nth_element partially sorts the range, suggesting O(NlogN) running time. There are algorithms to return the n-th smallest element in an unordered list in O(N).
std::nth_element has (average) linear complexity.