4 ms·
> find the minimum of the elements being pointed at Can you describe how you would do this and talk about how it would impact the time complexity of the algori
by jaredsohn 9y ago
> find the minimum of the elements being pointed at
Can you describe how you would do this and talk about how it would impact the time complexity of the algorithm?
- unsatchmo 9y agoYou have to do K comparisons unless you keep track of the ordering of the other K-1 indices every time you pick a new element. Keeping a heap makes this log(K), yielding a KNlog(K) instead of K^2N. The naive solution is probably better when the number of lists to merge is small.
- btschaegg 9y agoI would guess the time complexity is the crux with this issue: Without knowing the nature of what the algorithm is used for in practice, you're left guessing. If you assume continuous memory "lists", cheap comparisons and a relatively small set of lists, you're not necessarily wrong to pick a brute-force approach, since maintaining the heap will result in much bigger constant factors in the complexity formula (even due to prefetching and so on). It's basically the same problem that peeks its head in every std::vector vs linked list discussion (and it's really amazing how many items you need before std::vector ceases to be a good pick for almost any problem).
- deleted 9y ago[deleted]