Paul Johnson <p...@cogito.org.uk> writes: >> takeLargest k = take k . sort
> But of equal practical interest is the space complexity. The optimum > algorithm is to take the first k items, sort them, and then iterate > through the remaining items by adding each item to the sorted list and > then throwing out the highest one. That has space complexity O(k). > What does the function above do? Well - 'sort' doesn't know the value of 'k', so it needs to retain all elements, just in case 'k' might be 'n'. So I don't see how you can use space less than 'n' for a construct like the above. -k -- If I haven't seen further, it is by standing in the footprints of giants _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
