That's got me. I can't see how to improve on the simple thing of scanning through the list keeping a sorted set of the best k. That's O(n log k). Obviously we can drop the relatively expensive square root operation, after which the distance measure is just x*x+y*y which is only 3 operations. You could do a first pass filtering by x+y, then return and consider x^2+y^2, but I doubt you'd gain anything by it. Monkey stumped. What devious trick is there here? - Dan
1 comment:
That's got me. I can't see how to improve on the simple thing of scanning through the list keeping a sorted set of the best k. That's O(n log k). Obviously we can drop the relatively expensive square root operation, after which the distance measure is just x*x+y*y which is only 3 operations. You could do a first pass filtering by x+y, then return and consider x^2+y^2, but I doubt you'd gain anything by it.
Monkey stumped. What devious trick is there here?
- Dan
Post a Comment