Tag Info

New answers tagged

4

After fidgeting around with the code a bit, I've got some better results. I went back to the original paper and ignored the wikipedia page. I've compared the algorithm to other quick select routines with some great results. Ok, here are the methods I have been playing with. Note these are for floating point and also that I changed my method from a void. ...


1

It seems to be me that you can trivially get rid of the cycles by moving all foreign keys to join tables. Once you've move all foreign keys to join tables, none of the original tables have dependencies on anything. The join tables have dependencies on the original tables. Nothing has dependencies on the join tables. In consequence, you have a trivial ...


0

As said in another answer, worst case better than O (n log n) is not possible. You can obviously try to be better in some or many cases. Calculate the minimum and maximum. Then calculate a bucket size so that any optimal group must belong completely to two consecutive buckets, and distribute the values into that number of buckets. That should work quite ...


4

To do this on a list that has not been sorted would require an algorithm that is worse than O(n log n), which is the best you can hope for to sort the list in the first place, meaning on an unsorted list O(n log n) is the best. However, it should be said that the sorting is an operation which must only be performed once, thus you could sort the list and ...


0

Do a "binning" of the initial black box stack into N groups of equal proportions (your A-D, D-K...). At that point you can use any O(n log n) algorithm to sort each group in turn. Actually, you could pop items from the black-box stack directly into a group of N red-black trees. But if you have lots of identical elements... could you not just store a ...


6

Answer: The element distinctness problem for lists of numbers is Θ(n log n) and you can reduce it to your problem in constant time by setting m=2 and checking whether the result is 0. So no, O(n log n) is optimal. (See the comments for a caveat, though) A bit more explanation for those unfamiliar with the reduction idea: In the mentioned element ...



Top 50 recent answers are included