![]() Curious to hear if you have contrary examples, though. I actually can't think of a scenario where the amortized complexity is better than non-amortized complexity and we don't default to amortized (std::vector::push_back, for example). I also don't think it's necessarily correct that people default to not talking about amortized analysis. There is a nice rigorous definition regarding potential functions here that shows that if you sum up the amortized complexity over a sequence of operations, it will necessarily be an upper bound for the standard complexity summed over that sequence of operations (note that "worst case" is never referenced in this definition). Classical analysis only considers complexity on a per-operation basis, whereas amortized complexity is about analyzing on a per-algorithm basis. This is a widely misunderstood point about amortization, but it is actually completely independent from the concept of "worst case" or "average case". "It's just that when you don't mention that you're talking about amortised complexity, the assumption is that it's worst case." (Depends on if you turned -O2 on, and bunch of other factors, including your compiler version and OS) There are some benchmarks in stackoverflow, which I haven't throughly read yet.Įdit : my friend pointed out that my numbers are wrong. Latter can be a lot slower (bigger constant factor).Ĭurrently priority queue is somewhere 1.5x to 2x faster than multiset with compiler optimizations. Multiset is a balanced binary search tree, which takes up to $$$O(\log n)$$$ time to delete anything and then assuring balance. To sum up, priority queue is a heap structure, which takes $$$O(\log n)$$$ time to delete top element. Unless it does that job, there might be some possbile occasions which a sequence of insertion and deletion makes multiset's internal implementation tree unbalanced and makes operation after that very slow (up to O(n)) Since it should be 'balanced' after insertion and deletion, it has to do some 're-balancing' (algorithms can vary by implementation, but generally rotating trees). As far as I know, multiset is implemented as a balanced binary tree as Enchom mentioned.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |