A further optimization would be to keep track of the lowest value in your "keep" set. A simple compare against that value will eliminate many of the add/removes from the keep set.
Brad On Jun 23, 1:35 am, Christophe Grand <christo...@cgrand.net> wrote: > On Tue, Jun 23, 2009 at 10:14 AM, Daniel Lyons <fus...@storytotell.org>wrote: > > > I have to admit I don't really understand your code, so my apologies if > > I've missed something obvious. > > > I think if you consider each element of N and do an operation that costs > > sqrt(N) with it, you'd arrive at O(N*sqrt(N)), which I think would be worse > > than O(N log N) > > I guess I must take another coffee, you're right I talked about sqrt instead > of log. My bad. > > > which is what you'd get from just sorting the whole structure and taking > > the top n items. Is it really sqrt(N)? I'm under the impression insertion > > into a balanced binary tree is O(log(N)), but wouldn't you still need to > > have N of them? This algorithm reminds me of heap sort. > > The tree never grows beyond (N+1) items, so insertion/deletion is always > O(log(N)). But you perform these operations for each item of the full seq, > ie nth times (but not Nth times) thus O(n*log(N)) > > Christophe --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~----------~----~----~----~------~----~------~--~---
